FWT 笔记

用于给定 $A(x),B(x)$，解决计算

$$C(k)=\sum _{i\oplus j=k}A(i)B(j)$$

的问题。其中 $\oplus$ 是按位或，按位与或按位异或。

0. 核心思想

构造多项式 $F_A$，使得 $A$ 与其可以在 $O(n\log n)$ 的时间内相互转换，并且 $F_A\times F_B$ 可以在 $O(n)$ 内计算。

1. 按位或

构造

$$F_A(x)=\sum _{i\mathrm{or}x=x}A(i)$$

则

$$\begin{array}{rl}{F}_A(x)\times F_B(x)& =\sum _{i\mathrm{or}x=x}A(i)\sum _{j\mathrm{or}x=x}B(j)\\ & =\sum _{i\mathrm{or}x=x}\sum _{j\mathrm{or}x=x}A(i)B(j)\\ & =\sum _{(i\mathrm{or}j)\mathrm{or}x=x}A(i)B(j)\\ & =F_C(x)\end{array}$$

考虑如何将 $A$ 转换为 $F_A$，将 $A$ 的长度补到二的次幂后，可以进行分治，可以发现左边的数的最高位全为 $0$，右边的数的最高位全为 $1$。

除最高位外，左边的第 $i$ 个数和右边的第 $i$ 个数相同，因此，每一个左边的第 $i$ 个数都对右边的第 $i$ 个数有贡献。

按层自下向上递推，不断增加对右侧贡献的间隔长度即可。

考虑将 $F_A$ 转换为 $A$，分治后，右边的第 $i$ 个数要减去左边的第 $i$ 个数的贡献，因此这两个东西本质相同，一个函数即可解决。

点击查看代码

// 当前分治区间长度为 p，左端点为 i，半个区间的长度为 q
// 左边第 j 个数向右边第 j 个数贡献（i+j -> i+j+p）
void OR(int *f, int opt) {
    for (int p = 2, q = 1; p <= 1 << n; p <<= 1, q <<= 1)
        for (int i = 0; i < 1 << n; i += p)
            for (int j = 0; j < q; j++)
                f[i + j + q] = (f[i + j + q] + f[i + j] * opt + mod) % mod;
}

2. 按位与

和按位或同理，只是变成右边向左边贡献了。

点击查看代码

void AND(int *f, int opt) {
    for (int p = 2, q = 1; p <= 1 << n; p <<= 1, q <<= 1)
        for (int i = 0; i < 1 << n; i += p)
            for (int j = 0; j < q; j++)
                f[i + j] = (f[i + j] + f[i + j + q] * opt + mod) % mod;
}

3. 按位异或

构造

$$F_A(x)=\sum _{p(i\mathrm{and}x)mod2=0}A(i)-\sum _{p(i\mathrm{and}x)mod2=1}A(i)$$

其中 $p(x)$ 表示 $\mathrm{popcount}(x)$。

可以发现

$$(p(i\mathrm{and}j)mod2)\mathrm{xor}(p(i\mathrm{and}k)mod2)=(p(i\mathrm{and}j)+p(i\mathrm{and}k))mod2$$$$p(i\mathrm{and}(j\mathrm{xor}k))mod2=(p(i\mathrm{and}j)+p(i\mathrm{and}k)-2(i,j,k\mathrm{都}\mathrm{是}1\mathrm{的}\mathrm{位}\mathrm{置}))mod2$$

后面那个 $2$ 的倍数 $mod2$ 变成 $0$ 了。

令 $f(i)=p(i\mathrm{and}x)mod2$，故

$$f(i)\mathrm{xor}f(j)=f(i\mathrm{xor}j)$$

因此

$$\begin{array}{rl}{F}_A(x)\times F_B(x)& =(\sum _{f(i)=0}A(i)-\sum _{f(i)=1}A(i))(\sum _{f(j)=0}B(j)-\sum _{f(j)=1}B(j))\\ & =\sum _{f(i)=0\wedge f(j)=0}A(i)B(j)-\sum _{f(i)=0\wedge f(j)=1}A(i)B(j)-\sum _{f(i)=1\wedge f(j)=0}A(i)B(j)+\sum _{f(i)=1\wedge f(j)=1}A(i)B(j)\\ & =\sum _{f(i\mathrm{xor}j)=0}A(i)B(j)-\sum _{f(i\mathrm{xor}j)=1}A(i)B(j)\\ & =F_C(x)\end{array}$$

考虑 $A\to F_A$ 同样分治，左边第 $i$ 个数 $L$ 和右边第 $i$ 个数 $R$，二进制 $1$ 的个数奇偶必然不同。

首先考虑这个 $\mathrm{and}$，必然同 2 有右边向左边贡献。

接着考虑右边，因为全都多了一位，所以他们内部之间的 $p(i\mathrm{and}j)mod2$ 必然发生了改变，由于恰好是减号，所以直接取反。

由于只关心 $mod2$ 的值，所以左边也对右边有贡献。

综上，$L^{\prime }=L+R,R^{\prime }=L-R$。

考虑从 $F_A\to A$，则有 $L=\frac{L^{\prime }+R^{\prime }}{2},R=\frac{L^{\prime }-R^{\prime }}{2}$。

点击查看代码

void XOR(int *f, int opt) {
    for (int p = 2, q = 1; p <= 1 << n; p <<= 1, q <<= 1)
        for (int i = 0; i < 1 << n; i += p)
            for (int j = 0; j < q; j++) {
                int l = f[i + j], r = f[i + j + q];
                f[i + j] = (l + r) % mod * opt % mod;
                f[i + j + q] = (l - r + mod) % mod * opt % mod;
            }
}