子图计数

状压（集合幂级数）数符合某些性质的导出子图/边子图数。

APIO2025 记录

相似的容斥技巧：图计数。

集合幂级数基础运算。

限制分为无向图的连通性和有向图的强连通性，以及双连通性。

要做的比 $O(3^n)$ 好，需要集合幂级数的运算。

连通性

“已知要求连通的信息推及不要求连通的信息” 及其逆过程。

考虑 exp/ln 的组合意义：设 $f_S$ 表示导出子图 $S$ 的权值，$g_S$ 表示 $S$ 的所有划分方案的权值和，划分方案的权值为划分出的子集的权值积。有 $g_S=exp(f{)}_S$。

数连通子图

计数边子图使得是连通图。

$n\le 20$。

设 $f_S$ 为 $S$ 的导出子图的边子图有多少是连通图，$g=exp(f)$。则 $g_S$ 恰好考虑 $S$ 的导出子图的边子图个一次，$g_S=2^{cn{t}_S}$。$f=ln(g)$ 反推 $f$。

数连通二分子图

计数边子图使得连通且是二分图。

$n\le 20$。

枚举左部点 $S\subseteq U$，右部点 $U-S$，左右任意连。

忽略连通限制，原图的一个二分子图被计入 $2^{cnt}$ 次，$cnt$ 为弱连通块数。所以 exp 每拼上一个子图都要乘 $2$。

设 $f_S$ 为 $S$ 的答案乘 $2$，$g_S={\sum }_{T\subseteq S}{2}^{cross(S,T)}=2^{su{m}_S}{\sum }_{T\subseteq S}{2}^{-su{m}_T-su{m}_{S-T}}$，子集卷积求 $g$，$f=ln(g)$。

数杏仁图

给定杏仁的两极 $s,t$，对于每个 $u$ 计数边子图使得是杏仁且 $s\to u$。

$n\le 22$。

把从 $t$ 出发的所有链状压求出来 $O(2^n{n}^2)$。把这些链挖掉两极 exp 起来。询问时枚举 $u$ 所在的链和 剩下的任意组合的方案相乘。

Q6954

计数边子图使得连通且所有环的交非空。

$n\le 16$。

两个环交于大于两个点会形成新的大环，这三个环至多交于 $2$ 点。

所以合法的状态有：树、基环树、$\le 2$ 个点使得删去后图中无环。容斥掉树上删点也无环：$ans=an{s}_1-an{s}_2+((\genfrac{}{}{0ex}{}{n}{2})-n+1)nu{m}_{tree}+\sum ((\genfrac{}{}{0ex}{}{i}{2})-i+1)nu{m}_{ci{r}_i}$。

子集的生成树数可以矩阵树 $O(2^n{n}^3)$。也可以依次对于每个 $u=1\sim n$，算 $S\in [2^u,2^{u+1})$ 的方案数，即把 $<u$ 的子集乘上与 $u$ 的连边数 exp 起来，复杂度 $O(2^n{n}^2)$ 。

基环树是枚举环上的点集 $S$，先状压出环上排列的方案数，再把环缩成一个点做生成树计数。每个基环树有一个与环大小相关的容斥系数。复杂度 $O(2^n{n}^3)$。

删一个点图中无环，枚举删 $u$，剩下的子集内部有生成树数，还有至少一条连向 $u$，exp 起来。复杂度 $O(3^{n}n)$。

删两个点图中无环，枚举删 $u,v$，每个剩下的子集选至多一条边与 $u/v$ 连，不能没有，exp 起来，复杂度 $O(3^n{n}^2)$。还有一种数重的情况，变成 $u$ 和 $v$ 不连通，即两个数

图 k 匹配

$O(3^{n/2})$ 加速到 $O(2^{n/2}{n}^2)$。

强连通性

无向图重定向为 DAG 的方案数

P10221

设 $f_{i,s}$ 表示 $s$ 分为 $i$ 个非空段形成 DAG 的方案，$g_{i,s}$ 为 $s$ 分为 $i$ 个非空段段间没有边的方案数。容斥系数同 DAG 计数，可以做到 $O(3^n{n}^2)$。设 $F_S(x)=\sum f_{i,S}{x}^i$，$F_S(x)=G_T(x)F_{S\oplus T}(x)$，拉插之后算系数，复杂度 $O(3^{n}n)$。