51nod 1907（多項式乘法啟發式合并）

題目：

分析：

　　對于一個確定的生成子圖，很明顯是在一個連通塊上走，走完了再跳到另一個連通塊上，假設連通塊個數為cnt，那么答案一定是$min(a_{cnt-1},a_cnt,..,a_{n-1})$

?　 ?那現在的問題就是如何求出對于原圖而言，連通塊個數分別為1,2..n的生成子圖的個數

　　我們去考慮每條邊的貢獻

　　在一個仙人掌上只有樹邊和回路上的邊，對于樹邊如果刪除那么肯定連通塊個數+1，對于回路上的邊，刪除一條邊不影響，再后面每刪除一條邊連通塊個數+1

　　我們可以寫出它們的生成函數，然后乘起來

　　對于樹邊的生成函數明顯是$1+x$

　　對于長度為k的回路，生成函數是$1+\binom{k}{1}+\binom{k}{2}x+\binom{k}{3}x^2+...+\binom{k}{k}x^{k-1}$

　　然后將它們都乘起來就行了，但這樣會TLE

　　最壞的情況是$(1+x)^n$，這樣相當于退化成$O(n^2logn)$，這是因為每次拿一個低階多項式和一個高階多項式相乘很浪費時間

　　可以采取啟發式合并，類似合并果子，每次取階數最小的兩個多項式進行NTT相乘，這樣時間復雜度就是$O(nlog^2n)$的了