状压图计数入门

· · 算法·理论

简单介绍一下状压图计数这类问题。

作者水平不高，对这类问题没有什么深刻的理解，文章中的一些看法可能并不全面，如有不足之处欢迎在评论区指出。

需要读者对容斥原理有基本的了解。

下文中如无必要不会专门指出 dp 的初始状态。

下文中用 U 表示全集。

本文不涉及集合幂级数，可放心阅读。

遇到新题会持续更新。

例题 1 Lights Out on Connected Graph

题目链接

状压图计数的入门题目。

求解生成连通二分图的个数。

尝试对点做状压 dp。

二分图因为对称性不好计数，直接算黑白染色的方案数，也就是区分左部点和右部点，枚举作为左部点的子集，补集就是右部点，在两部分之间的边状态任意，其余边均不存在。

现在容斥掉不连通的方案，枚举集合内编号最小点所在的连通块减去即可。

设 f_S 为点集 S 的导出子图的生成连通二分图的黑白染色数量，g_S 表示黑白染色方案数，转移就是：

f_S=g_S-\sum_{\substack{T\subsetneq S\\ \operatorname{lowbit}(S)\in T}}f_T g_{S\setminus T}

最后答案就是 \frac{f_U}{2}，因为一个连通二分图恰有 2 个黑白染色方案。

例题 2 Amusement Park

题目链接

状压图计数的入门题目。

首先发现边数是假的，因为一个定向方案全部翻转也是合法的，两个对称方案改变的边数之和一定是 m，所以计算方案数再乘 \frac{m}{2} 即可。

尝试对于点做状压 dp。

设 f_S 为点集 S 的导出子图的答案，转移时可以枚举 0 出度点集合，那么集合内不能有边。

发现我们不能保证枚举的恰好是所有的 0 出度点，可能会漏掉一些，所以对点的个数做容斥。

设 g_S 为集合 S 内的边数，那么转移就是：

