FWT(快速沃尔什变换)零基础详解qaq（ACM/OI）

1.前言（废话）

记得一年半之前做SRM518 Nim的时候还不知道FWT，当时自己用分治完美的水过去了。然后昨天的牛客有一道题，是说nim博弈中有n堆石子，请问最多取出多少堆石子可以让先手必败。当时竟然没思路QAQ？？？想了想使劲往字典树靠边靠不上去QAQ，然后就没想出来！！！

想当年自己手推FWT或运算，真的感叹岁月是把杀猪刀！于是怒写这篇博客QAQ把这个算法总结一下QAQ

（其实我觉得这变换竟然也有名字真的很神奇QAQ）

2.FWT简介

沃尔什转换（Walsh Transform）是在频谱分析上作为离散傅立叶变换的替代方案的一种方法。
——wiki百科

其实这个变换在信号处理中应用很广泛，fft是double类型的，但是walsh把信号在不同震荡频率方波下拆解，因此所有的系数都是绝对值大小相同的整数，这使得不需要作浮点数的乘法运算，提高了运算速度。

所以，FWT和FFT的核心思想应该是相同的。都是对数组的变换。我们设数组A经过快速沃尔什变换之后记作

那么FWT核心思想就是：

我们需要一个新序列C，由序列A和序列B经过某运算规则得到，即

。我们先正向得到

,然后根据

（*为点乘），在O(n)求出

,然后再逆向运算得到原序列C。 时间复杂度为

在算法竞赛中，FWT是用于解决对下标进行位运算卷积问题的方法。

公式：

其中

是任意二元位运算中的某一种，

就是普通乘法。

3.FWT的运算

3.1FWT之与（&）运算和或（|）运算

与运算和或运算的本质是差不多的，所以这里讲一下或运算，与运算也是可以自己根据公式yy出来的。

3.1.1或运算

如果有

，那么i的二进制位为1的位置和j的二进制位为1的位置肯定是k的二进制位为1的位置的子集。

现在要得到

，我们就要构造这个fwt的规则。

我们按照定义，显然可以构造

,表示j满足二进制中1为i的子集。

那么显然会有

即

那么我们接下来看

怎么求。首先肯定不能枚举了，复杂度为n^2。既然不能整体枚举，我们就考虑分治。

我们把整个区间二分，其实二分区间之后，下标写成二进制形式是有规律可循的。

我们令

表示A的前一半，

表示区间的后一半，那么A0就是A下标最大值的最高位为0，他的子集就是他本身的子集（因为最高位为0了），但是A1的最高位是1，他满足条件的子集不仅仅是他本身，还包最高位为0的子集，即

其中merge表示向字符串拼接一样把他们拼起来。+就是普通加法，表示对应二进制位相加。

这样我们就通过二分能在logn完成拼接，每次拼接的时候要完成一次运算，也就是说在

的时间复杂度得到了

接下来就是反演了，其实反演是很简单的，既然知道了A0的本身的子集是他自己(A0 = FAT[A0])，A1的子集是 FAT[A0] + FAT[A1]（A1' = A0' + A1'）,那就很简单的得出反演的递推式了

3.1.2与运算

与运算类比或运算可以得到类似结论

3.2异或运算

最常考的异或运算。

异或的卷积是基于如下原理：

若我们令i&j中1数量的奇偶性为i与j的奇偶性，那么i与k的奇偶性异或j和k的奇偶性等于i^j和k的奇偶性。

对于

的运算其实也很好得到。

公式如下

(C1表示i&j奇偶性为0，C2表示i&j的奇偶性为1)

结论

3.3 同或运算

类比异或运算给出公式：

(C1表示i|j奇偶性为0，C2表示i|j的奇偶性为1)

QAQ