FWT 小记

Fucious_Yin · 2024-12-17 07:30:44 · 算法·理论

FWT 小记

原问题

我们想做 c_i = \sum\limits_{j \oplus k = i}a_jb_k，其中 \oplus 是一种位运算。

基础思路

沿用 FFT 和 NTT 的思路，我们希望通过【可接受的复杂度的】线性变换得到（点值表达）A、B、C，使得点乘可得 C_i = A_i \cdot B_i，这样我们就能再变换回 c，也就完成了位运算卷积。

这种变换就是快速沃尔什变换（FWT），即 FWT(a) = A。我们称正向（a \rightarrow A，系数变点值）的过程为 FWT，逆向（A \rightarrow a，点值变系数）为 IFWT。（也有叫 DWT 和 IDWT 的，但惯用 FWT 了，能看懂就行 qwq）

我们设贡献系数 coe(i,j)，意为 A_i = \sum \limits_{j} coe(i, j)a_j，将其与 c_i = \sum\limits_{j \oplus k = i}a_jb_k、C_i = A_i \cdot B_i 联立，可以解得：对于 coe(i,j)，我们要求 coe(i,j)coe(i, k) = coe(i,j \oplus k)。

我们只需要构造这个系数即可。又由于位运算每一位独立，所以可以按位做，也就是我们 coe(i,j) 只需要对独立的一位（也就是空间中的一维）构造，这保证了比较优秀的复杂度。

其他理解

还有其他理解方式：

• 矩阵乘法：位运算下 coe(i,j) 形成了一个矩阵，显然变换就是乘，逆变换就是乘逆矩阵，所以你的构造的矩阵得有逆。

• 直接构造：（二进制下）我们对于或构造子集和，对于与构造超集和，对于异或构造 -1^{ppc(i \& j)}（其实是对着异或搁那构造）我天沃尔什怎么神了，可以推式子证明是对的。

这里采用矩阵的思路，注意到上面写的是 “位运算下” 而非 “二进制位运算下”，所以他是极具扩展性的。我们通常称这个矩阵为位矩阵。

具体实现

直接给出二进制或、与、异或运算的 FWT 矩阵和 IFWT 矩阵。

或： \begin{bmatrix} 1 & 0 \\ 1 & 1 \end{bmatrix} \begin{bmatrix} 1 & 0 \\ -1 & 1 \end{bmatrix} ，其分别对应了高维前缀和、前缀差分，二进制下前者就是子集和。

与： \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & -1 \\ 0 & 1 \end{bmatrix} ，其分别对应了高维后缀和、后缀差分，二进制下前者就是超集和。

异或： \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix} \begin{bmatrix} 0.5 & 0.5 \\ 0.5 & -0.5 \end{bmatrix}，组合意义天地灭代数推导保平安。

给出代码实现。看似三个循环其实就是在对每一位分别做，写成类高维前缀和的形式也是对的。

void fwt(int *f, int len, bool op){
    for (int k = 1; k < len; k <<= 1)
        for (int i = 0; i < len; i += k + k)
            for (int j = 0; j < k; ++j)if (op){
                f[i + j + k] = (f[i + j + k] + f[i + j]) % mod;

                f[i + j] = (f[i + j] + f[i + j + k]) % mod;

                int x = f[i + j], y = f[i + j + k];
                f[i + j] = (x + y) % mod, f[i + j + k] = (x - y) % mod;
            }
            else {
                f[i + j + k] = (f[i + j + k] - f[i + j]) % mod;

                f[i + j] = (f[i + j] - f[i + j + k]) % mod;

                int x = f[i + j], y = f[i + j + k];
                f[i + j] = (ll)(x + y) * inv2 % mod,
                f[i + j + k] = (ll)(x - y) * inv2 % mod;
            }
}

简单性质

由于 FWT 是一个线性变换，所以显然有加法和数乘的性质，即有：

• FWT(a+b) = FWT(a)+FWT(b)
• FWT(k \cdot a) = k \cdot FWT(a)

k 进制扩展

然后我们拓展到 k 进制下。

每一位取 \max，位矩阵是左下 1 矩阵，逆矩阵为单位矩阵和左下相邻是 -1 的矩阵。

每一位取 \min，位矩阵是右上 1 矩阵，逆矩阵为单位矩阵和右上相邻是 -1 的矩阵。

每一位不进位加法，单位根启动了，因为要有逆，直接拉范德蒙德矩阵，这个可能个比较常用。