f_S=\sum_{\substack{T\subseteq S\\ g_T=0}} (-1)^{|T|-1}f_{S\setminus T} ## 例题 3 Balance Scale [题目链接](https://www.luogu.com.cn/problem/AT_abc306_h) 状压图计数的入门题目。 首先建图，有向边表示大于，无向边表示等于，那么把无向边缩点，有向边形成 DAG 就是合法方案。 和上一个题目几乎一致，但是多了一个无向边缩点。 所以我们枚举的 $T$ 可以不是独立集，让内部都是无向边进行缩点即可。 设 $f_S$ 为点集 $S$ 的导出子图的合法定向方案数，转移时枚举缩点后的 $0$ 出度点集合，形成的连通块数量就是缩点后实际的 $0$ 出度点个数。 设 $g_S$ 为点集 $S$ 内的连通块个数，那么转移就是： $$ f_S=\sum_{T \subseteq S} (-1)^{g_T-1}f_{S \setminus T} $$ $S \setminus T$ 和 $T$ 之间的边必须指向 $T$，$T$ 内的边必须都是无向边，都是确定的，没有额外系数。 ## 例题 4 寒妖王 [题目链接](https://www.luogu.com.cn/problem/P6789) 从这题开始就比较复杂了。 期望直接转为计数，统计每个情况的最大生成基环树森林权值之和。 直接做不大容易，把权值转到边上，统计每条边能够在最大生成基环树森林内的方案数。 类比 Kruskal 的过程，那么一条边能够加入当且仅当保留权值大于它的边时出现以下两种情况之一： - 连接的两点在一个连通块，该连通块是树； - 连接的两点不在一个连通块，两连通块中至多有一个不是树。 为了避免对相同边权的讨论，可以把编号作为第二关键字比较。 那么可以暴力枚举每一条边，每次只保留权值更大的边，计算 $f_S$ 和 $g_S$ 分别表示集合内剩下的边是树的方案数和连通的方案数，减一下就可以得到连通但不是树的方案数。 $f$ 的计算可以枚举叶子节点集合 $T$，也就是 $1$ 度点集合，转移时的系数就是 $T$ 中每个点连向 $S$ 中其余点的边数的乘积，转移时使用填表法，在计算出 $f_S$ 的时候枚举每一个超集转移，那么可以在转移前预处理出所有转移系数来避免掉复杂度中出现 $n$，注意这里同样需要容斥。 $g$ 的计算就很简单了，正难则反，枚举编号最小点所在的极大连通块容斥即可，设 $h_S$ 为 $S$ 内的边数，那么转移就是： $$ g_S=2^{h_S}-\sum_{\substack{T \subsetneq S\\ \operatorname{lowbit}(S)\in T}} g_T 2^{h_{S \setminus T}} $$ 为了保证 $T$ 是极大连通块，$T$ 与 $S \setminus T$ 之间的边都不存在，$T$ 内边的状态任意。 那么我们就以 $O(m3^n)$ 的复杂度解决了本题。 ## 例题 5 大度一点 [题目链接](https://qoj.ac/problem/6275) 考虑容斥，枚举编号最小的不合法点，把对应的不合法方案从答案里去掉。 不合法点要么 $0$ 度要么 $1$ 度。 $0$ 度的方案数就是不合法点编号都大于该点的所有方案。 $1$ 度点比较麻烦，如果这个点连向了编号大于它的点那么方案数还是不合法点编号都大于该点的所有方案，但如果连向编号小于它的点，这个被连的点就可以在子图中保持 $1$ 度，所以还要计算只有某个点为 $1$ 度点的方案数。 我们可以在外层从小到大枚举不合法点编号 $u$，维护 $f_S$ 表示集合 $S$ 内最小不合法点大于等于 $u$ 的方案数，$g_{S,i}$ 表示集合 $S$ 内仅有 $i$ 是编号小于 $u$ 的不合法点，且度为 $1$ 的方案数。 先计算 $g$，枚举 $i$ 连向的点，如果比 $u$ 小，那么这个点可以是合法点，对应一个 $f$，也可以是唯一的 $1$ 度点，对应一个已经算出的 $g$，如果比 $u$ 大就没有限制，根据 $f$ 的定义这里也直接对应一个 $f$，注意此时任何点都不能连向 $u$，我们在计算 $g$ 时也不考虑所有包含 $u$ 的集合。 $f$ 可以在原基础上迭代，枚举每个包含 $u$ 的集合，讨论该点的度减去不合法方案。 最终复杂度 $O(n^3 2^n)$。 ## 例题 6 重塑时光 [题目链接](https://www.luogu.com.cn/problem/P10221) 题目描述有点神人，特别是空序列这一块不大好处理。 拍成计数，发现切的方案和划分成的块的方案相互独立，可以乘法原理，统计划分成 $k$ 个非空序列的方案数，序列之间不计顺序。 先求划分出的一个序列的方案数，设 $h_S$ 表示 $S$ 内的点组成一个完整序列的合法方案数。 发现用人话来说，就是这个序列是 $S$ 的导出子图的拓扑序的方案数，枚举拓扑序的最后一个点进行转移即可，转移时确保枚举到的点没有出度。 划分出的不同序列之间不计顺序，那么就类似例题 2。 设 $g_{S,i}$ 表示把 $S$ 划分为 $i$ 段序列，每段序列之间没有边的方案数，这里的方案考虑拓扑序的部分，枚举编号最小点所在的弱连通块计数即可，转移时确保连通块与剩余部分之间没有边。 最后设 $f_{S,i}$ 为把 $S$ 划分为 $i$ 段的总方案数，类似例题 2 转移即可。 复杂度 $O(n^2 3^n)$，需要优化。 发现可以把容斥系数和 $g$ 绑在一块，那么转移 $f$ 时枚举两个集合后，剩下的部分完全就是多项式乘法，所以抽象成多项式，计算答案多项式在 $0\sim k+1$ 位置的值，最后拉插回来即可，这样枚举位置之后只需要预处理 $g$ 对应的多项式值，转移时就可以 $O(1)$ 直接相乘。 最终复杂度 $O(n 3^n)$。 用 $f$ 反推实际方案数是简单的。 ## 例题 7 二分图最大匹配期望 [题目链接](https://www.luogu.com.cn/problem/P14170) 首先，我们需要知道怎么刻画最大匹配。 用网络流或者匈牙利算法一看就很倒闭。 不过我们还有一个计算方式：霍尔定理。 **下文中的完美匹配都只针对左部点，即每个左部点都有与之相连的匹配边**。 霍尔定理的内容是：对于一个二分图，设左部点个数为 $n$，左部点集合为 $L$，右部点集合为 $R$，左部点集合 $S$ 的邻域，也就是与其直接相连的右部点集合，为 $N(S)$，那么我们有： - $\text{二分图存在完美匹配} \iff \forall S\subseteq L,\lvert S\rvert \le \lvert N(S)\rvert

