$FWT$通常用来求位运算卷积。
卷积是这样一种东西：$c_k=\sum_{i\circ j}a_i*b_j$
式子中的$\circ$表示一种运算。
乘法卷积就是$+$，狄利克雷卷积就是$*$，子集卷积就是$\subseteq$，位运算就是$\&,|,xor$

根据$FFT$的套路，我们需要找到一个变换$T(A)$以及逆变换$IT(A)$，满足：
$T(AB)=T(A)\cdot T(B)，IT(T(AB))=AB$此处的 $\cdot$ 为对位乘法，$AB$使用的是对应卷积。

1. or卷积：

如果$~k=i~|~j$，那么二进制位中$i,j$都是$k$的子集，下面的$\subseteq$就是二进制意义下的子集。
要想$T(AB)=T(A)T(B)$，构造：$T(A)_i=\sum_{j\subseteq i}A_j$ 那么$T(AB)_i=\sum_{j\subseteq i}\sum_{k|l=j}A_kB_l\\T(A)T(B)_i=\sum_{k\subseteq i}\sum_{l \subseteq i}A_kB_l$显然上面两式相等，第一项相当于多枚举了一个$j=k|l$。其中的原理是$(j|k)\subseteq i$等价于$j\subseteq i\wedge k\subseteq i$
怎么求$T(A)$呢？根据二进制位分治，假设$A$的下标范围是$[0,2^k)$，令$A_0$表示$A$的前一半，$A_1$表示$A$的后一半，那么有：
$T(A)=merge(T(A_0),T(A_0)+T(A_1))$当前位为0的情况是为1的子集，所以把左边加到右边就可以了。

如何求逆变换$IT(A)$呢？相当于已经知道$A_0',A_1'$，求$A_0,A_1$，已知$A_0'=A_0,A_1'=A_0+A_1$，那么$A_0=A_0',A_1=A_1'-A_0'$：$IT(A')=merge(IT(A_0'),IT(A_1'-A_0'))$
由变换的性质我们知道$T(A+B)=T(A)+T(B)$，所以上式可以写作：$IT(A')=merge(IT(A_0'),IT(A_1')-IT(A_0'))$

补充：在某些情况下(优化常数)，我们需要在已知变换$T(A)$的情况下对特定的$i$求出$A_i$，这时并不需要IFWT，由定义以及容斥原理可知$A_i=\sum_{j\subseteq i}(-1)^{|i|-|j|}T(A)_j$

2.and卷积：

与$or$卷积类似，基于$(i\&k=k)\wedge(j\&k=k)\lrArr((i\&j)\&k=k)$，构造：$T(A)_i=\sum_{i\&j=i}A_j$
它的$FWT$变换和逆变换分别为：$T(A)=merge(T(A_0)+T(A_1),T(A_1))$$IT(A')=merge(IT(A_0')-IT(A_1'),IT(A_1'))$

同样的，由定义及容斥原理可得$A_i=\sum_{i\subseteq j}(-1)^{|j|-|i|}T(A)_j$

3.xor卷积：

异或卷积同样需要与上面一样找到一种操作使得$(i~xor~j)\circ k$与$i\circ k$和$j\circ k$产生联系。
异或操作的性质是两个数异或后不改变二进制为1的个数的奇偶性，即$d(i)~xor~d(j)=d(i~xor~j)$，其中$d(i)$表示$i$的二进制中1的个数的奇偶性。
于是可以发现：$d(i\&k)~xor~d(j\&k)=d((i~xor~j)\&k)$
但是上面的操作是用$\wedge$（且）符号连接的，所以直接相乘就可以了，用$xor$符号连接咋整？
令$d(i)$为1的带上$-1$的系数就完美解决了这个问题，偶偶为偶，奇奇为偶，奇偶为奇，跟异或操作如出一辙。
所以我们的变换为：$T(A)_i=\sum_{d(i\&j)=0}A_j-\sum_{d(i\&j)=1}A_j$
我们简单地观察一下$T(AB)$和$T(A)T(B)$：$T(AB)_k=\sum_{d(l\&k)=0}\sum_{i~xor~j=l}A_iB_j-\sum_{d(l\&k)=1}\sum_{i~xor~j=l}A_iB_j$$T(A)T(B)_k=(\sum_{d(i\&k)=0}A_i-\sum_{d(i\&k)=1}A_i)*(\sum_{d(j\&k)=0}B_j-\sum_{d(j\&k)=1}B_j)\\=\sum_{d(i\&k)~xor~d(j\&k)=0}A_iB_j-\sum_{d(i\&k)~xor~d(j\&k)=1}A_iB_j$
由上面所说$d$的性质明显可以看出两式相等。
它的$FWT$变换为：$T(A)=merge(T(A_0)+T(A_1),T(A_0)-T(A_1))$
如果最高位为0，$and$后$d$的奇偶性不变，两式相加；如果最高位为1，右边$and$后$d$的奇偶性取反。
逆变换：$IT(A')=merge({IT(A_0')+IT(A_1')\over2},{IT(A_0')-IT(A_1')\over2})$

它的反演形式为$A_i=\frac 1{n}\sum_{}(-1)^{|i\&j|}T(A)_j$，带入即可得证。

4.子集卷积

下面这个图片截自Rose_max的博客

一点小拓展：

给出序列$a_1,...,a_n$以及$p$，求$i\in[1,n]$的$(1+px^{a_i})$的异或卷积。
分治FWT复杂度太高。
考虑$(1+px^{a})$的对应的多项式$b_ix^i$的$FWT$变换：$c_i=\sum\limits_{j}(-1)^{d(i\&j)}b_j$
1对于$c_i$的贡献是$j=0$时的$(-1)^0=1$，$p$对于$c_i$的贡献是$j=a$时的$(-1)^{d(i\&{a})}$，我们并不知道后一项是-1还是1，但是我们可以确定$c_i$要么等于$1+p$，要么等于$1-p$

假设$n$个$(1+px^a)$中第$i$位有$k$个为$1+p$，$n-k$个为$1-p$，$n$个$FWT$变换的和为$f$，则有：
$k(1+p)+(n-k)(1-p)=f_i$

因为$FWT(A)+FWT(B)=FWT(A+B)$，所以我们可以将所有式子加起来FWT一下求出$f_i$，从而得出每个位置的$k$。

那么最后所有式子FWT的对应位置的乘积$c_i=(1+p)^k(1-p)^{n-k}$，然后$IFWT$回去即可得到最终的异或卷积。

拓展之后的拓展：

给出一张$n*k$的表$p_{i,j}$，$p\in[0,2^m)$，以及$k$个数$a_i$，记第$i$个多项式$F_i(x)$为$\sum_{j=1}^ka_jx^{p_{i,j}}$，求$\oplus_{i=1}^nF_i(x)$（异或卷积）
暴力复杂度是$O(2^mnm/2^mnk)$，要求做到$O(2^{m}m*2^k+n*2^k)$

出处：【模拟赛】西行寺无余涅槃

子集卷积及占位多项式应用

具体可以看这道题 UOJ94，题解
这个是论文中求连通生成子图的解法：

在占位集合幂级数中，一部分是形式幂级数，一部分是集合幂级数，对于集合幂级数的乘法，先做莫比乌斯变换后转化为单点乘法；对于形式幂级数的乘法，就是普通的幂次相加，求ln相当于是对占位多项式求ln，每个$x$此时是一个变换后的集合幂级数。