Fast Walsh-Hadamard Transform (快速沃尔什变换)

Fast Walsh-Hadamard Transform (快速沃尔什变换)

做了一下（bestcoder#88）HDU 5909 ,发现是个树形dp。不小心写歪了就吃一个TLE。这个树形dp的复杂度是O（n*m^2），其实这个复杂度也能卡过吧。听说这里可以将O（m^2）优化成O（m*logm）,这里就用到了FWT，快速沃尔什变换，然而我并不懂。所以这几天看了下 Fast Walsh-Hadamard Transform ，感觉挺有趣的（骗你的），根据一位远古神犇的博客写了一些。

具体为什么是对的我还没有完全理清，大概就是个奇葩的构造吧……

Fast Walsh-Hadamard Transform 就是用于解决一类卷积问题的方法。大概如下：

其中

指任一二元逻辑位运算。

一些基础的想法： 为了加速这个运算，我们还是需要用一些类似FFT的东西。 注意到位运算都是有位独立性的，那么每次我们只考虑某一位？ 不妨假设：

此时：

当

指异或非运算、与非运算、或非运算时。

我们可以将 直接用异或运算、与运算、或运算的方法求出来，然后将互反的两位交换即可。

代码： 这里只贴一个与运算的代码，别的运算都可以类似实现。

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; }}

模板：

void FWT(int a[],int n) { for(int d=1;d

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。