子图计数

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

APIO2025 记录

容斥技巧：图计数。

集合幂级数基础运算。

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

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

连通性

可以容斥为总方案数减枚举一个包含最小点的子集不连通的方案数。复杂度 $O(3^n)$。

abc236h。

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

考虑 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$ 不连通，即两个树。

可以用 $2^n{n}^2$ 的集合幂级数代替 $3^n$ 的枚举子集。

图 k 匹配

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

强连通性

缩点后为 DAG，对 零度点 容斥，枚举零度点集合，容斥系数 为 $(-1{)}^{|T|+1}$。

有一些有意思的事情：比如可达性的容斥，把零度点当成 bfs 的最浅层点，系数也是 $(-1{)}^{|T|+1}$，但是显然有更简单的做法。

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

可以看成从空集开始每次加上一个集合（有序），集合带有 $0/1/-1$ 的系数。对于集合幂级数 $f$，$f_T=[e_T=0](-1{)}^{|T|+1}$ 且 $f_0=0$。$g(x)={\sum }_{i=0}{x}^i=\frac{1}{1-x}$，等价于求 $g(f)$ 在全集的系数。求逆。

重塑时光

设 $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)$。

主旋律

数多少个边子集，删去之后图强连通。

设 $f_s$ 表示强连通的方案，$g_s$ 表示若干个 $0$ 度点拼起来的方案，交替转移。

$f_s=2^{nu{m}_s}-{\sum }_{t\subseteq s}{g}_t{2}^{nu{m}_{s-t}+cross(t,s-t)}$

$g_s=f_s+{\sum }_{t\subset s,lowbit(s)=lowbit(t)}-f_t{g}_{s-t}$

先算 $g_s$，再算 $f_s$，再给 $g_s$ 加上 $f_s$。

岁月

数多少个边子集，删去之后图的最小外向生成树权值等于图的最小生成树。

here。

对于边权全相同的边，就是 主旋律。

按边权从小到大加入边，旧图的根集当作点，魔改一下。