1. 从“子集求和”到SOS DP一个被低估的利器“SOS DP”第一次听到这个名字你可能和我当初一样觉得它神秘又高级。它的全称是“Sum Over Subsets Dynamic Programming”翻译过来就是“子集和动态规划”。别被这个名字吓到它本质上解决的是一个非常具体且高频的问题给定一个数组如何高效地求出每个元素的所有子集或超集的某种聚合值通常是和听起来有点绕我们直接看一个最经典的场景。假设你有一个长度为n的数组A数组的索引从0到n-1。现在对于每一个索引i0 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)的时间内优雅地解决它当n20时这大约是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。当n20时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的子集。初始化当i0时我们还没有考虑任何位。此时dp[0][mask] F[mask]。因为如果不考虑任何位的子集关系那么唯一的“子集”就是它自己。状态转移现在我们要从dp[i][mask]推导出dp[i1][mask]也就是引入第i位。情况1如果mask的第i位是0。那么对于submask来说它的第i位也必须是0因为子集的对应位不能是1。所以引入第i位并没有带来新的选择状态不变dp[i1][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[i1][mask] dp[i][mask]如果mask的第i位是0。dp[i1][mask] dp[i][mask] dp[i][mask ^ (1 i)]如果mask的第i位是1。2.3 空间优化滚动数组的魔法我们注意到dp[i1][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 (1n)-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子集和。接着对于每个maskC[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; pairint, 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|1bit]; // 但这里我们是合并最大值所以是 dp[mask] merge(dp[mask], dp[mask|1bit]) 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中不存在的maskdp[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 163^n ≈ 4300万可能勉强能过如果操作简单。如果n203^n34亿基本必须用SOS DP或类似优化。如果n252^n3300万n*2^n8亿可能就需要更精妙的优化或剪枝了。预处理 vs. 在线查询如果你需要对同一个数组F进行很多次不同的子集查询那么预处理一个SOS数组是划算的。如果只需要查一次或者每次查询的“聚合函数”都不同比如一次求和、一次求最大值那么直接枚举子集可能更简单代码更清晰。聚合函数的性质SOS DP要求聚合操作如加、乘、max、min、and、or满足结合律和交换律。对于不满足的操作比如求子集的中位数SOS DP就无能为力了。我的个人经验是在竞赛中一旦n达到18或20并且问题涉及到“所有子集的某种聚合”SOS DP几乎总是正解的一部分。平时多积累它的各种变体和应用场景比赛时才能快速识别并套用。最后再分享一个调试小技巧当实现SOS DP时可以用小数据n3或4暴力枚举所有子集计算出正确结果然后与你的SOS DP结果对比。这样可以快速验证你的DP方向子集/超集、循环顺序、聚合操作是否正确。对于像“维护最大两个值”这类复杂状态单元测试尤其重要。