题解 SP4420 【KPGRAPHS - Counting Graphs】

和 sys 聊天的时候他说审题解会审到很多有趣的题目，然后我让他推荐几题，他跟我说了这题。 然而目前好像没看到这题有题解，难道是他拒绝了？ 我觉得这题也不会很有趣吧，就是中规中矩的图计数问题，纯理性愉悦内容，比赛基本不考的那种。 本着服务大众的理念，来普及一下这些简单的图计数。 进入正题，要计数三种图（简单有标号无向图）： 1. 连通图 2. 欧拉图（即可以一笔画的图） 3. 二分图 ### 连通图 令 $n$ 个点的连通图数量为 $a_n$，特别地，规定 $a_0 = 0$，令 $\displaystyle \hat A = \mathbf{EGF}(a) = \sum_{i = 0}^{\infty} \frac{a_i}{i!} z^i$，即 $a$ 的指数型生成函数。 令 $n$ 个点的图数量为 $d_n$，显然有 $\displaystyle d_n = 2^{\binom{n}{2}}$。 根据图计数理论有 $\displaystyle \hat A = \ln \mathbf{EGF}(d)$。 如果 $\hat G = \ln \hat F$，两边求导移项得 $\hat F {\hat G}' = {\hat F}'$，比较系数后不难得到递推式。 ### 欧拉图 令 $n$ 个点的欧拉图数量为 $b_n$，特别地，规定 $b_0 = 0$，令 $\displaystyle \hat B = \mathbf{EGF}(b) = \sum_{i = 0}^{\infty} \frac{b_i}{i!} z^i$，即 $b$ 的指数型生成函数。 令 $n$ 个点的，每个点的度数都是偶数的图数量为 $e_n$，有 $\displaystyle e_n = 2^{\binom{n - 1}{2}}$，特别地，规定 $e_0 = 1$。 这是因为考虑前 $(n - 1)$ 个点组成的任意图，加入第 $n$ 个点时仅和 $1 \sim (n - 1)$ 号点中度数为奇数的点连边，得到最终的图。据此 $n$ 个点的每个点的度数都是偶数的图，与 $(n - 1)$ 个点的任意图是一一对应的，于是前式得证。 一张图是欧拉图，当且仅当图中的每个点的度数都是偶数，且是图是连通图。 根据图计数理论有 $\displaystyle \hat B = \ln \mathbf{EGF}(e)$。 同上，求导比较系数后不难得到递推式。 ### 二分图 EntropyIncreaser 已经在 [UOJ Goodbye Jihai D. 新年的追逐战](http://uoj.ac/contest/50/problem/498) 中运用了类似方法求出此序列，可以查看他的 [题解](http://peehs-moorhsum.blog.uoj.ac/blog/5382)。 令 $n$ 个点的二分图数量为 $c_n$，特别地，规定 $c_0 = 1$，令 $\displaystyle \hat C = \mathbf{EGF}(c) = \sum_{i = 0}^{\infty} \frac{c_i}{i!} z^i$，即 $c$ 的指数型生成函数。 考虑求出 $n$ 个点的点二染色（黑白染色）图数量 $f_n$，令 $\hat F = \mathbf{EGF}(f)$。 容易得到：$\displaystyle \hat F = \sum_{i = 0}^{\infty} \sum_{j = 0}^{\infty} \binom{i + j}{i} 2^{i j} \frac{z^{i + j}}{(i + j)!}$。 即可以 $\mathcal O (m^2)$ 的时间复杂度求出 $f$ 的前 $m$ 项，若要追求更优的复杂度可以参考： 根据 Chirp Z-Transform，可以进行如下推导： $$\begin{aligned} \hat F &= \sum_{i = 0}^{\infty} \sum_{j = 0}^{\infty} \binom{i + j}{i} 2^{i j} \frac{z^{i + j}}{(i + j)!} \\ &= \sum_{i = 0}^{\infty} \sum_{j = 0}^{\infty} \frac{2^{ij}}{i! j!} z^{i + j} \\ &= \sum_{i = 0}^{\infty} \sum_{j = 0}^{\infty} \frac{2^{-\binom{i}{2}}}{i!} \frac{2^{-\binom{j}{2}}}{j!} 2^{\binom{i + j}{2}} z^{i + j} \\ &= \sum_{n = 0}^{\infty} 2^{\binom{n}{2}} z^n \left[ [y^n] {\left( \sum_{i = 0}^{\infty} 2^{-\binom{i}{2}} \frac{y^i}{i!} \right)}^2 \right]\end{aligned}$$ 使用快速多项式乘法即可得到更优的复杂度，但在本题中这不是必要的。 考虑到每个连通二分图均有两种染色方案，令 $n$ 个点的连通二分图数量为 $g_n$，令 $\hat G = \mathbf{EGF}(g)$，特别地，规定 $g_0 = 0$。 则 $2 \hat G$ 即为点二染色连通二分图的指数型生成函数。 根据图计数理论有 $2 \hat G = \ln \hat F$。 同样地还有 $\hat C = \exp \hat G$。 即 $\displaystyle \hat C = \exp \frac{\ln \hat F}{2} = {\hat F}^{1 / 2}$。 两边求导移项得 $2 \hat C {\hat C}' = {\hat F}'$，比较系数后不难得到递推式。