生成子图计数问题学习笔记

· · 算法·理论

好像烂尾了

省选场上觉得 D2T2 很有意思，但是因为太菜，只拿了最暴力的 24 分。于是回来把相关的科技都学了一下。

其实只是在复读参考资料

本文不涉及集合幂级数相关内容，因为笔者 不会 认为 NOI 及以下的比赛不会考。

前置知识：状压 DP，\mathcal{O}(3^n) 枚举子集，容斥原理。

一些符号和定义

下文中用 V,E 分别表示图的点集和边集，n=|V|，m=|E|，点从 0 到 n-1 编号，c(S) 表示 |\lbrace (u,v) \in E: u \in S, v \in S \rbrace|，c(u,S) 表示 |\lbrace (u,v) \in E: v \in S \rbrace|。其中 c(S) 和 c(u,S) 都容易 \mathcal{O}(m 2^n) 预处理。

一些模板题

连通生成子图计数

令 f(S) 表示仅考虑点集 S 的导出子图时，S 连通的方案数。

考虑容斥，用所有边任意的方案数减去至少两个连通块的方案数：任选顶点 u \in S，每次枚举包含 u 的连通块 T \subsetneqq S，S \backslash T 中的边任意。实践上多将 u 设为 \min S，代码就用 lowbit 实现。转移如下：

f(S) = 2^{c(S)} - \sum_{T \subsetneqq S, \min S \in T} f(T) 2^{c(S \backslash T)} \\

直接枚举子集即可做到 \mathcal{O}(3^n)。

（无向）欧拉生成子图计数

引理：在一个集合中选出任意多个数使得选出的数异或值为零，方案数为集合大小减去该集合线性基大小的二次幂。可理解为不在线性基中的元素可以任意选，再用线性基内的元素调整至异或和为 0。

把每条边 (u,v) 看作一个 n 位二进制数 2^u \oplus 2^v，那么一个子图是欧拉图首先要求所有点的度数为偶数，即所有边对应的数异或和为 0。令 f(S) 表示集合 S 中所有点的度数均为偶数的方案数，用上述引理容易 \mathcal{O}(nm 2^n) 计算，增量计算的话可以做到 \mathcal{O}((n+m) 2^n) 等等。

再令 g(S) 表示集合 S 中的点构成欧拉图的方案数，观察 f(S) 和 g(S) 的关系。注意到 g(S) 多了一个连通的限制，可以直接枚举子集减去不连通的情况数：

g(S) = f(S) - \sum_{T \subsetneqq S, \min S \in T} g(T) f(S \backslash T) \\

时间复杂度 \mathcal{O}(3^n)。

生成树计数

考虑从小到大加点。令 f(S) 表示加到点 u 时点集 S 的生成树个数，容易发现 u = \max S。

当加入点 u 时，将前面已经加入的点划分为若干个集合，每个集合内部构成一棵树并向点 u 连边。依次加入集合，并且为了防止算重，每次强制加入的集合包含 \min S：

f(S) = \sum_{T \subseteq S \backslash \lbrace \max S \rbrace, \min S \in T} f(T) f(S \backslash T) c(\max S, T) \\

时间复杂度 \mathcal{O}(3^n)。不过这个问题可以通过 矩阵树定理 做到和高斯消元一个复杂度。

生成仙人掌计数

我们从圆方树的角度考虑问题：令 f(S,i,j) 表示包括了集合 S 内的点，起点为 i，终点为 j 的路径条数，同时在环的最大点处合并，容易 \mathcal{O}(n^3 2^n) 算出任意子集的生成环个数。但在计算仙人掌时，既需要枚举当前考虑的环，又需要枚举当前环对应方点的子树，两层枚举子集的时间复杂度至少为 \mathcal{O}(4^n)，需要优化。

不难发现，枚举环与合并出仙人掌的复杂度分别为 \mathcal{\widetilde O}(2^n) 和 \mathcal{\widetilde O}(4^n)，可以试着平衡一下。将 f(S,i,j) 的定义放松为路径上的每个“点”本身可以是一棵仙人掌，同时令 g(S) 为包含了集合 S 的仙人掌数量。同样从小往大加点，f(S,i,j) 直接枚举子集转移，合并到 g(S) 时注意强制 i \le j 以免重复计算。于是有：

\begin{aligned} f(S,i,j) &= \sum_{T \subsetneqq S} \sum_{k \in T, (k,j) \in E} g(T) f(S \backslash T,i,k) \\ g(S) &= \sum_{T \subsetneqq S, \min S \in T} \sum_{0 \le i \le j < n, i,j \in T, (i,\max S),(j,\max S) \in E} f(T,i,j) g(S \backslash T) \\ \end{aligned}

时间复杂度 \mathcal{O}(n^3 3^n)。

点双连通生成子图计数

试着用组成连通图的方案数减去建出圆方树后方点数大于 1 的方案数来计算。外层枚举当前点双，内层枚举方点的当前方点子树的 \mathcal{\widetilde O}(4^n) 做法是简单的，但我们需要更优的做法。

