看了一个初赛题,题目大概是这样的:
由四个有标号的点构成的简单无向连通图的个数是:
感觉这应该是个经典问题。。就稍微写一下。

<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 就好了。只需要求导后求逆再积分就可以了。

Last modification:April 7th, 2020 at 10:14 pm
如果觉得我的文章对你有用,请随意赞赏