无向连通图计数

· · 个人记录

题目描述

求含有N个点的无向连通图的数量，对998244353取模。

数据范围

1\le N\le 10^5

题解

设f_n表示n个点的无向连通图的数量，g_n表示n个点的无向图的数量。

显然，g_n=2^{C_n^2}。

我们发现难以用g来表示f，于是就想到转换为用f来表示g。

枚举1号点所在连通块的大小i，并从2~n号点中选取i-1个点来与1号点组成连通块，剩下的点任意连边。这样就可以不重不漏地枚举到所有的包含n个点无向图。

写成式子就是：

g_n=\sum\limits_{i=1}^nC_{n-1}^{i-1}f_ig_{n-i}

两边除以(n-1)!：

\frac{g_n}{(n-1)!}=\sum\limits_{i=1}^n\frac{f_i}{(i-1)!}\frac{g_{n-i}}{(n-i)!}

不妨令f_0=0：

\frac{g_n}{(n-1)!}=\sum\limits_{i=0}^n\frac{f_i}{(i-1)!}\frac{g_{n-i}}{(n-i)!}

容易发现，这个式子是卷积的形式，于是构造多项式：

F(x)=\sum\limits_{i=1}^\infty\frac{f_i}{(i-1)!}x^i G(x)=\sum\limits_{i=1}^\infty\frac{g_i}{i!}x^i H(x)=\sum\limits_{i=1}^\infty\frac{g_i}{(i-1)!}x^i

也就是说：

H(x)=F(x)G(x)

因为g是已知的，所以G,H都是已知的。而现在我们要求的是F，于是移项得：

F(x)=G^{-1}(x)H(x)

此时求出G,H之后对G求逆，再乘上H就能得到F，进而就能求得f_n。