看了一个初赛题，题目大概是这样的：
由四个有标号的点构成的简单无向连通图的个数是：
感觉这应该是个经典问题。。就稍微写一下。
<h2>初赛上怎么解决</h2>
我们设 $f_n$ 表示 $n$ 个点的连通图的数量，转移只需要考虑计算出不连通的数量。可以枚举一号点所在的连通块大小计算。
$$f_n = 2^{\binom n 2} - \sum_{i=1}^{n-1} \binom{n-1}{i-1}f_i2^{\binom {n-i} {2}}$$
直接手推前四项就好了，复杂度 $O(n^2)$
<h2>快一点的做法</h2>
化简一下这个式子
$$f_n = 2^{\binom n 2}-(n-1)!\sum_{i=1}^{n-1} \frac{f_i}{(i-1)!}\frac{2^{\binom {n-i} 2}}{(n-i)!}$$
令 $a_i = \frac{f_i}{(i-1)!},b_i = \frac{2^{\binom i 2}}{i!}$
式子变为
$$f_n = 2^{\binom n 2}-(n-1)!\sum_{i=1}^{n-1} a_ib_{n-i}$$
分治 FFT 即可，时间复杂度 $O(nlog^2n)$
<h2>更快一点的做法</h2>
考虑是否有别的方法能推导出方案。
首先我们考虑这样一种划分关系：设满足性质 $A$ 的集合为 $S_A$，元素有标号，如果 $S_B$ 是由若干个 $S_A$ 组成的集合，我们设 $a_i$ 表示大小为 $i$ 的 $S_A$ 个数， $b_i$ 表示大小为 $i$ 的 $S_B$ 个数，他们的EGF：
$$A = \sum_{i=0}^{\infty} a_i\frac{x^i}{i!}$$
$$B = \sum_{i=0}^{\infty} b_i\frac{x^i}{i!}$$
考虑枚举 $B$ 是由哪些 $A$ 划分而来，（由于有序所以使用EGF）可以得到
$$B = \sum_{i=0}^{\infty}\frac{A^i(x)}{i!} = e^{A}$$
对应到这个题中：我们令连通图代表性质 $A$，那么若干连通图组成的集合就是任意的无向图，任意无向图组成的集合是 $S_B$，那么我们可以得到 $e^A = B$
两边取 ln 可以得到 $A = lnB$。可以发现 $b_i = 2^{\binom i 2}$，所以我们只需要对 $B$ 求 ln 就好了。只需要求导后求逆再积分就可以了。
2 comments
多项式求逆可以做到1log吧
%%%dalao教我分治FFT%%%