首先，全图点双连通意味着没有割点，于是可以分步减去所有含有割点的方案。令 f_u(S) 表示集合 S 组成的 连通图 的割点编号不小于 u 的方案数，那么首先有：

f_0(S) = 2^{c(S)} - \sum_{T \subsetneqq S, \min S \in T} f_0(T) 2^{c(S \backslash T)} \\

即 f_0(S) 就是点集 S 连通的方案数。接下来逐步从 f_u(S) 推到 f_{u+1}(S)，也就是要减去 u 同时向多个方点连边的情况：

f_{u+1}(S) = f_u(S) - \sum_{T \subsetneqq S, u \in T, \min(S \backslash \lbrace u \rbrace) \in T} f_{u+1}(T) f_u((S \backslash T) \cap \lbrace u \rbrace) \\

这样一直递推下去，f_n(S) 就是答案。时间复杂度 \mathcal{O}(n 3^n)。

边双连通生成子图计数

类似点双的 \mathcal{\widetilde O}(4^n) 并不难。但由于点双的 \mathcal{\widetilde O}(3^n) 做法需要逐步减去有割点的方案数，而本文所述的状压 DP 不能单独考虑一条条“边”作为割边，我们无法将这一做法简单扩展至边双的情况。

注意到，割边能与大小为 2 的点双一一对应。我们可以如上 先求出所有集合组成点双的方案数，再把所有大小为 2 的点双的方案数置为 0，然后把上面求点双方案的过程倒过来做。从另一个角度看，就是从大到小依次加入割点。令 g_u(S) 表示集合 S 组成的 边双连通图 的割点编号不小于 u 的方案数，状态转移方程直接反过来就可以了：

\begin{aligned} g_n(S) &= [|S| \ne 2] f_n(S) \\ g_u(S) &= g_{u+1}(S) + \sum_{T \subsetneqq S, u \in T, \min(S \backslash \lbrace u \rbrace) \in T} g_{u+1}(T) g_u((S \backslash T) \cap \lbrace u \rbrace) \\ \end{aligned}

答案为 g_0(S)，时间复杂度 \mathcal{O}(n 3^n)。

DAG 生成子图计数

令 f(S) 表示仅考虑集合 S 时的方案数，枚举零度点进行转移。但发现直接枚举并不好做，于是容斥：令 g(S,A) 表示仅考虑集合 S 时，零度点集 包含了 集合 A 的方案数，h(S,B) 表示零度点集 恰好为 集合 B 的方案数。同时有：

\begin{aligned} g(S,A) &= 2^{\sum_{u \in A} c(u,S \backslash A)} f(S \backslash A) \\ g(S,A) &= \sum_{A \subseteq B \subseteq S} h(S,B) \\ \end{aligned}

根据 g 和 h 的关系，运用子集反演（本质是容斥）可以得到：

h(S,B) = \sum_{B \subseteq A \subseteq S} (-1)^{|A|-|B|} g(S,A) \\

于是有：

\begin{aligned} f(S) &= \sum_{B \subseteq S, B \ne \varnothing} h(S,B) \\ &= \sum_{B \subseteq A \subseteq S, B \ne \varnothing} (-1)^{|A|-|B|} g(S,A) \\ &= \sum_{A \subseteq S, A \ne \varnothing} g(S,A) \sum_{B \subseteq A, B \ne \varnothing} (-1)^{|A|-|B|} \\ &= \sum_{A \subseteq S, A \ne \varnothing} (-1)^{|A|-1} g(S,A) \\ &= \sum_{A \subseteq S, A \ne \varnothing} (-1)^{|A|-1} 2^{\sum_{u \in A} c(u,S \backslash A)} f(S \backslash A) \\ \end{aligned}

时间复杂度 \mathcal{O}(n 3^n)，瓶颈为枚举 c(u,S)。

强连通生成子图计数

对于原图的任意生成子图，将其按照强连通分量缩点后就是一个 DAG；特别地，全图强连通的子图缩点后将会变为一个点。同时从 DAG 生成子图计数的问题中可以知道，某一点集方案数的容斥系数（即 g(S,A) 前面的系数）就等于 (-1)^{点集的大小-1}。故我们令 f(S) 表示点集 S 强连通的方案数，g(S) 为若干强连通点集“拼成”集合 S 的所有方案的带权和，权值就是前文所述的容斥系数。为了方便计算，再令 g'(S) 表示 S 由至少两个集合拼成的方案数。有转移：

\begin{aligned} g'(S) &= -\sum_{T \subsetneqq S, \min S \in T} f(T) g(S \backslash T) \\ f(S) &= 2^{c(S)} - g'(S) - \sum_{T \subsetneqq S, T \neq \varnothing} g(T) 2^{\sum_{u \in T} c(u,S \backslash T)} \\ g(S) &= f(S) + g'(S) \\ \end{aligned}

时间复杂度 \mathcal{O}(n 3^n)，瓶颈仍为枚举 c(u,S)。实践上可以让 g(S) 和 g'(S) 共用一个数组，只需要注意转移顺序即可。

一些练习题

参考资料