和 sys 聊天的时候他说审题解会审到很多有趣的题目，然后我让他推荐几题，他跟我说了这题。
然而目前好像没看到这题有题解，难道是他拒绝了？
我觉得这题也不会很有趣吧，就是中规中矩的图计数问题，纯理性愉悦内容，比赛基本不考的那种。
本着服务大众的理念，来普及一下这些简单的图计数。
进入正题，要计数三种图（简单有标号无向图）：
- 连通图
- 欧拉图（即可以一笔画的图）
- 二分图
连通图
令 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. 新年的追逐战 中运用了类似方法求出此序列，可以查看他的 题解。
令 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}'，比较系数后不难得到递推式。