SOS DP：从子集求和到位运算优化的核心算法-开发者社区

1. 从“子集求和”到SOS DP：一个被低估的利器

“SOS DP”，第一次听到这个名字，你可能和我当初一样，觉得它神秘又高级。它的全称是“Sum Over Subsets Dynamic Programming”，翻译过来就是“子集和动态规划”。别被这个名字吓到，它本质上解决的是一个非常具体且高频的问题：给定一个数组，如何高效地求出每个元素的所有子集（或超集）的某种聚合值（通常是和）？

听起来有点绕？我们直接看一个最经典的场景。假设你有一个长度为n的数组A，数组的索引从0到n-1。现在，对于每一个索引i（0 <= i < n），我们想要求出所有满足j & i == j的索引j所对应的A[j]之和。这里的&是按位与操作。换句话说，j是i的二进制表示下的一个子集（j的二进制位为1的地方，i的对应位也必须为1）。暴力枚举所有j的时间复杂度是O(3^n)，这在n达到20（即数组长度约100万）时是完全不可接受的。而SOS DP能在O(n * 2^n)的时间内优雅地解决它，当n=20时，这大约是20 * 2^20 ≈ 2000万次操作，完全在可接受范围内。

我第一次在竞赛中遇到它，是在处理一个关于“位掩码”和“集合贡献”的问题上。当时我写了一个O(3^n)的暴力，理所当然地超时了。看了题解后，SOS DP的简洁和高效让我印象深刻。它不像某些复杂的线段树或平衡树那样需要维护一大堆状态，它的核心思想异常清晰，代码也极其简短，但威力巨大。掌握了它，你就能在涉及子集枚举、高维前缀和、快速莫比乌斯变换（FMT）等一系列问题上，拥有降维打击的能力。今天，我就带你彻底拆解这个“一分钟”就能理解，但足以让你在算法工具箱里多一件神兵的技巧。

2. SOS DP的核心思想：从暴力到优雅的维度折叠

要理解SOS DP，我们必须先彻底理解它要解决的问题，以及暴力解法为什么慢。我们沿用之前的定义：有一个长度为2^n的数组F[mask]，其中mask是一个n位的二进制数（从0到2^n - 1）。我们想要求一个新的数组SOS[mask]，它等于所有满足submask & mask == submask的F[submask]之和。也就是说，SOS[mask]是mask的所有子集的F值之和。

2.1 暴力解法的瓶颈：指数级的枚举

最直接的想法是对于每一个mask，枚举所有可能的submask。如何枚举一个集合的所有子集？一个经典的技巧是利用位运算：submask = (submask - 1) & mask。这个循环会精确地枚举mask的所有子集（包括0和mask本身）。伪代码如下：

