RainAir
My OI Blog
RainAir
「初赛」无向连通图计数

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

初赛上怎么解决

我们设 $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)$

快一点的做法

化简一下这个式子
$$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)$

更快一点的做法

考虑是否有别的方法能推导出方案。
首先我们考虑这样一种划分关系:设满足性质 $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 就好了。只需要求导后求逆再积分就可以了。

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/882
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

「初赛」无向连通图计数
看了一个初赛题,题目大概是这样的: 由四个有标号的点构成的简单无向连通图的个数是: 感觉这应该是个经典问题。。就稍微写一下。 初赛上怎么解决 我们设 $f_n$ 表示 $n$ 个点的连通图…
扫描二维码继续阅读
2019-10-15
标签
近期评论