PKU1737-Connected Graph

題目：http://poj.org/problem?id=1737
男人八題之一
組合數學問題，給一個具n個節點(1...50)的無向圖
問有多少種不同的連結方法可以使其成為連通圖
每個點視為相異(可以想像編號1...n，同構圖編號序不同也當成不同)


程式碼：http://codepad.org/UQCFG5jo (1000MS壓時過，大數很醜)
程式碼：http://codepad.org/wBpxZBbt (範圍只支持n=1...8，公式示意用code)
我本來想朝著「大連通塊拆成兩個小連通塊」這種方向來檢討
但是越想越頭痛(事後AC看了網上解說也不懂這個思路)
於是異想天開地：補集有沒有效呢？

居然「不連通圖」的方法數竟容易理解許多

我們設節點數n，f(n)是連通方法數、f'(n)是不連通方法數、g(n)是總方法數
首先很顯然的：f(n)=g(n)-f'(n)
總共可能的圖數也很容易：g(n)=2^(n*(n-1)/2)
接下來怎麼求不連通方法數呢？

「這樣的圖一定具有兩個以上的連通塊」

以求出f(7)舉例說明，我們假想點有編號1...n、任取編號1的點當成中心來考量
(1)點1所在的連通塊只有自己一個點
(2)點1所在的連通塊有2個點
(3)點1所在的連通塊有3個點
(4)點1所在的連通塊有4個點
(5)點1所在的連通塊有5個點(6)點1所在的連通塊有6個點
顯然(1)~(6)這六種情形的聯集恰恰好就是我們需要的f'(7)
所以總結起來公式是這樣的：
f'(n) = sigma(k=1...n-1) f(k) * C(n-1,k-1) * g(n-k)
加總所有當點1所在聯通塊有1~n-1個點的所有情形數
該k聯通塊的可能方法數f(k) × 屬於這k集合點數的可能性C(n-1,k-1) × 剩下的點隨便連

最後注意大數運算不能太肥、盡量預處理、記憶化，此題得解