>
快速沃尔什变换（FWT）和子集卷积
2025-08-22 学习笔记 约 3.5 千字

引入 FWT

快速沃尔什变换（FWT）是解决这样一类卷积问题：

ci=∑i=j⊙kajbkc_i=\sum_{i=j\odot k}a_jb_k

其中，⊙\odot 是位运算的一种。举个例子，给定数列 a,ba,b，求：

ci=∑j⊕k=iajbkc_i=\sum_{j\oplus k=i} a_jb_k

FWT 的思想

看到 FWT 的名字，我们可以联想到之前学过的 FFT（很可惜，我没有写过 FFT 的笔记，所以没有链接），先看看 FFT 的原理：

  1. 把 a,ba,b 变换为 A,BA,B，O(nlog⁡n)O(n\log n)；
  2. 通过 Ci=AiBiC_i=A_iB_i 计算，O(n)O(n);
  3. 把 CC 变换回 cc，O(nlog⁡n)O(n\log n)。

综上，时间复杂度是 O(nlog⁡n)O(n\log n) 的。

在 FFT 中，我们构造了 A,BA,B 为 a,ba,b 的点值表示法，这么做满足 Ci=AiBiC_i=A_iB_i 且容易变换。

其实 FWT 的思想也是一样的，主要也是需要构造 A,BA,B，使得其满足 Ci=AiBiC_i=A_iB_i 且可以快速变换。下面我们举 ∪\cup（按位或）、∩\cap（按位与）和 ⊕\oplus（按位异或）为例。

因为数列长度是 22 的幂会更好处理，所以下文认为数列长度为 2n2^n。

按位或

ci=∑j∪k=iajbkc_i=\sum_{j\cup k=i} a_jb_k

我们可以构造 Ai=∑i∪j=iaiA_i=\sum_{i\cup j=i} a_i。看看为什么需要这么构造。

首先，它满足 Ci=AiBiC_i=A_iB_i：

AiBi=(∑i∪j=iaj)(∑i∪k=ibk) =∑i∪j=i∑i∪k=iajbk =∑i∪j=i∑i∪k=iajbk =∑i∪(j∪k)=iajbk =Ci\begin{align} A_iB_i&=(\sum_{i\cup j=i} a_j)(\sum_{i\cup k=i} b_k) \\\ &=\sum_{i\cup j=i}\sum_{i\cup k=i}a_jb_k \\\ &=\sum_{i\cup j=i}\sum_{i\cup k=i}a_jb_k \\\ &=\sum_{i\cup(j\cup k)=i}a_jb_k \\\ &= C_i \end{align}

其次，它可以快速变换。举顺变换的例子。类比 FFT 的步骤，我们采用分治的方法来处理它。假设目前考虑到第 ii 位，其中 A0A_0 和 A1A_1 是 i−1i-1 位分治的结果：

A=merge(A0,A0+A1)A=\text{merge}(A_0, A_0+A_1)

其中，A0A_0 是数列 AA 的左半部分，A1A_1 是 AA 的右半部分。merge\text{merge} 函数就是把两个数列像拼接字符串一样拼接起来。++ 则是将两个数列对应相加。

这么做为什么是正确的呢？容易发现，A0A_0 恰好是当前处理到的二进制位为 00 的子数列，A1A_1 则是当前处理到的二进制位为 11 的子数列。若当前位为 00，则只能取二进制位为 00 的子数列 A0A_0 才能使得 i∪j=ii\cup j=i。而若当前位为 11，则两种序列都能取。

考虑逆变换，则是将加上的 A0A_0 减回去：

a=merge(a0,a1−a0)a=\text{merge}(a_0, a_1-a_0)

下面我们给出代码实现。容易发现顺变换和逆变换可以合并为一个函数，顺变换时 type=1\text{type}=1，逆变换时 type=−1\text{type}=-1。

void OR(int a[], int n, int tp) {
    for (int len = 2; len <= n; len <<= 1) {
        for (int i = 0; i < n; i += len) {
            for (int j = i; j < i + (len >> 1); j ++ ) {
                add(a[j + (len >> 1)], a[j] * tp);
            }
        }
    }
}

按位与

ci=∑j∩k=iajbkc_i=\sum_{j\cap k=i} a_jb_k

同理构造 Ai=∑i∩j=iaiA_i=\sum_{i\cap j=i} a_i。Ci=AiBiC_i=A_iB_i 的正确性不证了。

