我的算法书 - SOS DP：子集和动态规划

一句话算法

SOS DP 就是在二进制集合上做高维前缀和：按位把子集或超集的贡献一层层累加起来。

问题模型

给定 $n$ 个元素的全集。每个集合用一个二进制 mask 表示，数组 $A[mask]$ 存储这个集合的权值。

常见查询有两类：

对每个 mask，求它所有子集的权值和：

$F[mask]=\sum_{sub\subseteq mask} A[sub]$
对每个 mask，求它所有超集的权值和：

$G[mask]=\sum_{sup\supseteq mask} A[sup]$

如果对每个 mask 暴力枚举子集，总复杂度是 $O(3^n)$ 。SOS DP 可以把它优化到：

O(n2^n)

核心直觉

普通一维前缀和是：

prefix[i] = a[0] + a[1] + ... + a[i]

SOS DP 可以理解成“布尔格上的前缀和”。

以子集和为例，mask = 1011 的所有子集只能在 mask 为 1 的位置自由选择，其余位置必须是 0。

mask = 1011
sub  = ?0??    只能在 1 的位上选 0 或 1

关键做法是：不要一次性枚举所有子集，而是按二进制位逐层允许变化。处理完第 i 位后，数组中已经包含了“前 i 位可自由变化”的部分答案。

子集和

目标是：

F[mask]=\sum_{sub\subseteq mask} A[sub]

先让：

F[mask]=A[mask]

然后枚举每一位 bit。如果 mask 的这一位是 1，那么 mask 的子集可以分成两类：

这一位取 1：已经在 F[mask] 中；
这一位取 0：对应 F[mask ^ (1<<bit)]。

所以转移是：

F[mask]\leftarrow F[mask]+F[mask\oplus 2^{bit}]

条件是 mask 的第 bit 位为 1。

超集和

目标是：

G[mask]=\sum_{sup\supseteq mask} A[sup]

先让：

G[mask]=A[mask]

枚举每一位 bit。如果 mask 的这一位是 0，那么 mask 的超集可以分成两类：

这一位仍取 0：已经在 G[mask] 中；
这一位变成 1：对应 G[mask ^ (1<<bit)]。

所以转移是：

G[mask]\leftarrow G[mask]+G[mask\oplus 2^{bit}]

条件是 mask 的第 bit 位为 0。

算法步骤

子集和

读入 $n$ 和长度为 $2^n$ 的数组 $A$ 。
复制 F = A。
枚举每一位 bit = 0..n-1。
枚举所有 mask。
如果 mask 包含这一位，就把去掉这一位后的结果加过来。

超集和

读入 $n$ 和长度为 $2^n$ 的数组 $A$ 。
复制 G = A。
枚举每一位 bit = 0..n-1。
枚举所有 mask。
如果 mask 不包含这一位，就把补上这一位后的结果加过来。

算法证明

以子集和为例。

关键不变量： 处理完前 $k$ 个二进制位后，F[mask] 等于所有满足下面条件的 sub 的权值和：

高于第 $k$ 位的位置必须和 mask 完全相同；
前 $k$ 位可以在 mask 的限制下自由变成 0。

初始时还没有处理任何位，只有 sub=mask，所以 F[mask]=A[mask] 正确。

处理第 bit 位时：

如果 mask 这一位是 0，它的子集这一位也只能是 0，不需要合并。
如果 mask 这一位是 1，子集这一位可以是 1 或 0。取 1 的部分已经在 F[mask]，取 0 的部分正好在 F[mask ^ (1<<bit)]。

两部分互不重叠，合并后正好覆盖当前位允许变化后的所有子集。

所有位处理完后，每一位都已经允许变化，因此 F[mask] 就是所有 sub ⊆ mask 的权值和。

超集和同理，只是把“有 1 的位可以变 0”换成“有 0 的位可以变 1”。

复杂度分析

设全集大小为 $n$ ，mask 总数为 $2^n$ 。

子集和时间复杂度： $O(n2^n)$ 。
超集和时间复杂度： $O(n2^n)$ 。
空间复杂度： $O(2^n)$ 。

通常 $n\le 20$ 时比较常见。

代码实现

子集和模板

