【題解】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\)是快速幂求次方。