FWT
FWT 的思想就是将数列经过变换后，将位运算卷积变为逐位相乘，最终通过逆变换将其得到所求数列。单次 FWT 的时间复杂度为 \(O(2^nn)\) 可以将 \(O(3^n)\) 甚至更高的卷积优化。
或卷积
有 \(C_s=\sum_{s=t|z}A_t\times B_z\) ，\(FWT(F)_s=\sum_{t \subseteq s}F_t\)。
可以发现 \(FWT\) 的变换就是求每个集合的子集和，这个东西是容易用高维前缀和做到 \(O(2^nn)\)。下面将证明它的正确性：
\[FWT(C)_s=FWT(A)_s \times FWT(B)_s \\
\sum_{w\subseteq s}C_s=\sum_{x\subseteq s}A_x \sum_{y\subseteq s}B_y\\\sum_{w\subseteq s} \sum_{w=x|y} A_x\times B_y=\sum_{x\subseteq s}A_x \sum_{y\subseteq s}B_y
\]
发现两边意义相同，证毕。
由于其良好的性质，计算单值时可以做到 \(O(2^n)\) ，简单容斥即可。
与卷积
和或卷积几乎同理。
异或卷积
有 \(C_s=\sum_{s=t\oplus z}A_t\times B_z\) ，\(FWT(F)_s=\sum_{t\circ s=0}F_t-\sum_{t\circ s=1}F_t\)。
(定义\(s\circ t=popcount(s\&t)(mod\ 2)\))
变换本身是容易的，直接依次考虑 \(2^i\) 的贡献即可，证明如下：
\[FWT(C)_s=FWT(A)_s\times FWT(B)_s\\
\sum_{t\circ s=0}C_t-\sum_{t\circ s=1}C_t=(\sum_{x\circ s=0}A_t-\sum_{x\circ s=1}A_t)(\sum_{y\circ s=0}B_t-\sum_{y\circ s=1}B_t)\\
\sum_{t\circ s=0}\sum_{x\oplus y=t}A_xB_y-\sum_{t\circ s=1}\sum_{x\oplus y=t}A_xB_y=
(\sum_{x\circ s=0}A_t\sum_{y\circ s=0}B_t+
\sum_{x\circ s=1}A_t\sum_{y\circ s=1}B_t)-
(\sum_{x\circ s=0}A_t\sum_{y\circ s=1}B_t+
\sum_{x\circ s=1}A_t\sum_{y\circ s=0}B_t)
\]
注意到有 \((x\oplus y)\circ s=(x\circ s)\oplus (y\circ s)\)，所以式子左右两边相等。
子集卷积
子集卷积一般使用或卷积实现，在或卷积的基础上，再加上位数的限制就行了。时间复杂度会多一个 \(n\)。