子图计数

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

APIO2025 记录

集合幂级数在子图计数问题上的应用-cxy.pdf

容斥技巧：图计数。

集合幂级数基础运算。

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

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

连通性

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

abc236h。

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

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

数连通子图

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

$n \leq 20$ 。

设 $f_{S}$ 为 $S$ 的导出子图的边子图有多少是连通图， $g = e x p (f)$ 。则 $g_{S}$ 恰好考虑 $S$ 的导出子图的边子图个一次， $g_{S} = 2^{c n t_{S}}$ 。 $f = l n (g)$ 反推 $f$ 。

数连通二分子图

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

$n \leq 20$ 。

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

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

设 $f_{S}$ 为 $S$ 的答案乘 $2$ ， $g_{S} = \sum_{T \subseteq S} 2^{cross (S, T)} = 2^{s u m_{S}} \sum_{T \subseteq S} 2^{- s u m_{T} - s u m_{S - T}}$ ，子集卷积求 $g$ ， $f = l n (g)$ 。

数杏仁图

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

$n \leq 22$ 。

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

Q6954

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

$n \leq 16$ 。

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

所以合法的状态有：树、基环树、 $\leq 2$ 个点使得删去后图中无环。容斥掉树上删点也无环： $an s = an s_{1} - an s_{2} + ((2 n) - n + 1) n u m_{t ree} + \sum ((2 i) - i + 1) n u m_{c i 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}$ 的枚举子集。

Q13329

计数边子图使得是仙人掌

仙人掌看作若干个 $\geq 2$ 的环拼起来。 $f_{S}$ 表示 $S$ 中点组成环的方案数，可以状压。

枚举连接点 $i$ ，把一些包含 $i$ 的元素组合起来，即挖掉 $i$ 之后 exp。

复杂度 $O (2^{n} n^{3})$ 。

图 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^{n u m_{s}} - \sum_{t \subseteq s} g_{t} 2^{n u m_{s - t} + cross (t, s - t)}$

$g_{s} = f_{s} + \sum_{t \subset s, l o w bi t (s) = l o w bi t (t)} - f_{t} g_{s - t}$

先算 $g_{s}$ ，再算 $f_{s}$ ，再给 $g_{s}$ 加上 $f_{s}$ 。

岁月

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

here。

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

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

双连通性

待补。其实是曾经贺过。

点双连通生成子图计数

连通边子图是边子图的 ln。

每次再减去 $i$ 是割点的图，即挖掉 $i$ 再求 ln 再放回去。

边双连通生成子图计数

边双是没有大小为 $2$ 的点双的图。那可以求出点双的，然后去掉点数 $\leq 2$ 的，然后枚举割点 exp 拼起来。

另一种更可拓展的做法是边双连通-连通变换。

对于正向的变换：有权值 $a_{S}$ ，一个连通树形结构，每个点是一个集合，权值定义为所有点的 $\prod a$ ，已知合成一个点的方案数是 $b_{S}$ ，求最后的权值和。在这里是把所有边双缩为点，有权值 $a_{S}$ ，生成边双的方案数 $b_{S}$ ，连通边子图权值为这样一个树形结构权值和。

设 $F_{i}$ 表示只允许存在两端编号 $max \leq i$ 的割边的权值和， $(F_{0})_{S} = a_{S} b_{S}$ 。枚举 $u$ ， $S$ 会被 $u$ 出去的割边划分为包含 $u$ 的 $T$ 和若干 $T_{i}$ ， $(F_{u})_{S} = \sum (F_{u - 1})_{T} \prod (F_{u - 1})_{T_{i}} co f (u, T_{i})$ ，其中 $co f_{u, S}$ 是 $u$ 向 $v < u, v \in S$ 的边数。对 $\forall u \in / S, (F_{u - 1})_{S} co f (u, S)$ exp 然后子集卷积一次。

然后反过来。如果给定的 $a_{S} = 1$ ，则得到的 $(F_{n})_{S}$ 是连通边子图的数量，倒着做到 $(F_{0})_{S}$ 即为 $b_{S}$ 。

假设已知 $(F_{u})_{S}$ ，则所有 $u \in / S$ 的 $(F_{u - 1})_{S} = (F_{u})_{S}$ ，然后 $u \in S$ 的部分 $F_{u - 1} = F_{u} \times e x p ((F_{u - 1})_{S} co f (u, S))^{- 1}$ 。