进一步，我们还有：

既然都已经状压了，那么尝试枚举 \lvert S\rvert - \lvert N(S)\rvert 最大的 S 来统计就是个很好的选择。称这种集合为特殊集合。设 num(S)=\lvert S\rvert - \lvert N(S)\rvert。

现在有一个问题：特殊集合不一定唯一。

那我们就再来个第二关键字，比如集合大小。枚举最小的特殊集合。

这时我们发现合法的 S 唯一了。

这是出于一个性质：最小的特殊集合包含于所有特殊集合。

::::success[证明] 如果最小特殊集合是空集，那显然成立，否则 \max num(S)>0。

在此基础上：

首先证明所有特殊集合的交集非空。

先证明一个更弱的结论：任意两特殊集合的交集非空。

反证法，如果存在两个不相交的特殊集合 S、T，那么：

\begin{aligned} num(S \cup T) &= \lvert S \cup T\rvert - \lvert N(S\cup T)\rvert\\ &=\lvert S \rvert +\lvert T\rvert - \lvert N(S\cup T)\rvert\\ &\geq \lvert S \rvert +\lvert T\rvert - \lvert N(S)\rvert-\lvert N(T)\rvert \\ &=\lvert S \rvert - \lvert N(S)\rvert+\lvert T\rvert-\lvert N(T)\rvert\\ &> num(S) \end{aligned}

这违反了 S 是特殊集合的假设，所以不存在两个不相交的特殊集合。

进一步，任意两特殊集合的交集也是特殊集合。

\begin{aligned} num(S \cap T) &=\lvert S \cap T\rvert - \lvert N(S\cap T)\rvert\\ &=\lvert S \rvert +\lvert T\rvert -\lvert S \cup T\rvert - \lvert N(S\cap T)\rvert\\ &\geq \lvert S \rvert +\lvert T\rvert -\lvert S \cup T\rvert- \lvert N(S)\cap N(T)\rvert \\ &=\lvert S \rvert +\lvert T\rvert -\lvert S \cup T\rvert- \lvert N(S) \rvert -\lvert N(T) \rvert +\lvert N(S \cup T) \rvert \\ &=num(S)+num(T)-num(S\cup T) \end{aligned}

中间那个 \geq 是因为 S\cap T 能到达的点一定在 \lvert N(S)\cap N(T)\rvert 内，但反过来就不一定了。

整理一下就是：

num(S \cap T)+num(S\cup T)\geq num(S)+num(T)

又因为 S 和 T 是特殊集合，所以只能：

num(S \cap T)=num(S\cup T)= num(S)=num(T)

所以任意两特殊集合的交、并集都是特殊集合。

利用此结论配合反证法不难完成证明。

虽然只需要使用后一条结论就可完成证明，但我还是保留了我证明时形成的较完整的思维链，便于读者理解。

那么我们可以枚举最小的特殊集合 S 来计数。

可以用类似的集合操作技巧证明：去掉 S 和 N(S) 之后，剩下的图一定存在完美匹配。

那么问题分成两部分，一部分是集合 S 是最小特殊集合的概率，一部分是剩余图存在完美匹配的概率，二者互相独立。

设 f_{S,T} 表示保留左部点集合 S 和右部点集合 T，满足 S 是最小特殊集合且 N(S)=T 的概率，g_{S,T} 表示保留左部点集合 S 和右部点集合 T，图中存在完美匹配且 N(S)=T 的概率，h_{S,T} 表示保留左部点集合 S 和右部点集合 T，N(S)=T 的概率。

预处理 p_{S,T} 表示 S 和 T 之间没有边的概率，转移时单步容斥，对于 f、g 枚举最小特殊集合，对于 h 枚举实际到达的 T，减去对应的不合法概率即可。那么转移就是：