cpp

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    int limit = 1 << n;
    vector<long long> f(limit);
    for (int mask = 0; mask < limit; ++mask) {
        cin >> f[mask];
    }

    // f[mask] = sum of original f[sub] for every sub ⊆ mask.
    for (int bit = 0; bit < n; ++bit) {
        for (int mask = 0; mask < limit; ++mask) {
            if (mask & (1 << bit)) {
                f[mask] += f[mask ^ (1 << bit)];
            }
        }
    }

    for (int mask = 0; mask < limit; ++mask) {
        if (mask) cout << ' ';
        cout << f[mask];
    }
    cout << '\n';

    return 0;
}

超集和模板

cpp

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    int limit = 1 << n;
    vector<long long> f(limit);
    for (int mask = 0; mask < limit; ++mask) {
        cin >> f[mask];
    }

    // f[mask] = sum of original f[sup] for every sup ⊇ mask.
    for (int bit = 0; bit < n; ++bit) {
        for (int mask = 0; mask < limit; ++mask) {
            if ((mask & (1 << bit)) == 0) {
                f[mask] += f[mask ^ (1 << bit)];
            }
        }
    }

    for (int mask = 0; mask < limit; ++mask) {
        if (mask) cout << ' ';
        cout << f[mask];
    }
    cout << '\n';

    return 0;
}

测试用例

输入数组按 mask 从 0 到 2^n-1 给出。

子集和

输入：

3
1 2 3 4 5 6 7 8

输出：

1 3 4 10 6 14 16 36

解释：mask=7(111) 的子集是所有 mask，所以结果为：

1+2+3+4+5+6+7+8=36

超集和

同样输入：

3
1 2 3 4 5 6 7 8

输出：

36 20 22 12 26 14 15 8

解释：mask=0(000) 的超集是所有 mask，所以结果为 36；mask=7(111) 的超集只有自己，所以结果为 8。

应用分类详解

SOS DP 的本质是在所有二进制集合上批量统计“子集贡献”或“超集贡献”。看到题目要求对很多 mask 重复统计子集/超集时，就应该考虑它。

一、子集贡献统计

典型模式： 对每个集合，统计它所有子集的信息。

识别信号： 题面出现“所有子集”“sub ⊆ mask”“枚举子状态会超时”。

核心建模： 原始权值放在 A[sub]，用子集和得到每个 mask 的总贡献。

应用场景	经典题目	核心思路
子集频次统计	Codeforces 383E	把字符串/集合映射为 mask 后统计子集贡献
集合包含关系计数	通用模型	对每个 mask 查询被它包含的集合数量

二、超集贡献统计

典型模式： 对每个集合，统计包含它的所有集合的信息。

识别信号： 题面出现“所有超集”“sup ⊇ mask”“与补集匹配”。

核心建模： 原始权值放在 A[sup]，用超集和得到每个 mask 的总贡献。

应用场景	经典题目	核心思路
兼容 mask 查询	Codeforces 165E	查询是否存在与当前数按位不冲突的数
AND 为 0 的配对	Codeforces 449D	用补集和统计可配对集合

三、按位包含关系优化

典型模式： 原本要枚举 sub = mask; sub; sub = (sub-1)&mask，但每个 mask 都要做一次。

识别信号： 总复杂度接近 $O(3^n)$ 。

核心建模： 把“每个 mask 枚举所有子集”改成“每一位做一次合并”。

应用场景	经典题目	核心思路
子集 DP 预处理	状压 DP 辅助	批量得到所有子集和
位运算卷积基础	FWT 前置知识	理解集合维度上的信息流

经典例题

1. Codeforces 165E

给定若干数，对每个数找一个与它按位与为 0 的数。可以对出现过的 mask 做超集 DP，在补集上查询。

2. Codeforces 449D

统计若干数中按位与为 0 的子集数量。核心是用 SOS DP 统计每个 mask 的超集出现次数。

3. Codeforces 383E

把字符串字符集合压成 mask，使用 SOS DP 统计子集/补集贡献，是 SOS DP 的经典练习题。

参考

本目录旧草稿：草稿1.md、草稿3.md、草稿gemini.md
前置章节：dynamic_programming/binary_state/index.md