一类图论连通性相关状压 DP 的做法 最后更新于 2025-04-11 17:57:06

# 一类图论连通性相关状压 DP 的做法 本文很多东西来自于学习了 Mackerel_Pike 大佬的 [一类图论相关的状压 DP 题的常见解法](https://www.cnblogs.com/Mackerel-Pike/p/16395436.html)，在此基础上增加了一些和 DAG 计数相关以及集合幂级数相关的东西。 --- ### 前言 首先关于图的最优化，所有强联通图和双联通图都能分解为若干链，这样就能用一种每次钦定链首尾的方式去 DP，但是这种东西会把一个图算多次，不过最优化下不影响；DAG 枚举拓扑序，每次新加点，也会算重； 图的计数一般可以考虑容斥，DAG 相关的计数可以枚举 DAG 入度为 $0$ 的点集 $T$ 前提 $T$ 是一个独立集，然后注意会算重，由 $\sum \binom{n}{|T|}g(|T|)=1$ 得到 $T$ 的容斥系数为 $(-1)^{|T|-1}$。 集合幂级数 exp 的组合意义是用若干集合组合成 $S$ 的方案数,ln 是其逆运算就是把 $S$ 变成若干不相交集合的方案数（感觉就是把散的集合变成整的，比如生成子图的集合幂级数 ln 就是生成联通子图的集合幂级数）。 > **关于 $O(n^22^n)$ 求每个子集的生成树边权之积**：考虑枚举子集最大的点 $i$，然后显然这些包含 $i$ 的生成树能刻画成 $i$ 向若干颗子树连边，方案数相当于 $\prod f_{T}\times V_{T}$，其中 $V_{T}$ 为所有 $T$ 向 $i$ 连边的边权之和，容易写成集合幂级数的形式 $F_{i-1}=\sum\limits_{T\subseteq 2^{i}-1}f_{T}V_{T}z^{T}$，则包含 $i$ 的集合 $S$ 的答案为 $[z^{S\text{\\}T}](\sum\limits_{j\geq 0}\frac{ F_{i-1}^{j}}{j!})=[z^{S\text{\\}T}]\exp(F_{i-1})$，每一次做 exp 的复杂度是 $O(i^22^i)$ 的，最后时间是 $\sum\limits_{i\leq n}O(i^22^i)=O(n^22^n)$，这个技巧我们称之为**逐点牛顿迭代法**。 > > 例题：**[ABC253Ex] We Love Forest** > > 一个森林的概率为 $\prod\limits_{i\in V} p_{i}\times \prod \limits_{i\notin V}(1-p_i)$，最后变成了 $\sum \limits_{T}\prod\limits _{i\in V_{T}}\frac{p_i}{1-p_i}$，然后变成求有 $i\in [1,n-1]$ 条边的森林边权积之和。 > > 考虑森林是由若干不交树并起来的，直接 exp 即可，相当于 $ans_{n-i}=[x^Sy^i]\prod\limits_{i\in [1,n-1]}\exp(F(x,y)),F(x,y)=\sum\limits_{T\subseteq S}f_{T}x^{T}y$。 > > 注意到对 $y$ 一维是加物品背包，时间复杂度 $O(n^32^n)$。 > > bonus：存在 $O(n^22^n)$ 的做法，但是我才疏学浅才刚刚入门集合幂级数所以不会。 ### DAG **[CEOI2019] Amusement Park** 给边定向后是 DAG 的图计数，因为 DAG 翻转后也是 DAG 所以平均翻转数为 $\frac{m}{2}$。 使用容斥 $f_{S}=\sum\limits_{T\subseteq S,S\neq \empty}(-1)^{|T|-1} g_{T}f_{S\text{\\}T}$，其中 $g_{T}$ 表示 $T$ 是否为独立集，不难发现是一个半半在线子集卷积的形式，直接 $O(n^22^n)$ 就做完了。 **[ABC306Ex] Balance Scale** 据说非常经典的题。 没有等于就是 **[CEOI2019] Amusement Park**，那题就是枚举入度为 $0$ 的点集，由 $\sum \binom{n}{|T|}g(|T|)=1$ 得到~~猜到~~ $T$ 的容斥系数为 $(-1)^{|T|-1}$，最后得到 $f_{S}=\sum\limits_{T\subseteq S,S\neq \empty}(-1)^{|T|-1} g_{T}f_{S\text{\\}T}$，其中 $g_{T}$ 表示 $T$ 是否为独立集。 考虑还是枚举入度为 $0$ 的点集，但是如果点集不是独立集的话所有边一定是赋值成 `=`，考虑这样会缩成若干个连通块，那现在容斥系数是什么呢？如果设连通块数量为 $v(T)$，那么 $f_{S}=\sum\limits_{T\subseteq S,T\neq\empty}(-1)^{v(T)-1}f_{S\text{\\}T}$。 考虑这为什么是对的？首先一个连通块是一个合法的极小独立集，那么其容斥系数自然是 $1$，自然上述的容斥系数就对了。 然后上述 DP 方程可以写成 $f_{S}=\sum\limits_{T\subseteq S}g_{S}f_{S\text{\\}T}$ 的形式，直接半半在线子集卷积即可，时间 $O(n^22^n)$。 ### 联通图 **生成树** 给一张图，对每个 $i$ 求其恰好有 $i$ 条边的连通生成子图数量。 设 $f(S,i)$ 表示点集 $S$ 中有 $i$ 条边的生成子图数量。套路地考虑设计代表元：编号最大的点 $u$，然后发现去掉这个点$u$ 后联通子图裂开成了若干不交的联通子图，考虑生成函数 $F_{(S,k)}(x,y)=\sum\limits_{T\subseteq S,i+j=k}f(T,i)g(T,u,j)x^{T}y^k$，其中 $g(T,u,j)$ 表示 $T$ 和 $u$ 中的连边有 $j$ 个的方案数，那么 $f(S,i)=[x^{S\setminus \{u\}}y^i]\exp (\sum\limits_{k=1}^{m}F_{({S\setminus \{u\}},k)}(x,y))=[x^{S\setminus u}y^i] \prod\limits_{k=1}^{m}\exp\left( F_{({S\setminus\{u\}},k)}(x,y)\right)$。 最后注意到对于 $g(T,u,j)$ 的处理每个集合只会算一次，时间 $O(m2^n)$；求 $F$ 有 $m2^n$ 个有效位置一共是 $O(m^22^n)$ 的；然后每一个 $[x^{\setminus u}y^i]$ 求系数是 $m$ 次背包，直接暴力跑是 $O(m^2n^22^n)$。 但是特殊的是每一个点集 $S$ 的关于 $y$ 的多项式次数不超过 $\binom{|S|}{2}$，考虑子集卷积的时候 $|T|+|S\setminus T|=|S|$，两个多项式相乘的得到的多项式次数显然不大于 $\binom{|S|}{2}$，自然可以转化为点值相乘然后还原多项式，考虑集合幂级数 $\exp$ 其实就是 $\sum\limits_{i=0}^{|S|}\frac{F^i(x)}{i!}$，每一次就是若干次子集卷积，自然可以对 $y$ 一维拉插，这样卷积的复杂度变成了 $O(m)$，这样时间复杂度是 $O(mn^22^n)$，最后的复杂度就是 $O(mn^22^n+m^22^n)$，比 $O(m3^n)$ 快。 > 众所周知，联通子图的集合幂级数就是生成子图的集合幂级数的 $\ln$，这题是不是也能这样做？ > > 设 $F(x,y)=\sum\limits_{T\subseteq S}\left(\sum\limits_{i=0}^{\binom{|T|}{2}}g(T,i)y^i\right)x^{T}$，则联通生成子图的集合幂级数就是 $\ln F(x,y)$。 > > 然后考虑还是对 $y$ 一维拉插，这样也能做到 $O(mn^22^n)$，而且常数更小。 ---- 剩下的咕了，因为**生成树**的降智浪费了时间导致没有在计划时间内学完。