for (int mask = 0; mask < (1 << n); mask++) { SOS[mask] = 0; for (int submask = mask; submask > 0; submask = (submask - 1) & mask) { SOS[mask] += F[submask]; } // 不要忘记空集 submask = 0 SOS[mask] += F[0]; }

我们来分析一下这个算法的时间复杂度。外层循环是O(2^n)。内层循环对于每个mask，枚举了它的所有子集。一个大小为k（即二进制中有k个1）的集合，其子集数量是2^k。所有mask的子集数量总和是多少呢？我们可以从每个元素的角度考虑：对于每一个二进制位，它在所有mask的子集中出现的模式是复杂的。一个经典的结论是，这个二重循环的总迭代次数是3^n。因为对于每一个二进制位，它在mask和submask中有三种状态：(0,0), (1,0), (1,1)。所以总状态数是3^n。当n=20时，3^20 ≈ 34亿，这显然太慢了。

2.2 SOS DP的降维打击：按位递推

SOS DP的精妙之处在于，它不直接去计算每个mask的最终答案，而是通过一种“维度叠加”或“前缀和”的思想，逐步构建出答案。

我们可以把mask看作一个n维的布尔向量。SOS[mask]可以理解为在一个n维空间里，求一个“前缀立方体”的和。想象一个n维的超立方体，每个顶点对应一个mask，顶点的值就是F[mask]。SOS[mask]就是求从原点(0,0,...,0)到点mask所构成的“超长方体”内所有顶点的值之和。

SOS DP的做法是：我们一维一维地来处理。定义dp[i][mask]表示：只考虑前i个二进制位（即第0位到第i-1位）时，mask的所有子集的F值之和。这里“只考虑前i位”的意思是，对于超过i的高位，我们要求submask必须和mask完全一致；而对于低i位，则要求submask是mask的子集。

初始化：当i=0时，我们还没有考虑任何位。此时，dp[0][mask] = F[mask]。因为如果不考虑任何位的子集关系，那么唯一的“子集”就是它自己。

状态转移：现在，我们要从dp[i][mask]推导出dp[i+1][mask]，也就是引入第i位。

情况1：如果mask的第i位是0。那么，对于submask来说，它的第i位也必须是0（因为子集的对应位不能是1）。所以，引入第i位并没有带来新的选择，状态不变：dp[i+1][mask] = dp[i][mask]。
情况2：如果mask的第i位是1。那么，submask的第i位可以是0或1。
- 如果submask的第i位是1，那么这部分的贡献已经包含在dp[i][mask]里了（因为dp[i][mask]允许低i位是子集，而第i位是1正好匹配）。
- 如果submask的第i位是0，那么我们需要找到一个状态，这个状态在低i位是mask的子集，并且第i位是0。这个状态就是mask ^ (1 << i)（即把mask的第i位翻转为0）。而这个状态的dp值，在上一轮dp[i]中已经计算好了，就是dp[i][mask ^ (1 << i)]。

因此，状态转移方程为：dp[i+1][mask] = dp[i][mask]，如果mask的第i位是0。dp[i+1][mask] = dp[i][mask] + dp[i][mask ^ (1 << i)]，如果mask的第i位是1。

2.3 空间优化：滚动数组的魔法

我们注意到，dp[i+1][mask]只依赖于dp[i][mask]和dp[i][mask ^ (1 << i)]。这意味着我们可以像很多DP问题一样，使用滚动数组来优化空间，只保留一个一维数组SOS[mask]，并就地更新。

最终的算法伪代码如下：

// 初始化：SOS[mask] = F[mask] for (int i = 0; i < (1 << n); ++i) { SOS[i] = F[i]; } // 核心递推：按位处理 for (int bit = 0; bit < n; ++bit) { for (int mask = 0; mask < (1 << n); ++mask) { if (mask & (1 << bit)) { // 只处理第bit位为1的mask SOS[mask] += SOS[mask ^ (1 << bit)]; } } } // 循环结束后，SOS[mask] 即为所求

为什么内层循环可以正序遍历？这是一个关键细节。因为SOS[mask]要加上的是SOS[mask ^ (1 << bit)]，而这个mask ^ (1 << bit)是把当前mask的某一位从1变成0，它的数值是小于当前mask的。在正序循环中，当我们处理到mask时，SOS[mask ^ (1 << bit)]已经被本轮的bit更新过了吗？我们需要仔细分析。

实际上，mask ^ (1 << bit)在第bit位是0。根据我们的转移条件if (mask & (1 << bit))，这个更小的mask在本轮循环中不会被更新（因为它的第bit位是0）。所以，SOS[mask ^ (1 << bit)]在本轮循环中保持的是上一轮（即处理完bit-1位）之后的值。而这正是我们递推公式所需要的dp[i][mask ^ (1 << bit)]。因此，正序循环是完全正确的，而且是最自然的写法。

注意：这里有一个非常容易混淆的点。有些教程或代码会使用逆序循环for (int mask = (1<<n)-1; mask >=0; mask--)。逆序循环通常是用于另一种类型的DP（例如背包问题），防止同一轮的状态被重复使用。在标准的SOS DP中，我们依赖的是“未被本轮更新的、更小的状态”，所以正序是正确且简洁的。如果你看到逆序，那可能是在处理“超集”问题，或者是一种等价的但思考角度不同的写法。作为初学者，牢牢掌握正序这个版本即可。

时间复杂度清晰明了：外层循环n次，内层循环2^n次，每次操作是O(1)，总复杂度O(n * 2^n)。空间复杂度O(2^n)。

3. 不止于求和：SOS DP的变体与应用场景

SOS DP之所以强大，是因为“求和”这个操作只是聚合函数的一种。它可以推广到任何满足结合律和交换律的运算上，比如求最大值（Max）、最小值（Min）、按位与（AND）、按位或（OR），甚至是计数。只要你能定义清楚“子集的贡献如何聚合”，SOS DP的框架就能适用。

3.1 求子集最大值（Max Over Subsets）

这是一个非常实用的变体。假设F[mask]表示集合mask的某个权值，我们想要求对于每个mask，其所有子集权值的最大值。初始化SOS[mask] = F[mask]，然后将转移方程中的加法+=替换为取最大值max=即可。

for (int i = 0; i < (1 << n); ++i) SOS[i] = F[i]; for (int bit = 0; bit < n; ++bit) { for (int mask = 0; mask < (1 << n); ++mask) { if (mask & (1 << bit)) { SOS[mask] = max(SOS[mask], SOS[mask ^ (1 << bit)]); } } }

这个技巧在解决一些“最优配对”问题中特别有用。例如，有n个物品，每个物品有一个权值，你可以选择若干个物品组成一个集合，但集合内某些物品不能共存（用冲突图表示）。我们可以预处理出所有合法集合（团）的权值，然后对于每个集合mask，求其所有子集中合法集合的最大权值。这常常是解决某些NP难问题的状压DP的关键优化步骤。

3.2 超集问题（Superset Sum）

我们刚才解决的是子集和问题。有时我们需要求超集和：对于每个mask，求所有包含它的集合（即超集，满足superset & mask == mask）的F值之和。

聪明的你已经发现了，这其实是子集问题的一个“对称”版本。有两种思考方式：

重新定义位的关系：把“1”看作“必须存在”，那么超集就是原集合的子集。我们可以定义一个新的数组G[mask] = F[~mask]（按位取反），然后对G做子集SOS DP，最后结果再映射回来。但取反操作要注意n的位数范围。
更直观的方法：修改DP方向。在子集DP中，我们从低位向高位处理，当mask的某位为1时，我们去加一个该位为0的状态（即一个更小的子集）。对于超集，我们需要当mask的某位为0时，去加一个该位为1的状态（即一个更大的超集）。代码只需稍作修改：

// 超集和 SOS Superset for (int i = 0; i < (1 << n); ++i) SOS[i] = F[i]; for (int bit = 0; bit < n; ++bit) { for (int mask = 0; mask < (1 << n); ++mask) { if (!(mask & (1 << bit))) { // 注意：这里判断第bit位为0 SOS[mask] += SOS[mask | (1 << bit)]; // 加上该位为1的超集 } } }

3.3 经典应用场景：位运算卷积与集合计数

SOS DP是解决一系列位运算相关计数问题的核心。举一个经典例子：

问题：给定两个数组A[mask]和B[mask]（mask范围[0, 2^n)），定义它们的“子集卷积”C[mask]为：C[mask] = sum over all (i, j) such that i | j = mask and i & j = 0 of A[i] * B[j]。

直接计算是O(3^n)。利用SOS DP，我们可以将其优化到O(n^2 * 2^n)。思路是引入集合的大小（popcount）。定义A_pc[popcount][mask]为所有大小为popcount的集合mask的A值。然后对每个popcount维度，分别对A_pc和B_pc做SOS DP（子集和）。接着，对于每个mask，C[mask]就是sum over k (SOS_A[k][mask] * SOS_B[popcount(mask)-k][mask])的某种组合（需满足交集为空的条件，这通过SOS DP后的容斥或特殊处理实现）。这就是“快速子集卷积”（Fast Subset Convolution）的基础。许多涉及“划分”、“配对”、“不交并”的计数问题，最终都能归约到这类卷积上。

另一个常见场景是“枚举子集再枚举子集”的优化。比如一个问题需要你对于每个集合i，枚举它的所有子集j，然后对于每个j又要做某种计算。双重循环就是O(3^n)。如果你发现内层对j的计算只依赖于F[j]且是一个可以叠加的操作（如求和、最值），那么就可以预先用SOS DP计算出对于每个i，其所有子集j的F[j]聚合值SOS[i]。这样就把O(3^n)优化成了O(n * 2^n)。这是竞赛中非常关键的优化技巧。

4. 实战演练：从理论到代码的避坑指南

光说不练假把式。我们用一个具体的题目来演示SOS DP的完整应用，并分享我在实战中踩过的坑。

例题（灵感来源于Codeforces 1208F）：给定一个数组a，长度最多1e6，元素值范围[0, 2^21)。求一对下标(i, j, k)，满足i < j < k，使得(a[i] | (a[j] & a[k]))的值最大。其中|是按位或，&是按位与。

分析：直接三重循环枚举i, j, k显然不行。我们需要转换视角。注意到a[j] & a[k]的结果是一个数，记为x。那么我们要最大化a[i] | x。对于一个固定的x，我们希望找一个a[i]，使得a[i] | x尽可能大。理想情况下，如果存在一个a[i]包含了x的所有位，那么结果就是x本身（如果a[i]有额外的位，结果会更大）。更一般地，我们希望a[i]能补上x中缺失的高位1。

一个关键观察是，我们可以从高位到低位贪心地构造答案。假设我们想知道，是否存在一个a[i]和某个x，使得最终结果的最高位（比如第20位）能为1。这意味着，存在a[i]和x，满足(a[i] | x)的第20位是1。这又等价于：a[i]的第20位是1或者x的第20位是1。

那么，x从哪里来？x = a[j] & a[k]。所以x的第20位是1，要求a[j]和a[k]的第20位都是1。

于是，问题转化为：我们需要快速知道，对于给定的一个目标掩码mask，是否存在两个（或一个）元素，它们的按位与是mask的超集？或者，是否存在一个元素，它本身是mask的超集？

这里，SOS DP就可以登场了。我们用它来维护“超集信息”。

解题步骤：

预处理超集存在性：我们用一个数组sup[mask]来记录，数组a中是否存在某个元素，它是mask的超集（即(a[i] & mask) == mask）。这可以用SOS DP（超集版本）来求“超集的最大出现次数”或“超集是否存在”。更实用的是，我们记录每个mask的“超集中，值最大的两个元素的下标”。因为我们需要a[j]和a[k]两个数。
定义DP状态：设dp[mask]为一个pair，表示在数组a的所有元素中，是mask的超集（即包含mask所有1的位）的、值最大的两个元素的下标（或值）。我们可以通过SOS DP来合并信息：如果mask是submask的超集，那么mask的超集也一定是submask的超集。所以我们可以从低位向高位递推，不断用超集的信息来更新子集的信息（注意这里是反向的，我们需要的是对于每个mask，知道它的超集的信息，所以是超集DP）。
贪心构造答案：从最高位（比如第20位）开始向下尝试。设当前答案为ans = 0。对于第bit位：
- 我们想知道，如果令答案的这一位为1（即candidate = ans | (1 << bit)），是否可行。
- “可行”意味着：存在两个下标j, k，使得(a[j] & a[k])是candidate的超集？不完全是。我们需要a[i] | (a[j] & a[k])包含candidate。更精确的检查是：存在i, j, k，使得(a[i] | (a[j] & a[k])) & candidate == candidate。这等价于candidate的每一位1，都必须被a[i]或(a[j] & a[k])所覆盖。
- 一个实用的贪心检查方法是：我们固定x = a[j] & a[k]。那么条件变为：存在x和a[i]，使得(a[i] | x) & candidate == candidate。即candidate中那些x没有覆盖到的1位，必须由a[i]来覆盖。
- 因此，我们可以枚举candidate的子集作为x（因为x只需要覆盖candidate的一部分位）。对于每一个这样的x，我们需要检查： a. 是否存在两个不同的元素，它们的按位与是x的超集（即>= x在集合包含意义上）？这可以通过我们预处理的dp[x]来判断，它存储了是x的超集的最大两个元素。 b. 是否存在另一个元素a[i]，它覆盖了candidate中除去x所覆盖的位之后剩下的位？即a[i]必须是(candidate ^ x)的超集（^是按位异或，得到的是candidate有而x没有的位）。这也可以通过查询dp[candidate ^ x]来判断。
- 如果对于某个x（它是candidate的子集），条件a和b同时满足，并且dp[x]和dp[candidate ^ x]提供的元素下标不冲突（总共至少三个不同的下标），那么这个candidate就是可行的，我们可以将ans设置为candidate。

SOS DP预处理部分的核心代码：

const int MAXB = 21; // 值域位数 const int MAXM = 1 << MAXB; pair<int, int> dp[MAXM]; // 存储（最大值，次大值）的下标或值 // 初始化：每个mask只记录自己对应的那个数（如果存在） for (int i = 0; i < n; ++i) { int val = a[i]; // 更新 dp[val]，维护最大的两个值 if (dp[val].first == -1) dp[val].first = i; else if (dp[val].second == -1 || a[dp[val].second] < a[i]) { if (a[dp[val].first] < a[i]) { dp[val].second = dp[val].first; dp[val].first = i; } else { dp[val].second = i; } } } // SOS DP（超集版本），用于合并信息：从子集更新超集 // 这里我们想要的是：对于每个mask，知道它的所有超集中，最大的两个值是什么。 // 我们可以用超集DP：如果 sup 是 sub 的超集，那么 sup 的信息应该包含 sub 的信息。 // 标准超集DP是：for mask， if (mask位为0) dp[mask] += dp[mask|1<<bit]; // 但这里我们是合并最大值，所以是 dp[mask] = merge(dp[mask], dp[mask|1<<bit]) for (int bit = 0; bit < MAXB; ++bit) { for (int mask = 0; mask < MAXM; ++mask) { if (!(mask & (1 << bit))) { // 合并 dp[mask] 和 dp[mask | (1 << bit)] int super = mask | (1 << bit); // 将 dp[super] 中的最大和次大值，尝试更新到 dp[mask] 中 // 这里需要一个 merge 函数，比较繁琐，但逻辑是清晰的 merge(dp[mask], dp[super].first); merge(dp[mask], dp[super].second); } } } // 经过这个DP后，dp[mask] 中存储的就是所有是 mask 的超集的元素中，值最大的两个。

避坑经验：

下标与值的混淆：在dp数组中，我们存储下标是为了最后判断i, j, k是否互不相同。但在合并最大值时，比较的是a[下标]的值。代码中很容易直接比较下标，导致逻辑错误。务必清晰区分“存储的是下标”和“比较的是值”。
空集与初始化：dp[0]表示所有数（因为任何数都是0的超集）。初始化时，对于数组a中不存在的mask，dp[mask]应设置为一个无效状态（如(-1, -1)）。在合并时，要小心处理无效状态。
贪心检查的复杂度：枚举candidate的所有子集x，最坏是O(2^popcount(candidate))，在popcount较大时可能很慢。但在这个问题中，我们是从高位向低位贪心，candidate的位数是逐步增加的，并且一旦某位确定为1，后续检查的candidate会包含它。实际上，由于值域只有2^21，且贪心过程剪枝很多，这个枚举子集的操作是可行的。但在更复杂的问题中，可能需要借助DP或折半枚举来优化。
内存与时间：MAXM = 1 << 21 = 2,097,152，存储pair数组是可行的（约16MB）。SOS DP的循环是21 * 2^21 ≈ 4400万次，每次循环包含几次内存访问和比较，在现代CPU上可以在1秒内完成。

通过这个例子，你应该能感受到SOS DP如何作为一个基础组件，嵌入到一个更复杂的贪心或DP框架中，高效地解决集合查询问题。它把看似需要O(3^n)枚举的操作，压缩到了O(n * 2^n)，这是质的飞跃。

5. 举一反三：SOS DP与其他算法的联系

理解SOS DP不能孤立地看，它和很多其他算法思想有着深刻的联系。明白这些联系，能帮助你更灵活地运用它。

5.1 与高维前缀和（High-Dimensional Prefix Sum）的等价性

这是最直接的联系。SOS DP本质上就是计算一个n维布尔立方体上的前缀和。每一维只有0和1两种状态。dp[i][mask]可以看作是已经对前i维做了前缀和。最终SOS[mask]就是点mask的n维前缀和。因此，所有高维前缀和的技巧，比如容斥原理求任意矩形区域和、差分数组等，在SOS DP中都有对应的形式。例如，求所有超集的和，就相当于一个“后缀和”。

5.2 与快速莫比乌斯变换（FMT）和快速沃尔什变换（FWT）

这是SOS DP在理论上的升华。对于子集卷积，我们提到了需要结合集合大小。更一般地，SOS DP是快速莫比乌斯变换（FMT）在集合幂集上的特例（用于求子集和）。而FMT、快速沃尔什变换（FWT）是解决一类广义的“卷积”问题的工具，包括按位与卷积、按位或卷积、按位异或卷积等。

按位或卷积：C[mask] = sum_{i | j = mask} A[i] * B[j]。它的快速算法（FWT_or）的核心步骤，和SOS DP的代码几乎一模一样！是的，你没看错。FWT_or的正变换就是做一遍SOS DP（子集和）。逆变换则是一个逆过程（包含减法）。所以，学会了SOS DP，你就已经掌握了FWT_or的一半。
按位与卷积：对应的是超集和SOS DP。
按位异或卷积：对应的是FWT_xor，它的变换公式不同，但思想类似，也是通过分治按位处理。

理解这个联系后，当你看到一个问题涉及集合的卷积时，你应该立刻联想到SOS DP/FWT。

5.3 与动态规划优化（DP over Subsets）

在很多状压DP问题中，状态转移需要枚举子集。例如，经典的旅行商问题（TSP）的DP解法是dp[mask][i]表示访问过集合mask，最后停在城市i的最短路径。转移时需要枚举mask中不是i的城市j。这里的子集枚举是O(3^n)。如果转移方程可以改写为只依赖于dp[mask]的子集和某种预处理的值，那么就有可能用SOS DP来优化，将复杂度从O(3^n)降为O(n * 2^n)。这通常需要问题本身具有很好的可分解性。

例如，有些计数DP需要计算：dp[mask] = sum_{submask ⊆ mask} f(submask) * g(mask ^ submask)。这显然是一个子集卷积，可以用前面提到的“快速子集卷积”优化。

5.4 实战中的选择：SOS DP vs. 枚举子集

虽然SOS DP很强大，但并不是所有需要枚举子集的地方都要用它。你需要权衡：

数据规模：n有多大？如果n <= 16，3^n ≈ 4300万，可能勉强能过（如果操作简单）。如果n=20，3^n=34亿，基本必须用SOS DP或类似优化。如果n=25，2^n=3300万，n*2^n=8亿，可能就需要更精妙的优化或剪枝了。
预处理 vs. 在线查询：如果你需要对同一个数组F进行很多次不同的子集查询，那么预处理一个SOS数组是划算的。如果只需要查一次，或者每次查询的“聚合函数”都不同（比如一次求和、一次求最大值），那么直接枚举子集可能更简单，代码更清晰。
聚合函数的性质：SOS DP要求聚合操作（如加、乘、max、min、and、or）满足结合律和交换律。对于不满足的操作（比如求子集的中位数），SOS DP就无能为力了。