FWT 是快速求形如 \(C(x)=\sum_{i?j=x}A(i)B(j)\) 的算法，其中 \(?\) 表示一种二进制的位运算。
原理
其实 FWT 背板挺容易的，但是因为考试趋向越来越本质化，所以我们要逐渐开始了解一些原来背板算法的原理。
类似于 FFT，我们考虑从最本源的地方来了解 FWT——构造一种线性变换 \(A\rightarrow A'\)，使得 \(C'(x)=A'(x)B'(x)\)，这样去掉线性变换的复杂度，总复杂度是 \(O(len)\) 的。需要注意的是，这里的 \(A,B,C\) 需要做同一种线性变换。
因为我们所做的是线性变换（即只存在加减），那么在 \(A'\) 中，我们可以把 \(A\) 中每个数对它的贡献用一个系数表示，即 \(A'(x)=\sum_i f(x,i)A(i)\)。
那么 \(C'(x)=\sum_i f(x,i)C(i)=\sum_if(x,i)\sum_{j?k=i}A(j)B(k)\)，\(A'(x)B'(x)=\sum_if(x,i)A(i)\sum_jf(x,j)B(j)\)。整理得 \(\sum_i\sum_jf(x,i?j)A(i)B(j)=\sum_i\sum_jf(x,i)f(x,j)A(i)B(j)\)。故有 \(f(x,i?j)=f(x,i)f(x,j)\)。
也就是说我们需要构造 \(f(x,i)\)，使得它满足上述需求。
对于或操作，有 \(f(x,i \text{ or }j)=f(x,i)f(x,j)\)，不难发现 \(i\text{ or }j\in x\Leftrightarrow i\in x\land j\in x\)，那么设 \(f(x,i)=[i\in x]\) 即可。
对于与操作，有 \(f(x,i\text{ and }j)=f(x,i)f(x,j)\)，和或相似的，\(x\in i\text{ and }j\Leftrightarrow x\in i\land x\in j\)。\(f(x,i)=[x\in i]\)。
对于异或操作，这可能就有些麻烦。我们需要挖掘一些异或的性质。对于两个数 \(x,y\)，显然 \(x\) 的 \(1\) 的个数加上 \(y\) 的 \(1\) 的个数的奇偶性和 \(x \text{ xor } y\) 的相同。而与和异或有恒等式 \((x\text{ xor } y)\text{ and } z=(x\text{ and }z)\text{ xor }(y\text{ and }z)\)（不难证明），所以 \(i\text{ and }x\) 的 \(1\) 的个数加上 \(j\text{ and }x\) 的 \(1\) 的个数的奇偶性和 \((i\text{ and }x)\text{ xor }(j\text{ and }x)=(i\text{ xor } j)\text{ and } x\) 的相同，而奇偶性的区分加减我们一般用 \((-1)^k\) ，所以设 \(f(x,i)=(-1)^{|x \text { and }i|}\) 即可。
实现
下面只讨论 FWT，对于 IFWT，其就是 FWT 的逆向过程。
考虑按位计算贡献。
设 \(f_k(S)\) 表示对于 \(S\)，已经计算了前 \(k\) 位任意，后面位数严格和 \(S\) 相等且暂未考虑其对贡献的影响的贡献。考虑从 \(f_k(S)\) 推到 \(f_{k+1}(S)\)。
考虑每个数对 \(u,v\) 互相的贡献，其中 \(u,v\) 仅在第 \(k+1\) 位不同，为了方便，设 \(u<v\)。
对于或，\(f_k(u)\) 中存的是后面位数和 \(u\) 相等，\(1\sim k\) 位是 \(u\) 子集的数的贡献，\(f_k(v)\) 同理，那么显然考虑了第 \(k+1\) 位后，\(f_{k+1}(u)=f_k(u)\) ，\(f_{k+1}(v)=f_k(u)+f_k(v)\)。
类似的，对于与，\(f_{k+1}(u)=f_k(u)+f_k(v)\) ，\(f_{k+1}(v)=f_k(v)\)。
对于异或，\(u\) 在 \(k+1\) 位对数的符号没有影响，而 \(v\) 在 \(k+1\) 位对 \(k+1\) 位为 \(1\) 的数的符号有一个 \(-1\) 的影响（因为之前没有考虑这一位对答案贡献的影响），所以 \(f_{k+1}(u)=f_k(u)+f_k(v)\)，\(f_{k+1}(v)=f_k(u)-f_k(v)\)。
这样就能在 \(O(len\log len)\) 的时间内对于 \(A\) 求得 \(A'\)。而逆变化就是正变化的相反操作，在此就不再赘述。