综合技巧
枚举子集·计数变形
本课摘要
综合技巧课程回答“子集枚举与计数变形有哪些可复用的位运算技巧”。内容以枚举子集·计数变形为主线，配合逐步推导、可编辑演示、例题与练习形成可复查的学习闭环。
- 判断综合技巧的适用条件与状态边界
- 围绕“枚举子集·计数变形”推导转移与计算顺序
- 用演示、复杂度分析和配套题目校验实现
本课目录 · 0 节
正在整理目录…
当转移要「把集合劈成两半」
前三类里，转移都是往集合里加一个元素或一批元素。但有一类问题，转移需要把当前集合 拆成两部分：一部分交给这一步处理、另一部分留给子问题。比如「把 个任务分给若干天、每天做一个子集」，就要枚举「今天做哪个子集」，剩下的递归。
朴素地想：对每个 枚举它的所有子集，再对子集枚举它的子集……听上去是 甚至更糟。但有一个漂亮的事实：「枚举所有集合的所有子集」总共只有 对。因为每个元素对一个 对只有三种归属——在 里、在 里、或不在 里，共 。
怎么不重不漏地枚举 的所有非空子集？这就是本类的招牌代码——一行 for：
它从 开始，每次令 。 把最低的 位借位变 、其下方全变 ，再 只保留 里有的位——于是 严格递减、且始终是 的子集，直到 停止。恰好把 的每个非空子集访问一次。
读懂 (T−1)&S：为什么不重不漏
盯住 看一轮。子集要在 的三个 位（第 0、1、3 位）里取值，第 2 位恒为 ：
T=(T−1)&S——看它每一步落在哪个子集、如何绕开 之外的位。亲手跑一遍子集枚举
- 来源参与当前转移的依赖状态
- 当前正在计算或观察的状态
- 确定 / 最优已进入当前最优解或确定结果
- 已处理已经扫描、当前不再活跃的状态
- 非法越界、冲突或不可达状态
另一副面孔：位掩码 + 附加维做计数
状压的第二类「综合技巧」，是给位掩码再挂一维附加状态，把「求最优」变成「求方案数」。最典型的是排列计数：逐位决定「这一位放哪个数字」，用 mask 记「哪些数字已用」，同时挂一维记录某种附加量——比如「当前拼出的数 的余数」。
以「排列」（P4163）为例：给一串数字，求它的全排列中能被 整除的有多少个（数字可能重复）。状态 = 已用数字集合为 、当前拼出的数 的方案数。转移是在末尾追加一个未用的数字 ：
答案是 ——所有位都用上、且余数为 （整除）。这里的转移是「加一位」而非「枚举子集」，但同样属于状压综合技巧：mask 之外挂一维，把最优 DP 改写成计数 DP。
本质
「枚举子集」 与「位掩码 + 附加维计数」是状压的两把通用扳手：前者应对「把集合劈成两块」的划分型转移；后者把 升成 （ 为附加量，如余数），让状压能数方案、能带取模、能挂任意可累加的辅助信息。它们不是新模型，而是嫁接在前几类骨架上的技巧。
回看「宝藏」：层内枚举子集扩展
上一类里「宝藏」（P3959）是从「集合覆盖」的角度看的；换到「枚举子集」的视角，它其实正是本类技巧的实战——转移时对已连通集合 的补集枚举一个子集 ，作为「这一层新接入的点」。
代码里那句 for(int sub=rest; sub; sub=(sub-1)&rest) 就是子集枚举—— 是 的补集，枚举它的每个非空子集当作新增的一层。这也解释了为什么状压 DP 常被说成「 级别」：一旦转移需要枚举子集，复杂度就从 抬到 。
常见陷阱：计数去重、子集别把空集也算进去
排列计数里数字可能重复，若不去重会把「相同数字换位」的等价排列重复计数。稳妥做法：同一层里，相同数字只允许在首次出现的那一位被选（见代码里 且前一位未用则跳过）。另外 for(T=S;T;...) 只枚举非空子集——若你的转移需要「空子集」（这一层不接任何点），要另行单独处理，别指望这行循环覆盖它。
例题
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int T;
long long f[1 << 10][1010]; // f[mask][r]：用了数字集合 mask、当前数 mod d = r 的方案数
int main()
{
cin >> T;
while (T--)
{
char s[15];
int d;
cin >> s >> d;
int n = strlen(s);
int digit[15];
for (int i = 0; i < n; i++) digit[i] = s[i] - '0';
memset(f, 0, sizeof f);
f[0][0] = 1; // 空排列，余数 0
for (int mask = 0; mask < (1 << n); mask++)
for (int r = 0; r < d; r++)
{
if (f[mask][r] == 0) continue;
for (int i = 0; i < n; i++)
{
if (mask >> i & 1) continue; // 第 i 位已用
// ★去重：同一层里相同数字只在「首次出现的那位」用一次
if (i > 0 && digit[i] == digit[i - 1] && !(mask >> (i - 1) & 1))
continue;
int nr = (r * 10 + digit[i]) % d; // 追加一位后的新余数
f[mask | (1 << i)][nr] += f[mask][r];
}
}
cout << f[(1 << n) - 1][0] << endl; // 用完所有位、且整除 d
}
return 0;
}sub=(sub-1)&rest 这行子集枚举，把复杂度抬到 ——本类技巧的实战范例。// 枚举集合 S 的所有非空子集 T：经典写法，复杂度对单个 S 是 O(2^popcount(S))
for (int T = S; T; T = (T - 1) & S)
{
// 这里 T 恰好取遍 S 的每个非空子集
int rest = S ^ T; // rest 是 T 在 S 内的补集（另一半）
// ... 用 (T, rest) 做转移，例如把 S 劈成两块
}
// 对全部 S 求和：Σ 2^popcount(S) = 3^n —— 所以「枚举子集」整体是 O(3^n)