1. 项目概述什么是SOS DP以及为什么你需要它如果你在刷题或者研究算法时被“子集求和”、“超集求和”这类问题卡住或者看到“动态规划状态压缩”的标签就感到头疼那么“SOS DP”这个技巧很可能就是你一直在找的那把钥匙。我第一次接触这个概念是在解决一个看似复杂的计数问题时常规的枚举子集方法直接超时直到我发现了SOS DP才真正体会到什么叫“降维打击”。它不是什么全新的算法而是基于动态规划和状态压缩的一种极其巧妙的优化思想能将某些问题的时间复杂度从恐怖的 O(3^N) 或 O(N * 2^N) 优化到优雅的 O(N * 2^N)。这里的N通常指状态压缩后的二进制位数比如一个集合有20个元素2^N就是一百多万O(N * 2^N)的算法是完全可行的而O(3^N)则是天文数字。简单来说SOS DP 解决的核心问题是给定一个长度为 2^N 的数组 F[mask]对于每一个掩码mask我们需要快速求出所有它的子集或超集的某种聚合值通常是和。这里的“mask”就是一个N位的二进制数每一位代表一个元素是否在集合中。例如mask (1011)_2 表示第0、1、3号元素在集合中假设从右往左编号。它的子集就是那些二进制位上1是它的子集的掩码比如(0011)_2, (1001)_2, (0001)_2等。为什么这个问题重要因为它在许多场景下是瓶颈操作。比如在一个有N种技能的游戏中计算拥有特定技能组合mask的玩家数量或者在图论中处理点集mask的某些属性又或者在容斥原理、快速莫比乌斯变换FMT、快速沃尔什变换FWT中都能看到它的身影。掌握了SOS DP你就掌握了一种处理“集合关系”的高效武器。2. SOS DP的核心思想与暴力解法的局限在深入代码之前我们必须先理解我们想要优化什么以及为什么暴力解法行不通。这样你才能深刻体会到SOS DP的精妙之处。2.1 问题定义与暴力枚举假设我们有一个数组A其下标从0到 (2^N - 1)。A[mask]可以理解为拥有“mask”这个集合的某种权值。现在我们定义一个新的数组F[mask]F[mask] 所有满足submask mask submask的A[submask]之和。换句话说F[mask]是mask的所有子集的权值之和。最直接的暴力做法是什么对于每一个mask我们枚举所有可能的submask并检查它是否是mask的子集。枚举所有子集有一个经典的技巧for(int submask mask; submask 0; submask (submask - 1) mask)。这个循环会精确地枚举出mask的所有非空子集。如果加上0就需要额外处理。那么计算整个F数组的时间复杂度是多少对于每个mask它平均有 2^(popcount(mask)) 个子集popcount是二进制中1的个数。所有mask的子集数量总和经过计算正好是 3^N。这是一个组合数学的结论对于每个元素它在mask和submask中有三种状态在mask中不在submask中在mask中且在submask中不在mask中。因此暴力算法的时间复杂度是O(3^N)。当 N20 时3^20 约等于 34.9亿这显然是不可接受的。而 2^20 约等于 100万N * 2^N 约等于 2000万这才是我们算法可以努力的目标。SOS DP 正是实现了 O(N * 2^N) 的复杂度。2.2 SOS DP 的灵感来源按位动态规划SOS DP 的全称是 “Sum Over Subsets Dynamic Programming”。它的核心洞察是我们不一次性考虑整个掩码而是逐位bit地进行动态规划。想象一下我们要计算F[mask]。我们可以这样思考过程初始时F[mask]只包含它自身的值A[mask]。然后我们考虑mask的二进制表示中的每一位。对于某一位i如果mask在这一位上是1那么我们可以尝试把这一位“翻成0”从而得到一个更小的子集。F[mask]应该包含这个子集的所有子集之和。这引出了动态规划的状态定义dp[mask][i]表示考虑mask的前i位从第0位到第i位时所有子集的权值和。这里“考虑前i位”的意思是我们只允许改变即从1变成0mask的第0位到第i位这些比特位更高位的比特位必须保持和原mask一致。这个定义有点绕但它是理解一切的关键。我们可以这样解读当i -1时即还没开始考虑任何位dp[mask][-1]就是A[mask]本身因为一个不允许改变任何位的掩码其唯一的子集就是它自己。当我们从i-1推进到i时我们获得了处理第i位比特的自由度。最终当i N-1时即考虑完了所有N位dp[mask][N-1]就是我们所求的F[mask]因为此时我们可以自由改变mask的任何位只要是1来得到它的所有子集。注意这里“前i位”的索引方式在不同教程中可能不同有的从0开始有的从1开始。关键是理解“逐步解放对每一位的限制”这一过程。为了和代码保持一致后文我们采用从0开始索引dp[mask][i]表示处理完第0位到第i位共i1位。3. SOS DP 的算法实现与代码逐行解析理解了状态定义我们就可以推导状态转移方程并最终得到那个极其简洁的优化版本。3.1 二维DP推导与状态转移根据定义dp[mask][i]表示考虑前i位时mask的子集和。我们如何从dp[mask][i-1]得到它呢这需要考察mask的第i位比特。情况1mask的第i位是 0。如果第i位是0那么我们根本没有“翻0”的操作空间因为这一位本来就是0。在考虑前i位时我们无法通过改变这一位来得到新的子集。因此所有有效的子集在决定前i位时就已经被前i-1位的考虑过程所涵盖了。 所以dp[mask][i] dp[mask][i-1]。情况2mask的第i位是 1。如果第i位是1那么对于mask的子集这一位有两种可能性保持为1或者翻转为0。子集在这一位保持为1这类子集在考虑前i位时其状态完全等同于在考虑前i-1位时mask本身的子集。它们的贡献就是dp[mask][i-1]。子集在这一位翻转为0这类子集相当于我们把mask的第i位强制设为0得到一个新的掩码mask ^ (1 i)然后考虑这个新掩码在前i-1位上的所有子集。因为第i位已经是0且不允许再改变对于当前mask的这类子集来说所以它们的贡献就是dp[mask ^ (1 i)][i-1]。因此当第i位是1时总贡献是这两部分之和dp[mask][i] dp[mask][i-1] dp[mask ^ (1 i)][i-1]综合两种情况状态转移方程可以统一写为if (mask (1 i)) dp[mask][i] dp[mask][i-1] dp[mask ^ (1 i)][i-1]; else dp[mask][i] dp[mask][i-1];初始条件dp[mask][-1] A[mask]。在代码中我们通常用dp[mask][0]来表示考虑了第0位之后的状态因此初始化时dp[mask][0]需要根据第0位的情况由A[mask]计算而来。更常见的做法是直接让dp[mask] A[mask]作为第-1层的状态然后开始迭代i从0到N-1。二维DP的代码实现如下for(int mask 0; mask (1N); mask) { dp[mask][-1] A[mask]; // 初始化通常用另一个一维数组或dp[mask][0]的特殊处理来实现 for(int i 0; i N; i) { if(mask (1i)) dp[mask][i] dp[mask][i-1] dp[mask ^ (1i)][i-1]; else dp[mask][i] dp[mask][i-1]; } F[mask] dp[mask][N-1]; }这个算法的时间复杂度是 O(N * 2^N)空间复杂度也是 O(N * 2^N)。虽然时间上达标了但空间上我们还可以优化。3.2 空间优化一维滚动数组与“子集迭代”写法观察状态转移方程你会发现dp[mask][i]只依赖于dp[?][i-1]即上一层的状态。这是典型的可以使用滚动数组进行空间优化的场景。我们可以只用一个一维数组dp[mask]来表示当前层正在计算第i位的结果。但这里有一个至关重要的遍历顺序问题。对于第i位是1的mask它的状态转移需要用到mask ^ (1i)在上一层的值。mask ^ (1i)是将mask的第i位由1变成0所以它的数值比mask小。如果我们正序遍历mask从0到2^N-1当计算到较大的mask时它所需要的mask ^ (1i)这个较小的状态可能已经被更新成当前层第i位的新值了而不是我们需要的上一层第i-1位的旧值。这会导致错误。正确的做法是对于每一位i我们逆序遍历所有mask。因为mask ^ (1i)小于mask逆序可以保证当我们更新dp[mask]时dp[mask ^ (1i)]还保留着上一轮即未考虑第i位时的值。于是我们得到了SOS DP最经典、最简洁的代码形式// 初始化dp[mask] 存储 A[mask] for(int i 0; i (1N); i) { F[i] A[i]; } // SOS DP 核心 for(int i 0; i N; i) { for(int mask 0; mask (1N); mask) { if(mask (1 i)) { F[mask] F[mask ^ (1 i)]; } } } // 循环结束后F[mask] 即为所有子集的权值和这段代码就是“一分钟学会”的精华。它看起来简单但内涵深刻。外层循环i遍历每一个二进制位内层循环遍历所有掩码。只有当掩码的第i位是1时我们才进行累加操作累加的对象是“将第i位翻转为0”后的那个掩码的当前值。实操心得这段代码的优雅之处在于它直接在原数组F上进行了“原地”更新。在每一轮i的循环中F[mask]的含义是“考虑了第0位到第i位之后mask的子集和”。当i从0迭代到N-1后F[mask]自然就成为了考虑所有位之后的最终结果。务必理解这个“逐步解放比特位”的过程这是内层循环可以原地操作且结果正确的根本原因。3.3 超集求和Superset Sum的变体有时我们需要求的不是子集和而是超集和。即G[mask] 所有包含mask的集合的权值和。也就是满足supmask mask mask的A[supmask]之和。这可以通过一个简单的变换来解决。求mask的超集和等价于求(~mask)在全集补集意义上的子集和然后再进行一些调整。更直观的方法是修改SOS DP的遍历逻辑。在子集求和中我们是在mask的1位上做文章把1翻成0。在超集求和中我们则需要在mask的0位上做文章把0翻成1。因此代码只需要改变判断条件// 初始化 F[mask] A[mask] for(int i 0; i N; i) { for(int mask 0; mask (1N); mask) { if(!(mask (1 i))) { // 注意这里判断的是第i位为0 F[mask] F[mask | (1 i)]; // 将0翻为1 } } } // 循环结束后F[mask] 即为所有超集的权值和同样为了保证用到的F[mask | (1i)]是上一层的值内层对mask的遍历顺序也有要求。这里mask | (1i)比mask大所以我们需要正序遍历mask从0到2^N-1以确保计算小mask时它依赖的大mask还没有被当前轮次更新。4. SOS DP 的典型应用场景与实战例题理论再漂亮不如看几个实实在在的例子。下面我通过几个经典问题展示SOS DP如何大显神威。4.1 应用一快速子集卷积计数问题描述给定两个数组f[mask]和g[mask]定义它们的子集卷积h[mask]为h[mask] sum over all submask of mask: f[submask] * g[mask ^ submask]即将mask划分为两个不相交子集的所有方式对应的f和g值乘积之和。暴力计算需要 O(3^N) 时间。利用SOS DP我们可以优化到 O(N^2 * 2^N)。思路是对f和g分别做SOS DP得到它们各自的子集和数组F和G。根据容斥原理或莫比乌斯反演可以通过F和G快速计算出h的某种变换形式然后再逆变换回去。 这实际上是快速子集卷积Fast Subset Convolution的核心步骤之一SOS DP扮演了预处理的关键角色。4.2 应用二Codeforces 题目实战CF 1208F这是一道非常经典的SOS DP应用题。题目大意给定一个数组a找到下标(i, j, k)使得(a[i] | a[j]) a[k]最大且i j k。一个关键技巧是对于某个值x我们想知道是否存在两个不同的位置i, j使得a[i] | a[j]是x的超集即(a[i] | a[j]) x x。我们可以用SOS DP来维护对于每个值mask能在数组中找到的、其超集对应的两个最大或最靠右的下标。通过预处理这个信息我们就能枚举a[k]并快速找到能与它进行“与”操作后得到最大值的(a[i] | a[j])。解题思路简化我们维护一个数组dp[mask] pair(最大下标次大下标)表示能通过“或”运算得到mask的超集的两个最大数组下标。初始化dp[a[i]]用下标i更新。使用SOS DP超集版本来合并信息对于每个mask如果它的某个超集supmask有更优的下标对就更新dp[mask]。这个过程需要小心处理确保两个下标来自不同的原始元素。预处理完成后对于每个a[k]我们枚举a[k]的所有子集submask这里又用到了子集枚举技巧检查dp[submask]中记录的两个下标是否都小于k满足i j k然后计算(submask a[k])更新答案。这道题完美结合了子集枚举、超集SOS DP和信息合并是检验SOS DP掌握程度的绝佳题目。4.3 应用三集合计数问题问题有N个物品每个物品有一个权值一个不大的整数比如小于20。给定很多个查询每个查询是一个权值集合mask问有多少种选择物品的方式使得所选物品权值的“或”运算结果恰好等于mask。令cnt[val]为权值为val的物品数量。定义f[mask]为选择的物品权值“或”起来是mask的子集的方案数。注意是子集而不是恰好。那么要得到“恰好”的方案数需要用到容斥原理子集反演。首先计算f[mask]。考虑一个物品它的权值w必须是mask的子集这个物品才能被选入一个最终“或”结果为mask子集的方案中。对于所有是mask子集的权值w每个物品都有选或不选两种选择。因此f[mask] 2^(sum_{w subset of mask} cnt[w])。这里的sum_{w subset of mask} cnt[w]正是对所有是mask子集的权值w的物品数量求和这完全就是SOS DP要解决的问题。我们可以令A[mask] cnt[mask]如果mask这个权值存在然后对A做一次SOS DP得到F[mask] sum_{submask of mask} A[submask]即子集物品总数。那么f[mask] 2^(F[mask])。得到f[mask]子集方案数后通过容斥原理莫比乌斯反演即可得到g[mask]恰好等于mask的方案数g[mask] sum_{submask of mask} (-1)^(popcount(mask) - popcount(submask)) * f[submask]。这个计算过程本身又可以用SOS DP的变体高维前缀差分来高效实现。5. 常见问题、调试技巧与性能优化即使理解了原理在实现时也难免踩坑。下面是我在多次实践中总结的一些经验和教训。5.1 内存与初始化陷阱SOS DP通常处理的是长度为2^N的数组。当 N 达到20甚至22时数组大小是百万到千万级别。在C中使用int类型4字节的数组大小约为 4MB 到 16MB通常可以接受。但如果使用long long或者二维数组就需要小心了。错误示例int dp[120][20];这个二维数组的大小是 2^20 * 20 * 4字节 ≈ 80MB很可能导致栈溢出如果开在函数内部或超内存限制。务必使用一维滚动数组。初始化最安全的做法是单独用一个数组A存储初始值然后用另一个数组F做DP。如果像示例代码那样原地更新要确保初始值F[mask] A[mask]被正确设置。如果A[mask]的计算本身有耗时注意别把计算逻辑错误地放在DP循环里。数据类型溢出子集和可能非常大尤其是涉及方案数2的幂时。务必使用long long或__int128并在取模运算时注意中间结果溢出。5.2 遍历顺序与位运算细节这是SOS DP最容易出错的地方。子集和标准SOS DP内层对mask的循环必须是逆序从(1N)-1到0吗仔细看我们的经典代码它用的是正序for(int mask 0; mask (1N); mask)。为什么可以因为我们的判断条件是if(mask (1 i))只有当第i位是1时才更新。对于当前mask它用到的mask ^ (1i)是比它小的数。在正序遍历时当我们处理到mask时比它小的mask ^ (1i)可能在本轮i循环中已经被更新过了如果它的第i位也是1。这会导致错误吗会所以经典代码其实是错误的不这里有一个精妙之处。让我们重新审视经典代码的循环for(int i 0; i N; i) { for(int mask 0; mask (1N); mask) { if(mask (1 i)) { F[mask] F[mask ^ (1 i)]; } } }假设i1我们正在处理所有掩码的第二低位。当mask 3 (二进制11)时mask ^ (11) 1 (二进制01)。在正序遍历中mask1会在mask3之前被处理。当处理mask1时它的第1位是0所以if条件不成立F[1]不会被更新。因此当处理mask3时F[1]仍然是上一轮i0结束后的值这正是我们需要的。所以对于标准子集和SOS DP正序遍历是可行的因为被依赖的项mask ^ (1i)在第i位一定是0所以它在当前轮次不会被更新。这是一个非常重要的洞见但是为了保险和统一理解很多资料和选手习惯使用逆序遍历这总是正确的。对于超集和版本则必须使用正序遍历。位运算优先级if(mask (1 i))千万别写成if(mask 1 i)因为位运算的优先级低于会导致逻辑错误。加括号是好习惯。5.3 从子集和还原原数组逆SOS DP有时我们做了SOS DP得到F[mask]子集和但后续步骤需要用到原始的A[mask]。如何从F还原A这个过程称为“莫比乌斯反演”或“高维前缀差分”。原理是SOS DP的逆过程。代码和SOS DP非常像只是把加号变成减号并且遍历顺序要反过来从高位到低位// 假设 F[mask] 已经是子集和 for(int i N-1; i 0; --i) { for(int mask 0; mask (1N); mask) { if(mask (1 i)) { F[mask] - F[mask ^ (1 i)]; } } } // 循环结束后F[mask] 就变回了原始的 A[mask]这个逆操作在容斥原理和子集卷积中非常有用。5.4 性能优化与小技巧循环展开与寄存器优化当N固定且较小时比如N20编译器通常能很好地优化内层循环。手动展开循环收益不大。使用内置函数__builtin_popcount(mask)可以快速计算二进制中1的个数在容斥等场景常用。预处理2的幂如果问题中频繁需要计算2^k mod M提前预处理一个数组pow2是必要的。内存访问优化SOS DP的内存访问模式是连续的对缓存友好。使用一维数组和顺序访问即可。6. 总结与延伸思考SOS DP的本质是一种高维前缀和。我们可以把每个掩码mask看作一个N维空间中的点坐标是每个比特位0或1。F[mask]求子集和就相当于求这个N维立方体中一个“低角”原点到“高角”mask点形成的子立方体内所有点的权值和。SOS DP的逐位处理正是在逐维度地计算这个前缀和。掌握了标准SOS DP你可以很容易地扩展到其他集合运算按位与的子集和求所有满足submask mask submask的集合的和这就是标准的子集和。按位或的超集和求所有满足supmask | mask supmask的集合的和这就是超集和。对称差异或的相关求和这类问题通常需要结合沃尔什变换Walsh-Hadamard Transform。最后学习SOS DP最好的方法就是动手。找几道标有“SOS DP”或“Sum over Subsets”的题目如CF 165E, CF 383E, CF 449D从理解暴力解法开始然后推导DP方程最后写出优化代码。当你看到原本TLE的暴力枚举被瞬间秒杀时那种成就感就是算法学习最大的快乐。记住这个核心代码模板理解其背后的逐位解放思想你就能在需要处理集合关系的题目中多拥有一件强大的利器。