InoueMoby's Blog

前言

02-05 组合计数里我们学过容斥原理：用”全部 - 重复”来计算精确值。容斥的本质其实是 Möbius 变换。这篇要把这个想法推广到子集上——对所有 $2^n$ 个子集同时做”前缀和”或”差分”，时间只要 $O(n \cdot 2^n)$ 。

为什么这有用？因为很多计数问题涉及”子集的贡献”。比如：对每个集合 $T$ ，求 $\sum_{S \subseteq T} f(S)$ 。朴素做法是对每个 $T$ 枚举子集， $O(3^n)$ 。Zeta 变换把它加速到 $O(n \cdot 2^n)$ 。

问题的本质

Zeta 变换 = 子集前缀和

给定函数 $f: 2^n \to \mathbb{Z}$ ，Zeta 变换定义：

$g(T) = \sum_{S \subseteq T} f(S)$

就像一维前缀和 $g[i] = \sum_{j \le i} f[j]$ 一样，只是" $\le$ "换成了" $\subseteq$ "。

Möbius 变换 = 子集差分（Zeta 的逆）

给定 $g$ ，求 $f$ 使得 $g(T) = \sum_{S \subseteq T} f(S)$ 。由容斥原理：

$f(S) = \sum_{T \subseteq S} (-1)^{|S|-|T|} g(T)$

为什么能加速？

Zeta 变换的朴素实现是 $O(3^n)$ （枚举 $T$ 和 $S \subseteq T$ ）。但关键观察：我们可以逐位处理。

考虑第 $i$ 个比特。如果 $T$ 的第 $i$ 位是 1，那 $g(T)$ 收到的贡献来自两种 $S$ ：第 $i$ 位是 0 或是 1。我们可以分步累加——先处理第 0 位，再处理第 1 位，依此类推。每步 $O(2^n)$ ，共 $n$ 步，总 $O(n \cdot 2^n)$ 。

追问：为什么逐位处理是正确的？因为 $S \subseteq T$ 等价于”每一位 $S_i \le T_i$ “。对每一位独立做前缀和（0→0 不变，1→0+1 的和），连做 $n$ 次就得到了所有子集的和。这是标准的”SOS DP”（Sum Over Subsets）技巧。

理论 + 代码

高速 Zeta 变换（子集）

#include <vector>
using namespace std;

// 就地变换：f[T] 变为 sum_{S⊆T} f[S]
void subset_zeta(int n, vector<long long>& f) {
    for (int i = 0; i < n; i++)                        // ① 逐位处理
        for (int s = 0; s < (1 << n); s++)
            if (s >> i & 1)
                f[s] += f[s ^ (1 << i)];              // ② 加上翻转第 i 位后的值
}

逐行解析：

① 对每一位 $i$ （从 0 到 $n-1$ ）做一轮扫描。
② 如果 $s$ 的第 $i$ 位是 1，则 $s \oplus (1 \ll i)$ 是 $s$ 去掉第 $i$ 位后的子集。把这个子集的值累加到 $s$ 上。经过 $n$ 轮后， $f[s]$ 就是所有 $S \subseteq s$ 的原始值之和。

模拟表（ $n=3$ ，初始 $f = [3,1,4,1,5,9,2,6]$ ）：

$s$	初始	$i=0$	$i=1$	$i=2$
000	3	3	3	3
001	1	4	4	4
010	4	4	8	8
011	1	5	9	9
100	5	5	5	8
101	9	14	14	18
110	2	2	7	14
111	6	8	15	31

最终 $f[7] = 31 = 3+1+4+1+5+9+2+6$ （所有子集之和）。✓

高速 Möbius 变换（子集逆变换）

// 就地变换：f[T] 从 sum_{S⊆T} f[S] 还原为原始值
void subset_mobius(int n, vector<long long>& f) {
    for (int i = 0; i < n; i++)
        for (int s = 0; s < (1 << n); s++)
            if (s >> i & 1)
                f[s] -= f[s ^ (1 << i)];              // ① 把加号改减号
}

逐行解析：

① 和 Zeta 变换唯一的区别：+= 改为 -=。这就是 Zeta 的逆操作。

上位集合 Zeta 变换

