仅供学习。
给定长度为 \(2^n\) 两个序列 \(A,B\)，设
\[C_i=\sum_{j\oplus k = i}A_j \times B_k
\]
分别当 \(\oplus\) 是 or,and,xor 时求出 \(C\)
or
\[c_{i}=\sum_{j|k\in i} a_{j} b_{k}
\]
定义 \(fwt[a]_i = \sum_{j\in i} a_j\)
显然 $$ \begin{aligned} fwt[a] \times fwt[b] &= \left(\sum_{j\in i} a_j\right)\left(\sum_{k\in i} b_k\right) \\ &= \sum_{j\in i} \sum_{k\in i} a_jb_k \\ &= \sum_{(j|k)\in i} a_jb_k \\ &= fwt[c] \end{aligned} $$
其中 \(c=a|b\)
则有$$ fwt[a] = \text{merge}(fwt[a_0], fwt[a_0] + fwt[a_1]) $$ 其中 \(\text{merge}\) 表示「拼接」，\(+\) 表示对应位置相加。
这里 \(a_0\) 表示 \(a\) 中 前 \(2^{n-1}\) 个数。
反之显然。