引入
这几天看了下 Fast Walsh-Hadamard Transform ，感觉挺有(gui)趣(chu)的，于是在这里写一下。
具体为什么是对的我还没有完全理清，大概就是个奇葩的构造吧……
之前有几个地方弄错了……现在修正了下。
简介
Fast Walsh-Hadamard Transform 就是用于解决一类卷积问题的方法。大概如下：
其中 指任一二元逻辑位运算。
这有什么用？呵呵……
一些基础的想法
为了加速这个运算，我们还是需要用一些类似FFT的东西。
注意到位运算都是有位独立性的，那么每次我们只考虑某一位？
不妨假设：
那么，我们的目标就是求出：
假如构造了一个变换 ，满足：
且可以在较短时间内进行变换 及其逆变换 ，那么我们的目标就可以实现了。
似乎便不能继续往下走了，那我们具体情况具体分析。
XOR
当 指异或运算的时候，即 SRM518 Nim 那题中所需要的方法。
此时：
接下来怎么来找变换 ？其实我并不知道这个变换是怎么找到的（可能哪个无聊的正好构造出来了？或者从很小的情况中顺藤摸瓜出来了？）。
但是这个变换确实存在，且形式比较漂亮。
虽然不知道这个是怎么构造出来的，不过我们还是可以很轻易地验证的。
AND
当 指与运算的时候，也是可以做的。
变换为：
同样轻易可验证。
OR
当 指或运算的时候，可以类比于与运算的变换：
XNOR,NAND,NOR
当 指异或非运算、与非运算、或非运算时。
我们可以将 直接用异或运算、与运算、或运算的方法求出来，然后将互反的两位交换即可。
代码
这里只贴一个与运算的代码，别的运算都可以类似实现。
void FWT( ll X[], int l, int r, int v ) {
if ( l == r ) return;
int m = ( l + r ) >> 1;
FWT( X, l, m, v ); FWT( X, m + 1, r, v );
FOR ( i, 0, m - l ) {
X[ l + i ] += X[ m + 1 + i ] * v;
}
}