// g[T] = sum_{S⊇T} f[S]
void superset_zeta(int n, vector<long long>& f) {
    for (int i = 0; i < n; i++)
        for (int s = 0; s < (1 << n); s++)
            if (!(s >> i & 1))                         // ① 注意条件取反
                f[s] += f[s | (1 << i)];              // ② 加上包含第 i 位的超集
}

OR 卷积

给定 $A$ 和 $B$ （长度 $2^n$ ），求 $C_U = \sum_{S \cup T = U} A_S \cdot B_T$ 。

vector<long long> or_convolution(int n, vector<long long> A, vector<long long> B) {
    subset_zeta(n, A);                                 // ① Zeta 变换
    subset_zeta(n, B);
    for (int s = 0; s < (1 << n); s++)
        A[s] *= B[s];                                  // ② 逐点相乘
    subset_mobius(n, A);                               // ③ Möbius 逆变换
    return A;
}

逐行解析：

①②③ 类似 FFT：Zeta 变换（类比 DFT）→ 逐点相乘 → Möbius 逆变换（类比 IDFT）。总时间 $O(n \cdot 2^n)$ 。

例题

例题 1：子集和统计

场景： $N$ 种物品，第 $i$ 种的价值为 $v_i$ 。对每个子集 $T \subseteq \{0,\ldots,N-1\}$ ，定义 $f(T) = \sum_{i \in T} v_i$ 。给定 $2^N$ 个值 $g(T)$ ，已知 $g(T) = \sum_{S \subseteq T} f(S)$ 。求所有 $f(T)$ 。

数据范围： $N \le 20$

分析：Möbius 逆变换的直接应用。

代码：

#include <cstdio>
#include <vector>
using namespace std;

void subset_mobius(int n, vector<long long>& f) {
    for (int i = 0; i < n; i++)
        for (int s = 0; s < (1 << n); s++)
            if (s >> i & 1) f[s] -= f[s ^ (1 << i)];
}

int main() {
    int N;
    scanf("%d", &N);
    vector<long long> f(1 << N);
    for (int s = 0; s < (1 << N); s++) scanf("%lld", &f[s]);
    subset_mobius(N, f);                               // ① Möbius 逆变换
    for (int s = 0; s < (1 << N); s++) {
        if (s) printf(" ");
        printf("%lld", f[s]);
    }
    printf("\n");
}

逐行解析：

① 对 $g$ 做 Möbius 逆变换得到 $f$ 。把 Zeta 的 += 改为 -= 即可。

例题 2：OR 卷积——集合合并计数

场景：两组 $2^N$ 个数 $A$ 和 $B$ 。求 $C_U = \sum_{S \cup T = U} A_S \cdot B_T \pmod{998244353}$ 。

数据范围： $N \le 20$

分析：OR 卷积标准模板。

代码：

#include <cstdio>
#include <vector>
using namespace std;
const long long MOD = 998244353;

void subset_zeta(int n, vector<long long>& f) {
    for (int i = 0; i < n; i++)
        for (int s = 0; s < (1 << n); s++)
            if (s >> i & 1) f[s] = (f[s] + f[s ^ (1 << i)]) % MOD;
}
void subset_mobius(int n, vector<long long>& f) {
    for (int i = 0; i < n; i++)
        for (int s = 0; s < (1 << n); s++)
            if (s >> i & 1) f[s] = (f[s] - f[s ^ (1 << i)] + MOD) % MOD;
}

int main() {
    int N;
    scanf("%d", &N);
    vector<long long> A(1 << N), B(1 << N);
    for (int s = 0; s < (1 << N); s++) scanf("%lld", &A[s]);
    for (int s = 0; s < (1 << N); s++) scanf("%lld", &B[s]);

    subset_zeta(N, A);                                 // ① Zeta
    subset_zeta(N, B);
    for (int s = 0; s < (1 << N); s++)
        A[s] = A[s] * B[s] % MOD;                      // ② 逐点相乘
    subset_mobius(N, A);                               // ③ Möbius

    for (int s = 0; s < (1 << N); s++) {
        if (s) printf(" ");
        printf("%lld", A[s]);
    }
    printf("\n");
}

逐行解析：

①②③ Zeta → 逐点乘 → Möbius，类比 FFT/NTT 的三步流程。

例题 3：上位集合贡献

场景： $2^N$ 个值 $f[T]$ 。对每个 $T$ ，求 $g(T) = \sum_{S \supseteq T} f[S]$ 。

