我们设 $c_{i,j}$ 表示数组 $X_j$ 对变换数组 $FWT[X]_i$ 的贡献系数，有 $FWT[X]_i=\displaystyle\sum_{j=0}^{len-1}c_{i,j}X_j$。$c_{i,j}$ 使用人类语言表述就是所有下指标是 $j$ 的 $X$ 都对变换数下指标 $i$ 的位置有 $c_{i,j}$ 的贡献，值得注意的是下指标可重，这对于下面的理解至关重要。

由于卷积数组 $FWT[C]_i=FWT[A]_i\times FWT[B]_i$，我们可以发现 $c_{i,j}\times c_{i,k}=c_{i,j\otimes k}$，其中 $\otimes$ 是我们需要进行卷积的位运算。

实际上可以这么理解，我们假设已经写出了卷积后 $A\otimes B$ 的所有项，其中 $A_j$ 和 $B_k$ 就会产生一个新的 $C_{j\otimes k}=A_j\times B_k$ 的项，下指标可重，所以我们要求对于 一个 $FWT[C]_i$ 和所有 $j$，算所有下指标是 $j$ 的项的 $c_{i,j}\times C_j$ 的和，发现和上面乘法的效果如出一辙。

于是我们得到了关于 $c$ 数组的一个重要性质。

常见的卷积套路是分两半，但是 FWT 不需要和 FFT 一样蝴蝶变换，直接按照原下标即可。$$FWT[X]_i=\displaystyle\sum_{j=0}^{\frac{len}{2}-1}c_{i,j}X_j+\displaystyle\sum_{j=\frac{len}{2}}^{len-1}c_{i,j}X_j$$

前后除了最高位具有完全相同的格式，直接根据多项式套路 $FWT[X]_i=c_{p,0}\displaystyle\sum_{j=0}^{\frac{len}{2}-1}c_{i’,j’}X_j+c_{2^p,1}\displaystyle\sum_{j=\frac{len}{2}}^{len-1}c_{i’,j’}X_j$ 就是对的，其中 $i’$、$j’$ 分别是 $i$、$j$ 除去最高位之后的数，$p$ 代表 $i$ 的最高位。

$p$ 只会是 $1$ 或者 $0$，剩下的直接迭代，所以我们只需要知道 $c_{0,0}$、$c_{0,1}$、$c_{1,0}$、$c_{1,1}$ 这 $4$ 项即可。

现在我们需要的就是构造出符合重要性质的 $c$。

对于按位或

我们构造 $c_{i,j}=[i=i\cup j]$，我们需要的 $4$ 项的值分别是 $1$、$0$、$1$、$1$。

对于按位与

同理构造 $c_{i,j}=[i=i\cap j]$。

对于按位异或

很困难的构造出 $$c_{i,j}=\begin{cases}1 & \text{popcount}(i\cap j)\bmod 2=0 \\ -1 & \text{otherwise.}\end{cases}$$

不难发现上述过程其实相当于在不断迭代的过程中给某两项乘上矩阵 $$\begin{bmatrix}c_{0,0} & c_{0,1}\\c_{1,0} & c_{1,1}\end{bmatrix}$$

所以其实 iFWT 时候我们需要的系数就很好求了，手动推出来上述矩阵的逆矩阵即可，理解就不很困难了。