算法笔记-FWT快速沃尔什变换

快速沃尔什变换是干什么的

快速沃尔什变换，英文名Fast Walsh–Hadamard transform，简称FWT，是用来在 $O(n logn)$ 的复杂度下完成Hadamard transform的。当然，如果你有量子计算机的话复杂度是 $O(1)$ 。这个变换可以被看作一个矩阵 H而$(H)_{i,j}$可以被看作 $\frac{1}{2^{\frac{n}{2}}} (-1)^{i \cdot j}$ 其中 $i \cdot j$ 表示 $i$ 和 $j$ 二进制表示的点积。
Hadamard transform被应用于加密算法，压缩算法，量子计算中的质因数分解算法等。

对于算法竞赛选手，最重要的是快速沃尔什变换的思想,而Hadamard transform于我们而言只是现场推得的式子，没有深究的必要。我们在处理如下形式的式子时会使用快速沃尔什变换。$C_k = \sum_{i\;xor\;j=k}a[i]*b[j]$接下来我们探讨一下如何在 $O(nlogn)$ 的复杂度下搞定这个东西。

咋整

这种东西和多项式卷积长得非常像，所以着手点在于变换成一个类似于多项式点值的表示法，然后直接两个点积一下再变换回来。

又由于位运算这种东西显然按位搞比较方便，我们可以考虑按位分治。

假设枚举下标的当前位，为零的记为 $a_0\;b_o$ ,为1的记为 $a_1 b_1$ ，那么根据异或的定义，

$$c_o=a_0*b_1+a_1*b_0$$ $$c_1=a_0*b_0+a_1*b_1$$

我们可以构造 $x_0x_1y_0y_1$
满足 $x_0=a_0+a_1，x_1=a_0-a_1$ 且 $y_0=b_0+b_1，y_1=b_0-b_1$

随后点积，$x_0 \cdot y_0=a_0b_0+a_0b_1+a_1b_0+a_1b_1$ ，

$ x_1 \cdot y_1=a_0b_0-a_0b_1-a_1b_0+a_1b_1$ ，

$c_0$ 即为 $\frac{x_0 \cdot y_0 - x_1 \cdot y_1}{2}$ ，

$c_1$ 即为 $\frac{x_0 \cdot y_0 + x_1 \cdot y_1}{2}$

那么只要从低位到高位递归地操作即可， $x$ 和 $y$ 就是所得到的类似多项式点值表示的数组。

代码如下

template<typename T>
void fwt(LL a[], int n, T f) {
    for (int d = 1; d < n; d *= 2)
        for (int i = 0, t = d * 2; i < n; i += t)
            for (int j = 0; j < d; j++)
                f(a[i + j], a[i + j + d]);
}
void XOR (LL& a, LL& b) {
    LL x = a, y = b;
    a = (x + y) % MOD;
    b = (x - y + MOD) % MOD;
}
void rXOR(LL& a, LL& b) {
    static LL INV2 = (MOD + 1) / 2;
    LL x = a, y = b;
    a = (x + y) * INV2 % MOD;
    b = (x - y + MOD) * INV2 % MOD;
}

只需要对a和b都调用XOR进行变换，点积之后做rXOR即可求得c。

其实，这一段代码所进行的变换就是Hadamard transform，对于其他的X进制上的位运算，我们都可以用类似方法得到一个变换。本质就是运用乘法结合律将信息重新存储到指定位置，然后减少计算次数。对于比较变态的位操作，比如说三进制位上取mex，可以在数组中插入空位，扩充为四进制来做。