【题解】POJ#1737 Connected Graph（计数）

​​http://www.fzoi.top/problem/3143​​

给定\(n\)个有编号的点，求可以组成多少个不同的连通图。多组询问（仅在FZOJ上：答案对\(10^9+7\)取模）。

\(n\le 50\)

直接算并不好算ps:但是好像有人硬刚出来了，考虑转化为 图的总数 - 不合法数量。

设\(f[i]\)表示\(i\)个点能组成的合法数量。

考虑计算有\(i\)个点时不合法的方案数，我们枚举 1 号点所在连通块的大小\(j\)，这\(j\)个点是合法的，而剩下\(i-j\)个点可以随意连边。所以不合法的方案数为\(\sum\limits_{j=1}^{i-1} f[j]\times \binom{i-1}{j-1}\times 2^{\frac{(i-j)(i-j-1)}{2}}\)。

其中\(\binom{i-1}{j-1}\)是从除 1 外的点中选出 j-1 个点构成连通块的方案数。

时间复杂度\(O(n^2\ log\ n)\)，\(log\)是快速幂求次方。