容易发现，A0A_0 恰好是当前处理到的二进制位为 00 的子数列，A1A_1 则是当前处理到的二进制位为 11 的子数列。若当前位为 11，则只能取二进制位为 11 的子数列 A0A_0 才能使得 i∩j=ii\cap j=i。而若当前位为 00，则两种序列都能取。

A=merge(A0+A1,A1)A=\text{merge}(A_0+A_1, A_1)

a=merge(a0−a1,a1)a=\text{merge}(a_0 - a_1, a_1)

下面我们给出代码实现。顺变换时 type=1\text{type}=1，逆变换时 type=−1\text{type}=-1。

void AND(int a[], int n, int tp) {
    for (int len = 2; len <= n; len <<= 1) {
        for (int i = 0; i < n; i += len) {
            for (int j = i; j < i + (len >> 1); j ++ ) {
                add(a[j], a[j + (len >> 1)] * tp);
            }
        }
    }
}

按位异或

发现异或有点难搞，对此我们引入一个新的运算符 ∘\circ。定义 x∘y=popcnt(x∩y) mod 2x\circ y=\text{popcnt}(x\cap y)\bmod 2，其中 popcnt\text{popcnt} 表示二进制下 11 的个数，并重申一下 ∩\cap 表示按位与。

不用慌，我们也不需要你真正实现一个 popcnt\text{popcnt}，它仅仅只是作为一个理解的辅助罢了。

我们发现它满足 (x∘y)⊕(x∘z)=x∘(y⊕z)(x\circ y)\oplus (x\circ z)=x\circ(y\oplus z)。（重申一下 ⊕\oplus 表示按位异或）

感性证明：发现这个新的运算符 ∘\circ 其实就是 xx 与 yy 相同位数的奇偶性。若 (x∘y)⊕(x∘z)=0(x\circ y)\oplus (x\circ z)=0，则 xx 与 yy、xx 与 zz 相同位数个数奇偶性相同，所以 y⊕zy\oplus z 和 xx 相同位数个数奇偶性也是相同的 ；若 (x∘y)⊕(x∘z)=1(x\circ y)\oplus (x\circ z)=1，则 xx 与 yy、xx 与 zz 相同位数个数奇偶性不同，所以 y⊕zy\oplus z 和 xx 相同位数个数奇偶性也是不同的。

设 Ai=∑i∘j=0aj−∑i∘j=1ajA_i=\sum_{i\circ j=0}a_j-\sum_{i\circ j=1}a_j。我们来证一下 Ci=AiBiC_i=A_iB_i 的正确性：

AiBi=(∑i∘j=0aj−∑i∘j=1aj)(∑i∘k=0bk−∑i∘k=1bk) =(∑i∘j=0aj∑i∘k=0bk+∑i∘j=1aj∑i∘k=1bk)−(∑i∘j=0aj∑i∘k=1bk+∑i∘j=1aj∑i∘k=0bk) =∑(j⊕k)∘i=0ajbk−∑(j⊕k)∘i=1ajbk =Ci\begin{align} A_iB_i&=(\sum_{i\circ j=0}a_j-\sum_{i\circ j=1}a_j)(\sum_{i\circ k=0}b_k-\sum_{i\circ k=1}b_k) \\\ &=(\sum_{i\circ j=0}a_j\sum_{i\circ k=0}b_k+\sum_{i\circ j=1}a_j\sum_{i\circ k=1}b_k)-(\sum_{i\circ j=0}a_j\sum_{i\circ k=1}b_k+\sum_{i\circ j=1}a_j\sum_{i\circ k=0}b_k) \\\ &=\sum_{(j\oplus k)\circ i=0}a_jb_k-\sum_{(j\oplus k)\circ i=1}a_jb_k \\\ &=C_i \end{align}

来看看怎么快速计算 A,BA,B 的值，依旧是分治：

对于 ii 在当前位为 00 的子数列 A0A_0，进行 ∘\circ 运算时发现它和 00 计算或和 11 计算结果都不会变（因为 0∩0=0,0∩1=00\cap 0=0,0\cap1=0），所以 Ai=∑i∘j=0aj−∑i∘j=1ajA_i=\sum_{i\circ j=0}a_j-\sum_{i\circ j=1}a_j 中的 ∑i∘j=1aj=0\sum_{i\circ j=1}a_j=0。

