題目：

分析：

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

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

　　我們?nèi)タ紤]每條邊的貢獻(xiàn)

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

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

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

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

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

　　最壞的情況是$(1+x)^n$，這樣相當(dāng)于退化成$O(n^2logn)$，這是因?yàn)槊看文靡粋€(gè)低階多項(xiàng)式和一個(gè)高階多項(xiàng)式相乘很浪費(fèi)時(shí)間

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

轉(zhuǎn)載于:https://www.cnblogs.com/wmrv587/p/7481969.html

總結(jié)

以上是生活随笔為你收集整理的51nod 1907（多项式乘法启发式合并）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。