f_{S,T}=h_{S,T}-\sum_{\substack{S'\subsetneq S\\ T' \subseteq T \\ \lvert S \rvert -\lvert T \rvert\le\lvert S' \rvert - \lvert T' \rvert}} f_{S',T'}g_{S\setminus S',T\setminus T'}p_{S',T\setminus T'} g_{S,T}=h_{S,T}-\sum_{\substack{S'\subsetneq S\\ T' \subseteq T \\ \lvert S' \rvert - \lvert T' \rvert>0}} f_{S',T'}g_{S\setminus S',T\setminus T'}p_{S',T\setminus T'} h_{S,T}=1-\sum_{T' \subsetneq T} h_{S,T'}p_{S,T\setminus T'}

转移 f、g 时出现 g_{S\setminus S',T\setminus T'} 是因为，如果这部分不是完美匹配，那么可以用这部分的特殊集合和 S 拼起来形成 num 更大的集合。为了保证 S 是特殊集合，这部分必须存在完美匹配。

统计答案时枚举最小特殊集合。

设 G_{S,T} 表示保留 S、T，存在完美匹配的概率：

G_{S,T}=\sum_{T'\subseteq T}g_{S,T'}p_{S,T\setminus T'}

答案就是 \sum f_{S,T}p_{S,R\setminus T}G_{L\setminus S,R\setminus T}(n-\lvert S \rvert +\lvert T \rvert)。

例题 8 主旋律

题目链接

来一道简单题，主要是为了下一题做铺垫。

单步容斥，设 f_S 为集合 S 的导出子图的方案数，如果不合法那么缩点后是个点数大于 1 的 DAG，枚举缩点后的 0 出度点对应的集合，设 g_{S,i} 为集合 S 内的点分出 i 个强连通分量，每个强连通分量之间没有边的方案数，类似例题 1 容斥即可，g 转移时枚举编号最小点所在的强连通分量即可。

设 h_{S,T} 为起点在集合 S，终点在集合 T 的边数。

转移就是：

\begin{aligned} f_S &= 2^{h_{S,S}}-\sum_{T \subseteq S} \sum_i (-1)^{i-1}g_{T,i}2^{h_{S,S \setminus T}}\\ &=2^{h_{S,S}}-\sum_{T \subseteq S} 2^{h_{S,S \setminus T}}\sum_i (-1)^{i-1}g_{T,i} \end{aligned} g_{S,i}=\sum_{\substack{T \subseteq S\\ \operatorname{lowbit}(S)\in T}} f_T g_{S \setminus T,i-1}

好像会重复转移，发现真正会重复的地方只有 T=S 的转移，对于 f 来说这种转移只有 i \neq 1 时有效，而对应的 g 转移时不会用到未计算的 f，所以对于一个集合 S，先算 f 后算 g 就是对的。

这样是 O(n3^n) 的，我们优化一下。

如果能直接算出 \sum \limits _i (-1)^{i-1}g_{S,i} 就可以省掉枚举，发现 -1 的指数正好与 i 是线性关系，很容易想到把 g 直接定义为和式，转移变成这样：

f_S=2^{h_{S,S}}-\sum_{T \subseteq S} 2^{h_{S,S \setminus T}}g_T g_S=f_S+\sum_{\substack{T \subsetneq S\\ \operatorname{lowbit}(S)\in T}} -f_T g_{S \setminus T} 还是先算 $f$ 后算 $g$，根据前面的分析，转移是正确的。 ## 例题 9 岁月 [题目链接](https://www.luogu.com.cn/problem/P11834) 难度逆天，由特殊性质逐渐拓展到正解，会尽量讲的详细一些，方便理解。 这题的概率杀不杀都行，我没杀。 一个显然的转换是变成有向图，每条边 $\frac{1}{2}$ 概率消失。 ### 性质 B 原图最小生成树唯一 那么可以只保留最小生成树上的边，其它边存不存在都无所谓。 现在就变成，原图是树，存在外向生成树的概率。 一个显然的想法是枚举外向生成树的根，这样可以唯一确定生成树的结构，但是发现一个图可能会有多个合法根，会算重。 考虑 NOIP 2024 T3 的 trick，枚举所有可能根的位置就不会算重了，因为从每个点出发都可以到达全图所有点，所以这些根一定构成了连通块，内部都是双向边，直接与外部相连的部分是向外的单向边，所有向外伸展的边必须存在，向内的可以不存在，容易计算。 ### 性质 C 边权全部相同 限制就变成了存在外向生成树。 还是枚举根节点集合，那么集合内是强连通分量，这是 主旋律 原题。 现在要求从根节点集合可以到达所有点，可以对连通性做状压图计数，并不难，可以尝试思考下。 ::::success[解法] 单步容斥，转移时枚举根节点能到达的极大集合即可，集合不能存在出边，集合外的其余边随意。 设当前根节点集合为 $R$，$f_S$ 表示 $R$ 可以到达 $S$ 内所有点的概率，$E_{S,T}$ 表示起点在 $S$，终点在 $T$ 的边的数量： $$ f_S=1-\sum_{R \subseteq T \subsetneq S} f_T2^{-E_{T,S \setminus T}} $$ :::: 最后为了保证 $R$ 是当前图的最大根节点集合，还要求不能有从外部指向 $R$ 的边，显然这部分边不影响 $R$ 内部的连通性，也不会影响 $R$ 能到达的范围，所以和前两部分相互独立，直接乘上就好了。 那么对于一个根节点集合 $R$，转移次数是 $3^{\lvert U \setminus R \rvert}$，要枚举每个集合 $R$，总复杂度 $O(4^n)$，需要优化。 设 $f_{R,S}$ 表示根节点集合为 $R$ 情况下的 $f_S$。 发现整个转移好像跟 $R$ 就没啥关系，只限制了 $T$ 的范围，我们要求所有的 $f_{R,U}$，但是过程中算了一大堆 $f_{R,S}$，感觉挺浪费的。 发现我们实际是每次从 $R$ 向 $U$ 转移，那能不能反过来，从 $U$ 出发，转移到所有 $R$，反正转移系数跟 $R$ 没关系。 直接反着转移好像搞不出来，我们现在只关心 $f$ 的值，把 dp 结构抽象出来看看能不能找到一个能反着做的意义。 先把原本的转移方程写成这样： $$ f_S=1+\sum_{R \subseteq T \subsetneq S} -2^{-E_{T,S \setminus T}}f_T $$ 发现对于一个 $S$，每次可以任选一个子集 $T$ 走向它，转移时的系数只和 $S$、$T$ 本身有关，那么可以抽象成： 有一个有向无环图，每个点对应一个集合，向所有超集对应的点连边，$T \to S$ 边权为 $-2^{-E_{T,S \setminus T}}$，定义路径的权值为经过边权值的乘积，那么 $f_S$ 就表示以 $R$ 的任意超集为起点，到达 $S$ 的路径权值之和。 转移式里的 $1$ 就是以 $S$ 为起点的情况，和式就是在枚举路径的上一个点进行转移。 我们只需要 $f_{R,U}$ 的值，也就是以 $R$ 的任意超集为起点，到达 $U$ 的所有路径权值之和。 到现在就很简单了，把所有转移边全部反向，边权不变，计算从 $U$ 出发到 $S$ 的所有路径权值之和，由于对称性这个权值就等于原图中从 $S$ 出发到 $U$ 的所有路径权值之和，最后枚举起点做一个超集和即可。 计算路径权值之和的转移是这样的： $$ f_S=\sum_{S \subsetneq T} -2^{-E_{S,T \setminus S}}f_T $$ 然后做一个超集和就好了。 这样得到的 $f_S$ 就表示从 $S$ 内的点出发，能到达全集的概率。 枚举根节点集合，设 $g_S$ 为 $S$ 内强连通的概率，那么答案就是： $$ \sum_{R} f_R g_R 2^{-E_{U \setminus R,R}} $$ 复杂度 $O(3^n)$。 ### 正解 现在我们需要处理最小外向生成树大小的限制了。 首先，题目要求它等于最小生成树的大小，也就是要求这个最小外向生成树对应原图里的一个最小生成树。 考虑最小生成树计数的 trick，按边权从小到大加入边，相同边权的边在同一批被加入，每次把能连通的部分全部连起来缩点，这样就能保证数出来的都是最小生成树。 设 $f_R$ 为考虑 $R$ 所在的连通块，合法根节点集合为 $R$ 的概率，这里要求 $R$ 在同一个连通块内，考虑新增一些边时该如何转移。 首先把新形成的连通块拉出来，每个连通块分开考虑。 下文中的讨论范围是加入这一组新边后的一个连通块，下文中的“连通块”指加入新边前的一个连通块。 首先每个连通块内部是已经考虑好的，现在要把多个这样的连通块连起来。 还是枚举根节点集合 $R$，那么这些点会被分到不同的连通块中。 首先，$R$ 内每个点必须是所在连通块的根节点。 如果它在原连通块中不是根节点，那么在新图中就更不可能成为根节点。 其次，对于一个连通块，如果 $R$ 和它有交，那么交集部分必须恰好是该连通块的根节点集合。 如果有一个不在 $R$ 内的点是这个连通块的根节点，因为 $R$ 内有点在这个连通块内，而且是该连通块的根节点，那么根据根节点的强连通性，这个不在 $R$ 中的点可以到达这个 $R$ 内的点，就可以成为新图中的根节点了。 **所以，$R$ 内的点必须恰好是所在连通块的所有根节点。** 这一部分的贡献会对后面的 dp 有影响，在后面 dp 时一起处理。 **现在仿照性质 C，考虑三条限制。** - 限制 1：$R$ 强连通。 - 还是主旋律，但是稍微改一下，$R$ 内在同一个连通块的部分已经强连通，对应概率已经在前面的贡献里算过了。转移系数要用缩点后的点数。 - 转移时在同一个连通块内的部分必须一起转移，不能拆开，其实就是缩点之后做普通的主旋律，但是已经状压了所以不用真的缩点，在转移时加点判定就好，比如预处理所有集合对应的连通块编号集合，转移时看一下分出的两部分是否有交即可。 - 限制 2：$R$ 可以到达 $U$。 - 还是先考虑暴力转移，发现这里和之前不大一样了。 - 原本只需要考虑点，但现在都是连通块。 - 那么 $R$ 需要到达连通块内的每一个点，但还要考虑连通块内部也会对可达性产生影响。 - 分析一下发现当且仅当能到达连通块内任意根节点时可以到达整个连通块，所以只需要考虑连向根节点的边。 - 边的起点没有限制。 - 因为连通块缩点，所以同一连通块内的点必须绑在一块。 - 设 $g_S$ 为当前根节点集合为 $R$，能到达的根节点集合为 $S$ 且 $S$ 恰好是所在连通块中所有根节点构成的集合概率， $h_S$ 为 $S$ 恰为所在所有连通块所有根节点集合的概率，$sc_S$ 为 $S$ 内的点所在的连通块的集合，具体的转移是这样的： - $g_S=h_S-\sum \limits _{\substack{R\subseteq T \subsetneq S\\ sc_T \cap sc_S= \varnothing}}2^{-E(T,sc_{S \setminus T})}h_{S \setminus T}g_T

分析一下复杂度，处理一个大小为 n 的连通块的复杂度是 O(3^n)，连通块合并会形成一个树结构，那么分析树结构的每一层，设当前合并根节点大小为 n，本层对复杂度的贡献就是 O(3^n)，下一层的复杂度贡献满足 \prod \limits _i T_i=O(3^n)，因为必须分成至少两部分，所以最大贡献是 O(3^{n-1})，所以设 t(i) 为合并树第 i 层的所有节点贡献的复杂度，t(1)=O(3^n)，t(i+1)<\frac{t(i)}{3}，T(n)=\sum t(i)，放缩成等比数列求和，T(n)=O(3^n)。

结语

以上就是本文对状压图计数类问题的一些初步整理。从最基础的连通二分图计数、定向方案计数，到二分图最大匹配期望、岁月这类综合了容斥、连通性 DP、图论分析方法等技巧的题目，可以看出状压图计数的核心往往在于找到一个可以枚举的关键集合，把枚举边变为枚举点。

常见套路大致有：

当然也要熟练掌握对 dp 本身的优化技巧，比如把容斥系数直接绑进 dp 数组，使用反向转移、多项式插值等。

本文只是抛砖引玉，很多题目的推导细节和优化技巧并没有完全展开，部分公式和表述也可能存在疏漏。如果读者在阅读过程中发现错误，或者有更简洁的理解方式，欢迎在评论区指出。

希望这篇文章能对刚开始接触这类题目的读者有所帮助。

感谢阅读。