对于 ii 在当前位为 11 的子数列 A1A_1，进行 ∘\circ 运算时发现它和 00 计算结果是 00，和 11 计算结果是 11（因为 1∩0=0,1∩1=11\cap 0=0,1\cap1=1）。

综上，有：

A=merge((A0+A1)−0,A0−A1)A=\text{merge}((A_0+A_1)-0, A_0-A_1)

也就是：

A=merge(A0+A1,A0−A1)A=\text{merge}(A_0+A_1, A_0-A_1)

逆变换易得：

a=merge(a0+a12,a0−a12)a=\text{merge}(\frac{a_0+a_1}{2}, \frac{a_0-a_1}{2})

给出代码，顺变换时 type=1\text{type}=1，逆变换时 type=12\text{type}=\frac{1}{2}。

void XOR(int a[], int n, int tp) {
    for (int len = 2; len <= n; len <<= 1) {
        int k = (len >> 1);
        for (int i = 0; i < n; i += len) {
            for (int j = i; j < i + k; j ++ ) {
                int ls = a[j], rs = a[j + k];
                a[j] = 1ll * (ls + rs) % mod * tp % mod;
                a[j + k] = 1ll * (ls - rs + mod) % mod * tp % mod;
            }
        }
    }
}

性质

类似 DFT，我们构造出的 FWT 也是一个线性变换。所以我们能得出如下性质：

FWT(A+B)=FWT(A)+FWT(B)FWT(λ⋅A)=λ⋅FWT(A)\begin{aligned} \mathrm{FWT}(A+B) & =\mathrm{FWT}(A)+\mathrm{FWT}(B) \\ \mathrm{FWT}(\lambda \cdot A) & =\lambda \cdot \mathrm{FWT}(A) \end{aligned}

「洛谷 P4717」【模板】快速莫比乌斯/沃尔什变换 (FMT/FWT)

求 ∪\cup、∩\cap、⊕\oplus 的三种卷积。n≤17n\le17。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> PII;

#define fir first
#define sec second
#define ep emplace
#define eb emplace_back

#define lowbit(x) ((x) & (-(x)))
#define add(a, b) ((a) = ((a) + (b) >= mod))

inline int read() {
    int x = 0, f = 1; char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
    for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
    return x * f;
}

const int N = 131075;
const int mod = 998244353;

int lgn, n, a[N], b[N], c0[N], c1[N];

#define add(a, b) { \
    if (((a) = (a) + (b)) >= mod) (a) -= mod; \
    if (a < 0) a += mod; \
}

void OR(int a[], int n, int tp) {
    for (int len = 2; len <= n; len <<= 1) {
        for (int i = 0; i < n; i += len) {
            for (int j = i; j < i + (len >> 1); j ++ ) {
                add(a[j + (len >> 1)], a[j] * tp);
            }
        }
    }
}

void AND(int a[], int n, int tp) {
    for (int len = 2; len <= n; len <<= 1) {
        for (int i = 0; i < n; i += len) {
            for (int j = i; j < i + (len >> 1); j ++ ) {
                add(a[j], a[j + (len >> 1)] * tp);
            }
        }
    }
}

void XOR(int a[], int n, int tp) {
    for (int len = 2; len <= n; len <<= 1) {
        int k = (len >> 1);
        for (int i = 0; i < n; i += len) {
            for (int j = i; j < i + k; j ++ ) {
                int ls = a[j], rs = a[j + k];
                a[j] = 1ll * (ls + rs) % mod * tp % mod;
                a[j + k] = 1ll * (ls - rs + mod) % mod * tp % mod;
            }
        }
    }
}

int main() {
    lgn = read(), n = 1 << lgn;
    for (int i = 0; i < n; i ++ ) a[i] = c0[i] = read();
    for (int i = 0; i < n; i ++ ) b[i] = c1[i] = read();
    OR(c0, n, 1), OR(c1, n, 1);
    for (int i = 0; i < n; i ++ ) c0[i] = 1ll * c0[i] * c1[i] % mod;
    OR(c0, n, -1);
    for (int i = 0; i < n; i ++ ) {
        printf("%d ", c0[i]);
        c0[i] = a[i], c1[i] = b[i];
    }
    puts(""), AND(c0, n, 1), AND(c1, n, 1);
    for (int i = 0; i < n; i ++ ) c0[i] = 1ll * c0[i] * c1[i] % mod;
    AND(c0, n, -1);
    for (int i = 0; i < n; i ++ ) {
        printf("%d ", c0[i]);
        c0[i] = a[i], c1[i] = b[i];
    }
    puts(""), XOR(c0, n, 1), XOR(c1, n, 1);
    for (int i = 0; i < n; i ++ ) c0[i] = 1ll * c0[i] * c1[i] % mod;
    XOR(c0, n, 499122177);
    for (int i = 0; i < n; i ++ ) printf("%d ", c0[i]);
    return 0;
}

