本来这个东西要放到多项式那一章的，但想想还是算了，毕竟应用场景区别还是蛮大的。
听说还有叫子集反演的黑科技，有时间再补吧。
问题是这样的：给两个长为 \(2^n(n\le 17)\) 的序列 \(A,B\)，设
当 \(\operatorname{opt}\) 分别为 \(\rm or,and,xor\) 时求出 \(C\)。
考虑怎么做。
我们仿照 FFT 的思路，先把 \(A,B\) 变成点值表示，在对应项相乘，然后再变回序列。
我们一个一个运算来看
或运算的本质是枚举子集。
首先有一个显而易见的性质：若 \(i\operatorname{or} j=i,i\operatorname{or} k=i\)，则有 \((j\operatorname{or}k)\operatorname{or}i=i\)。
所以我们考虑这么构造：
考虑这么做的正确性：
现在考虑怎么 \(O(n\log n)\) 做 FWT。借鉴 DFT 的思路进行最高位 01 分类，记 \(A_0\) 为 \(A\) 序列下标最高位为 \(0\) 的序列，\(A_1\) 为下标最高位为 \(1\) 的序列，易知两个序列长度为当前序列的一半。得到以下式子：
括号表示把两个序列当成字符串拼接起来，\(+\) 代表序列对应位置的值相加。
很明显可以看出这个过程就是将子集的值不断往上累加的过程。
再考虑还原这个序列。之前是累加的过程，那还原就减掉即可。式子是：
与运算的本质是枚举超集。
那么我们完全按照或运算相反的方向推即可。
记 \(d(x,y)={\rm popcount}(x\operatorname{and}y)\bmod 2\)。
则有 \(d(i,j)\oplus d(i,k)=d(i,j\oplus k)\)。构造
然后证明 DWT 运算的正确性。我翻遍全网只找到了 xht37 的证明，然而没看懂，其他根本没人证，所以我也不证了。
变换的式子：
这个也不会证，什么玩意啊。
原文：https://www.cnblogs.com/wzzyr24/p/13291856.html