\(\text{FWT}\) 快速沃尔什变换
给定两个序列 \(a,b\) ，求解序列 \(c\) 满足：
\[c_i=\sum_{j\cdot k=i}a_jb_k \]其中 \(\cdot\) 可以为 \(\&\) ，\(|\) ，还有 \(\oplus\) 等位运算。快速沃尔什变换用于求解位运算卷积等问题。
\(\text{and}\) 、\(\text{or}\) 卷积
以 \(\text{or}\) 为例
记
\[FWT(a)_i=\sum_{j|i=i}a_j \]则
\[FWT(c)_i=FWT(a)_iFWT(b)_i=\sum_{j|i=i}a_i\sum_{k|i=i}b_k=\sum_{(j|k)|i=i}a_jb_k \]那么我们只要完成 \(a \rightarrow FWT(a)\) 和 \(FWT(a) \rightarrow a\) 这两种操作即可。
先考虑前者，分治处理，将 \(a\) 序列中按照下标最高位分类。记 \(a_0\) 为最高位为 \(0\) 的那一部分，\(a_1\) 为最高位为 \(1\) 的那一部分，考虑合并的过程：
\[FWT(a)=merge(FWT(a_0),FWT(a_0)+FWT(a_1)) \]\(merge\) 表示将两个序列拼接，\(+\) 表示对应位相加。其原理是 \(a_0\) 中的每一位都是其在 \(a_1\) 中的子集，需要做贡献。
那么第二种操作就是将上述分治过程逆过来即可：
\[a=merge(a_0,a_1-a_0) \]再来考虑 \(\text{and}\)
记
\[FWT(a)_i=\sum_{j \& i=i}a_j \]则
\[FWT(a)=merge(a_0+a_1,a_1) \]\[a=merge(a_0-a_1,a_1) \]\(\text{xor}\) 卷积
这里记
\[FWT(a)_i=\sum_{j\oplus i=0}a_j-\sum_{j \oplus i=1}a_j \]其中 \(j\oplus i=popcount(j \& i)\&1\) ，考虑每一位对答案的贡献，不难发现满足：
\[(j \oplus i)\: \text{xor}\: (k \oplus i)=(j \: \text{xor} \:k)\oplus i \]因此：
\[FWT(c)=FWT(a)FWT(b)=\left( \sum_{j \oplus i=0}a_j-\sum_{j\oplus i=1}a_j \right )\left( \sum_{k\oplus i=0}b_k-\sum_{k \oplus i=1}b_k\right) \]\[=\sum_{(j\:\text{xor} \: k)\oplus i=0}a_jb_k-\sum_{(j \: \text{xor} \:k)\oplus i=1}a_jb_k \]两部分求解过程依然是考虑分治与还原。
\[FWT(a)=merge(FWT(a_0)+FWT(a_1),FWT(a_0)-FWT(a_1)) \]\[a=merge\left(\frac{a_0+a_1}{2},\frac{a_0-a_1}{2}\right) \]然后到这里就做完了！
标签：xor,text,sum,笔记,merge,沃尔什,FWT,oplus From： https://www.cnblogs.com/oscaryangzj/p/17120641.html