子集卷积

给定两个长度为 2n2^n（n≤20n \le 20）的序列 f0,f1,⋯ ,f2n−1f_0,f_1,\cdots,f_{2^n-1} 和 b0,b1,⋯ ,b2n−1b_0,b_1,\cdots,b_{2^n-1}，你需要求出一个序列 g0,g1,⋯ ,g2n−1g_0,g_1,\cdots,g_{2^n-1}，其中 hkh_k 满足：

hk=∑i∩j=0, i∪j=kfigjh_k=\sum_{i\cap j=0,~i\cup j=k}f_ig_j

对于 i∪j=ki\cup j=k 这一限制可以直接用 FWT/FMT 解决。

容易发现 i∩j=0i\cap j=0 等价于 ∣i∣+∣j∣=∣i∪j∣|i|+|j|=|i\cup j|，我们引入 占位多项式：

Fi,j={fj∣j∣=i0∣j∣≠iF_{i, j}= \begin{cases}f_j & |j|=i \\ 0 & |j| \neq i\end{cases}

求 Hi,jH_{i, j} 时，可以枚举拼成 jj 的两个集合大小 i1i_1 和 i2i_2 ，我们有：

Hi,j=∑i1+i2=i∑a or bFi1,aGi2,bH_{i, j}=\sum_{i_1+i_2=i} \sum_{a \text { or } b} F_{i_1, a} G_{i_2, b}

也就是：

Hi=∑i1+i2=iFi1∗Gi2H_i=\sum_{i_1+i_2=i} F_{i_1} * G_{i_2}

其中 ∗* 为或卷积，由于 FWT 是线性变换，因此一个 F∗GF*G 在 ∑\sum 后的结果 HH 仍然是满足 FWT 性质的。

因此我们再做 IFWT 还原即可。

「洛谷 P6097」【模板】子集卷积

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> PII;

#define fir first
#define sec second
#define ep emplace
#define eb emplace_back

#define lowbit(x) ((x) & (-(x)))
#define add(a, b) { \
    if (((a) = (a) + (b)) >= mod) (a) -= mod; \
    if ((a) < 0) (a) += mod; \
}

inline int read() {
    int x = 0, f = 1; char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
    for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
    return x * f;
}

const int N = 1048580;
const int mod = 1e9 + 9;

int n, m, a[21][N], b[21][N], h[21][N];

void OR(int a[], int n, int tp) {
    for (int len = 2; len <= n; len <<= 1) {
        for (int i = 0; i < n; i += len) {
            for (int j = i; j < i + (len >> 1); j ++ ) {
                add(a[j + (len >> 1)], a[j] * tp);
            }
        }
    }
}

int main() {
    n = read(), m = 1 << n;
    for (int i = 0; i < m; i ++ ) a[__builtin_popcount(i)][i] = read();
    for (int i = 0; i < m; i ++ ) b[__builtin_popcount(i)][i] = read();
    for (int i = 0; i <= n; i ++ ) OR(a[i], m, 1), OR(b[i], m, 1);
    for (int i = 0; i <= n; i ++ ) {
        for (int j = 0; j <= i; j ++ ) {
            for (int k = 0; k < m; k ++ ) {
                add(h[i][k], 1ll * a[j][k] * b[i - j][k] % mod);
            }
        }
    }
    for (int i = 0; i <= n; i ++ ) OR(h[i], m, -1);
    for (int i = 0; i < m; i ++ ) printf("%d ", h[__builtin_popcount(i)][i]);
    return 0;
}

参考资料：
快速沃尔什变换（FWT）和子集卷积
https://ac.sky390.cn/p/fwt-related/
本文作者
Sky390
发布于
2025-08-22
版权协议
转载或引用本文时请遵守许可协议，注明出处、不得用于商业用途！