数据范围： $N \le 20$

分析：上位集合 Zeta 变换。

代码：

#include <cstdio>
#include <vector>
using namespace std;

void superset_zeta(int n, vector<long long>& f) {
    for (int i = 0; i < n; i++)
        for (int s = 0; s < (1 << n); s++)
            if (!(s >> i & 1))
                f[s] += f[s | (1 << i)];              // ① 第 i 位为 0 → 加上位为 1 的超集
}

int main() {
    int N;
    scanf("%d", &N);
    vector<long long> f(1 << N);
    for (int s = 0; s < (1 << N); s++) scanf("%lld", &f[s]);
    superset_zeta(N, f);
    for (int s = 0; s < (1 << N); s++) {
        if (s) printf(" ");
        printf("%lld", f[s]);
    }
    printf("\n");
}

逐行解析：

① 第 $i$ 位为 0 的集合 $s$ ，加上第 $i$ 位改为 1 的超集 $s | (1 \ll i)$ 的值。处理完所有位后， $f[s]$ 就是所有 $S \supseteq s$ 的原始值之和。

例题 4：位运算计数——AND 卷积

场景：两组 $2^N$ 个数 $A$ 和 $B$ 。求 $C_U = \sum_{S \cap T = U} A_S \cdot B_T \pmod{998244353}$ 。

数据范围： $N \le 20$

分析：AND 卷积用上位集合 Zeta/Möbius 变换。原理与 OR 卷积对称： $S \cap T \supseteq U \iff S \supseteq U$ 且 $T \supseteq U$ 。

代码：

void superset_zeta(int n, vector<long long>& f) {
    for (int i = 0; i < n; i++)
        for (int s = 0; s < (1 << n); s++)
            if (!(s >> i & 1)) f[s] = (f[s] + f[s | (1 << i)]) % MOD;
}
void superset_mobius(int n, vector<long long>& f) {
    for (int i = 0; i < n; i++)
        for (int s = 0; s < (1 << n); s++)
            if (!(s >> i & 1)) f[s] = (f[s] - f[s | (1 << i)] + MOD) % MOD;
}

int main() {
    // 读入 A, B ...
    superset_zeta(N, A);                               // ① 上位集合 Zeta
    superset_zeta(N, B);
    for (int s = 0; s < (1 << N); s++)
        A[s] = A[s] * B[s] % MOD;
    superset_mobius(N, A);                             // ② 上位集合 Möbius
    // 输出 A ...
}

逐行解析：

①② 和 OR 卷积完全对称，只是 Zeta/Möbius 换成了上位集合版本。

参考文献

理论讲义 — AtCoder Algorithm Lectures

ゼータ・メビウス変換（部分集合関係）難易度 4

系列索引

第零章基础工具

第一章搜索技术

第二章数学基础

第三章数据结构

第四章图论

第五章动态规划

第六章贪心

第七章字符串

第八章进阶

Zeta / Möbius 变换

子集上的前缀和——快速计算所有子集的贡献

前言

问题的本质

Zeta 变换 = 子集前缀和

Möbius 变换 = 子集差分（Zeta 的逆）

为什么能加速？

理论 + 代码

高速 Zeta 变换（子集）

高速 Möbius 变换（子集逆变换）

上位集合 Zeta 变换

OR 卷积

例题

例题 1：子集和统计

例题 2：OR 卷积——集合合并计数

例题 3：上位集合贡献

例题 4：位运算计数——AND 卷积

参考文献

系列索引

Zeta / Möbius 变换

$s$	初始	$i=0$	$i=1$	$i=2$
000	3	3	3	3
001	1	4	4	4
010	4	4	8	8
011	1	5	9	9
100	5	5	5	8
101	9	14	14	18
110	2	2	7	14
111	6	8	15	31

$s$	初始	$i=0$	$i=1$	$i=2$
000	3	3	3	3
001	1	4	4	4
010	4	4	8	8
011	1	5	9	9
100	5	5	5	8
101	9	14	14	18
110	2	2	7	14
111	6	8	15	31

$s$	初始	$i=0$	$i=1$	$i=2$
000	3	3	3	3
001	1	4	4	4
010	4	4	8	8
011	1	5	9	9
100	5	5	5	8
101	9	14	14	18
110	2	2	7	14
111	6	8	15	31