To_Heart—总结——FWT(快速沃尔什变换)

闲话

这个比FFT简单了很多呢，，大概是我可以学懂的水平！

好像是叫 快速沃尔什变换 ？

拿来求什么

以 FFT 来类比。我们 FFT 可以在 $\mathrm{O}(\mathrm{nlogn})$ 的复杂度下实现求解：

$$C_k=\sum _{i+j=k}{A}_i\times B_j$$

那么 FWT 的作用就是再 $\mathrm{O}(\mathrm{nlogn})$ 的时间复杂度下面求解：

$$C_k=\sum _{i\oplus j=k}{A}_i\times B_j$$

其中的 $\oplus$ 是位运算异或的意思。 FWT 应该是支持 $\oplus$、$|$、 $\&$ 三种位运算的。

然后就准备开始讲这三种位运算分别对应的算法。

或

我们定义 $\mathrm{FWT}(\mathrm{A}{)}_{\mathrm{i}}={\sum }_{j|i=i}{A}_j$。根据定义可以知道 $\mathrm{FWT}(\mathrm{A})$ 是一个由 $A$ 构造出来的多项式。先不管如何构造，我们考虑 $\mathrm{FWT}(\mathrm{A})$ 有什么用。我们发现：

$$\mathrm{FWT}(\mathrm{A})\times \mathrm{FWT}(\mathrm{B})$$
$$=\sum _{i=0}\mathrm{FWT}(\mathrm{A}{)}_{\mathrm{i}}\times \mathrm{FWT}(\mathrm{B}{)}_{\mathrm{i}}$$
$$=\sum _{i=0}(\sum _{j|i=i}{A}_j\times \sum _{k|i=i}{B}_k)$$

$$=\sum _{i=0}\sum _{(j|k)|i=i}{A}_j\times B_k$$

$$=\sum _{i=0}\sum _{(j|k)|i=i}{C}_i$$
$$=\mathrm{FWT}(\mathrm{C})$$

所以我们发现可以在 $\mathrm{O}(\mathrm{n})$ 的时间复杂度下实现由 $A,B$ 到 $C$ 的转换。所以现在的问题就是如何在 $\mathrm{O}(\mathrm{nlogn})$ 及以下的时间复杂度中求出 $\mathrm{FWT}(\mathrm{A})$ 。

考虑分治。假设 $A$ 有 $2^n$ 项，那么 $A_0$ 表示 $A$ 的前 $2^{n-1}$ ，$A_1$ 表示 $A$ 的后 $2^{n-1}$ 项。

然后就可以得到一个崭新的转移：

$$\mathrm{FWT}(\mathrm{A})=\{\begin{array}{ll}\mathrm{FWT}({\mathrm{A}}_0),\mathrm{FWT}({\mathrm{A}}_1)+\mathrm{FWT}({\mathrm{A}}_0)& n\ge 1\\ A& n=0\end{array}$$

这个 ,可以理解成把两个多项式拼起来。

如何理解这个式子呢？$n=0$ 的边界很好理解，问题在上面一个式子。

你考虑 $A_0$ 和 $A_1$ 的区别：在 $A$ 中且在 $A_0$中 的项的下标的最高位一定是 0 ；在 $A$ 中且在 $A_1$中 的项的下标的最高位一定是 1 ；

所以你发现从 $A_0$ 和 $A_1$ 向 $A$ 中只有可能是 $A_0$ 所在的项给 $A_1$ 所在的项做贡献。

所以就可以做到 $\mathrm{O}(\mathrm{nlogn})$ 的时间复杂度实现从 $A$ 到 $\mathrm{FWT}(\mathrm{A})$ 的转换了。

但是还需要实现从 $\mathrm{FWT}(\mathrm{A})$ 到 $A$ 的转换，也就是逆转换。

你感性理解一下，大概就是 A_0 会影响的两个位置，其中一个只有 A_0 ，另一个是 A_0+A_1 ，所以设 x_0 为改变的第一个位置， x_1 为改变的第二个位置，那么有 $x=A_0$ 和 $y=A_0+A_1$ 。现在是知道了 x 和 y ，所以 $A_0=x$，$A_1=y-A_0=y-x$

那么关于 或运算 的 FWT 就可以实现了：

void OR(ll *a,int n,int op){ //op=1是顺转换，op=-1是逆转换for(int mid=1;mid<n;mid<<=1) for(int len=mid<<1,j=0;j<n;j+=len) for(int i=j;i<j+mid;i++)a[i+mid]=(a[i+mid]+a[i]*op+Mod)%Mod;
}

与

这个和 或 差不多，但是注意到只有 $A_1$ 可以向 $A_0$ 贡献，所以反过来。

void AND(ll *a,int n,int op){for(int mid=1;mid<n;mid<<=1) for(int len=mid<<1,j=0;j<n;j+=len) for(int i=j;i<j+mid;i++)a[i]=(a[i]+a[i+mid]*op+Mod)%Mod;
}

异或

这个可能要麻烦一点。

异或本身并不好统一的下标之间的关联。什么意思呢？对于 或 ，我们可以很清楚的发现对于所有情况都是 $A_0$ 向 $A_1$ 做贡献；对于 与，所有情况都是 $A_1$ 向 $A_0$ 做贡献。但是异或并不满足这样的性质。所以需要考虑一种构造 $\mathrm{FWT}$ 的方式使得 $A_0$ 和 $A_1$ 的做贡献方式是一成不变的。

那么考虑怎么找到构造方式。