吓哭了，之前根本没学明白。 $(e^{x})^{- 1} = e^{- x}$ ，等价于每乘一条边多一个常数 $c$ 算到 $co f$ 里，其他是完全一样的。所以正着变换等于逆着变且 $c$ 取反。记 $t r an s (a, c)$ 表示正着变换，则对于连通子图数 $f$ ，边双子图数为 $t r an s (f, - 1)$ 。

void trans(int *dp,int c){
	for(int i=n-1;i;i--){
		for(int s=0;s<(1<<i);s++){
			for(int t=0;t<(1<<n-i-1);t++){
				tmpg[s|(t<<i)]=dp[s|(1<<i)|(t<<i+1)];
				int num=__builtin_popcount(s&e[i]);
				tmph[s|(t<<i)]=c*dp[s|(t<<i+1)]%mod*num%mod;
			}
		}
		xorexp(tmph,tmph,n-1);
		xormul(tmpg,tmph,tmpg,n-1);
		for(int s=0;s<(1<<i);s++){
			for(int t=0;t<(1<<n-i-1);t++){
				dp[s|(1<<i)|(t<<i+1)]=tmpg[s|(t<<i)];
			}
		}
	}
}
void split(int *dp,int c){
	for(int i=1;i<n;i++){
		for(int s=0;s<(1<<i);s++){
			for(int t=0;t<(1<<n-i-1);t++){
				tmpg[s|(t<<i)]=dp[s|(1<<i)|(t<<i+1)];
				int num=__builtin_popcount(s&e[i]);
				tmph[s|(t<<i)]=mod-c*dp[s|(t<<i+1)]%mod*num%mod;
			}
		}
		xorexp(tmph,tmph,n-1);
		xormul(tmpg,tmph,tmpg,n-1);
		for(int s=0;s<(1<<i);s++){
			for(int t=0;t<(1<<n-i-1);t++){
				dp[s|(1<<i)|(t<<i+1)]=tmpg[s|(t<<i)];
			}
		}
	}
}

之前没想明白贺的代码，分别实现的正、反变换，事实上显然有 $t r an s (f, - c) = s pl i t (f, c)$ 。

还有一种正着证的方法。直接考虑 $t r an s (f, c)$ 的结构，首先是树形结构，所以每个边双不会跨过树边；然后如果一些边双缩成一个点，考虑一个桥，贡献为 $- 1$ 和直接拆开为新树边 $1$ ，抵消了。所以只能是边双。

【UR #30】交通管制

有 $k$ 条限制： $s \to t$ 路径上至少有 $c$ $(1 \leq c \leq 2)$ 条简单路径。

求满足条件的边子图数。

最后的图是若干极大的单点形成的连通块和若干大小 $\geq 2$ 的边双，其中对于 $c = 1$ 的 $(s, t)$ 不能属于同个单点连通块。

设 $f_{S}$ 表示 $S$ 的生成森林数，其中包含 $(s, t, 1)$ 的 $S$ 的 $f_{S} = 0$ 。 $g_{S}$ 为按上面求出来的边双数。

然后对一堆 $f$ 和 $g$ 连边，做生成树计数，要求不能有 $f$ 之间的边。这个即先钦定一些 $f$ 连边，权值 $- 1$ ，剩下的乱连，权值为 $1$ 。即 $t r an s (t r an s (f, - 1) + g, 1)_{U}$ 。

最后可能不连通，再 exp 一下。

P11567 建造军营 II

有 $k$ 个限制，一个边子图的权值为 $2^{c n t}$ ，其中 $c n t$ 为 $(u, v) \in E^{'}$ 且不存在 $p \to q$ 的边不重复路径经过 $(u, v)$ 的数量。

求边子图权值和。

把每个 $(p, q)$ 路径上所有边双染黑，剩下的白边有 $2$ 的权值。

黑连通块要求：必须同时包含整对的 $(p, q)$ ；不能存在一个桥没有被 $(p, q)$ 对覆盖。初始 $f_{S}$ 为满足第一个的连通边子图，做 $t r an s (f, - 1)$ 之后可以得到黑连通块，这个可以对每个 $S$ 中可能的桥分析，如果没有被 $(p, q)$ 覆盖贡献就被抵消。

白边双要求不能含有 $(p, q)$ ，选一条边为 $2$ ，还可以不选 $1$ ，即对 $3^{n u m (S)}$ 的 ln 做 $t r an s (f, - 2)$ 。

然后把黑白的加起来做 $t r an s (f, 2)$ 。

Quartz 4

Explorer

Recent Notes

all notes

AT_utpc2025_b 题解