生成函數

補一發生成函數 還挺有趣的。。生推各種通項公式(~~好像有的需要泰勒展開？~~

首先我們定義一個數列${a_1,a_2,a_3,a_4,a_5,a_6....}$考慮用函數表達一下這個數列。

則有 $f(x)=a_1+a_2x+a_3x^2+a_4x^3+a_5x^4+a_6x^5+...$

好像沒啥大用 那從一個小引子開始吧.

比如說 數列a這類物品選i件的方案數 例：a={1,1,1};隻能選不大于兩件。

無限長$b = \{1, 0, 0, 1, 0, 0, 1, 0, 0, 1...\}$表示B類物品隻能選3的倍數件的各個方案數。

那麼把$f(x)=1+x+x^2$和$g(x)=1+x^3+x^6+x^9+...$乘起來第i項的系數就表示a,b兩種物品共選i件的方案數..

可以FFT,就nlogn啦...(當然不這樣表示你也是可以看出要FFT的...

此時研究一個特殊的生成函數:$1+x+x^2+x^3+...$當$x\in (-1,1)$時生成函數又為$\frac{1}{1-x}$

等比數列求一發和即可。

那還有生成函數$1+3x+6x^2+10x^3+15x^4+...$這個東西求和之後為$\frac{1}{(1-x)^3}$

推廣一下$\frac{1}{(1-x)^k}$的生成函數的數列為$\sum_i^\infty C_{i+k-1}^{k-1}x^i$

隔闆法的簡單應用..

我說到這裡你一定還是很蒙蔽對吧，因為 我根本就沒有說明生成函數的定義。

什麼是生成函數：也叫母函數 是組合數學中尤其是計數方面的一個重要理論和工具。

生成函數有兩種 普通型生成函數和指數型生成函數 運用這種數學方法可以對程式的效率與速度有很大的提升。

大體上解決問題時 我們利用函數表達一個數列 然後進行化簡求和等用一個非常短的式子來代替一個數列。

然後進行數列相乘 進行快速運算的時候我們可以直接利用生成的這個函數來進行運算。

最後展開這個數列 然後求出需要的 第n項的系數即為答案。

展開的時候 我們回望來時的路 展開即可。

我想 生成函數的實質 是從代數->函數->表達式->通項這個過程過來的吧。

上題練練？

[bzoj 3028食物](https://www.lydsy.com/JudgeOnline/problem.php?id=3028)

直接暴力背包顯然不可做 組合計數能讓你起飛。

生成函數一發 化簡式子還是挺簡單的 最後的式子為 $\frac{x}{(1-x)^4}$

再展開回去 發現 第n項的系數為 C(n+2,3).n過大且p為10007 小 而且還是質數 使用盧卡斯定理即可.

盧卡斯定理：C(n,m)=C(n/p,m/p)%p$\cdot$C(n%p,m%p)%p;

恭喜你成功入門生成函數 23333

再來題目：

[luogu 2000拯救世界](https://www.luogu.com.cn/problem/P2000)

這道題目首先注意的是 不要讀錯題 有兩種方法 意味着 各種神石的使用方法都有兩種但是這兩種也是分開計算的。

n塊神石每塊可以隻能當作一種來用。很多限制條件 讓我利用生成函數了。

列出式子+化簡整個過程非常的簡單。最後的式子為$\frac{1}{(1-x)^5}$

不難發現我們要求得是 C(n+4,4); 再化簡一下 (n+4)(n+3)(n+2)(n+1)/24

3次NTT即可...ps:第一次用NTT寫高精 還怪好寫的。。。

再來一道：

[luogu 6078糖果 CEOI 2004](https://www.luogu.com.cn/problem/P6078)

答案要對2004取模但是題目上好像沒寫...列出來生成函數 發現後面還有一坨東西。

後面的東西考慮暴力展開 最多有2^n方項 和前面的相乘 顯然我們有p$\cdot$...一堆可以通過基礎的組合數變形的到 C(n+a-y,n);

于是乎複雜度為$2^n\cdot n$.值得一提的是 求組合數的時候不需要對n!取逆元這樣不友善。

因為n!和mod可能是不互質的 别提費馬小定理了 連擴充歐幾裡得都用不了 不存在逆元.

解決方法：我們讓mod$\cdot$n! 讓答案對這個東西取模 最後再除以n!即可得到答案.

當然你真的不太會的話可以嘗試約分不過複雜度要高一丢丢.

簡單說一下原理：大體上 我們取模後一般是質因子有可能被膜掉了考慮答案裡面有多少個n!如果恰好為mod的整數倍說明不管怎麼搞都是0.

如果沒有的話 那肯定還剩下若幹個n!除一下得到答案.

接下來是指數型生成函數簡稱EGF

和普通型生成函數唯一的差別是 配系數的時候 多除以了階乘這是為了簡便的解決排列問題而特意設立的.

其他的我也沒什麼好說網上都有下面開始習題時間.

[bzoj3456城市規劃](https://www.lydsy.com/JudgeOnline/problem.php?id=3456)

這道題我用分治FFT做到自閉...

考慮指數生成函數怎麼做？為什麼會是指數生成函數呢？下面圍繞這兩個問題進行讨論。注意下面都是讨論有标号的情況。

設 G(x) 表示一張任意無向圖的指數生成函數。

那麼其中第i項的系數為 $2^{C_{i}^{2}}$

設 F(x) 表示一張無向聯通圖的指數生成函數.設fi表示i個點的無向聯通圖的方案數。

那麼顯然F(x)的第i項的系數為$f_i$.

考慮組合意義 那麼顯然了 G(x)=e^{F(x)} 那麼求F(x) 對G取In即可。

我不太清楚。。按照我的了解 對于i這個系數 由i個F(x)相乘得到的對應的系數為G的系數。

為什麼會這樣 考慮到 由若幹個連通塊形成 是以有标号 是以每次選都存在方案數而對于同一個集合内的東西又無順序可言是以這樣是正确的。

遇到了一道非常好的題目 盡管腦殼有點疼..

[CF891E](https://www.luogu.com.cn/problem/CF891E)

我覺得算是一道品質很高 比較有難度的題目，(凡是期望題我tm的都不會做 自閉了.

每次随機一個值減一 答案增加其他值得乘積 求答案的期望...

我們不可能模拟整個局面算出來機率及答案 考慮初始整個局面的值為$\Pi_{i=1}^{n}a_i$

某個值減一後局面的值變成了$(a_x-1)\Pi_{i=1,i\not =x}^na_i$答案增加的量$\Pi_{i=1,i\not=x}^{n}a_i$

我們發現兩個局面做差即為答案的增加量 進行k次當然也就意味着初始局面減去最終局面。

但是我們如何求出最終局面的期望呢？

期望=機率*結果。機率為 $\frac{1}{n^k}$這樣我們隻需要對結果求和就可以了。

考慮一下結果是什麼 考慮每個位置最後被減去的數字為$b_i$那麼顯然有$\sum_{i=1}{n}b_i=k$

考慮到這種局面出現的次數(因為剛才是$n^k$是以每種局面可能會在這種情況之下出現多次。

假設每次選擇都是不同的$k!$最後再除以相同時候的方案數那麼出現的次數為$\frac{k!}{\Pi_{i=1}^{n}b_i!}$

對于這種局面的貢獻為 $\Pi_{i=1}^{n}(a_i-b_i)$

寫一下總式子$E=\frac{1}{n^k}\sum_{\sum b_i=k}\frac{k!}{\Pi_{i=1}^{n}b_i!}\Pi_{i=1}^{n}(a_i-b_i)$

簡單變換一下$E=\frac{1}{n^k}\sum_{\sum b_i=k}k!\Pi_{i=1}^{n}\frac{a_i-b_i}{b_i!}$

寫到這裡我們的EGF已經呼之欲出了 因為有條件$\sum b_i=k$和$\frac{k!}{\Pi_{i=1}^{n}b_i!}$

我們對于每個元素列出來其EGF那麼這兩個條件就可以輕松的滿足。

那麼對于一個元素的EGF $F_s(x)=\sum_{i=0}^{\infty}\frac{(a_s-i)x^i}{i!}$表示選擇減掉i個數時的答案

對面對于每個元素的EGF相乘 x^k的系數即為剛才上式的答案.

設$[x^k]f(x)$表示多項式f(x)的$x^k$項的系數.

原式=$\frac{k!}{n^k}\Pi_{i=1}^{n}\sum_{j=0}^{\infty}\frac{a_j-j}{j!}x^j$

化簡一波 $\frac{k!}{n^k}\Pi_{i=1}^{n}\sum_{j=0}^{\infty}(\frac{a_j}{j!}-\frac{j}{j!})x^j$

關注與後面的最後的式子當j==0時此項為0 當j不為0的時候j和j!進行約分。

是以上式為 $\frac{k!}{n^k}\Pi_{i=1}^{n}\sum_{j=0}^{\infty}(\frac{a_j\cdot x^j}{j!}-x\frac{x^j}{j!})$

用泰勒展開式進行展開$\frac{k!}{n^k}\Pi_{i=1}^{n}(a_ie^x-xe^x))$

$\frac{k!}{n^k}e^{nx}\Pi_{i=1}^{n}(a_i-x)$

最後的式子可以暴力展開長度不超過n 每次乘法複雜度O(n)

當然可以考慮分治求最後的那一項 不斷分治下去 在每一層做FFT.複雜度nlogn^2

至于那個$e^{nx}$這個東西也很好搞再變回去對于某個系數我們算對應的系數即可.

總複雜度 $n^2$...(這個時候寫剛才的FFT确實很麻煩 估計心态會爆炸...

有一個坑點是 這裡我們的EGF不是直接生成的 可以了解為我們先生成了OGF 由于下面還要除以一波$b_i$

是以形成了EGF 我們利用EGF的性質解題 最終還原成OGF 是以最後還是得除以一下!。

遇到幾種複合OGF函數的題目不太了解..然後走法都是要多項式exp 靠 我不會多項式exp 題解上說要求導。 全班估計隻有我一個人不會求導吧...不學了自閉了

[TJOI2015機率論](https://www.luogu.com.cn/problem/P3978)

這道題考驗的估計使我們的爆搜能力和發現規律的能力。

因為看起來是要推式子的題目 很難列出來生成函數。。

同時也很難化簡下去 是以這裡不講這種方法，經過我們的打表發現 $g_n=nf_{n-1}$其中g數組表示答案f數組表示二叉樹的個數。

考慮證明這個東西我想幾次都無法将其證明出來 而在_rqy的題解之中卻說道非常的簡單我覺得這很受打擊啊。。

我們考慮對于一顆n個點的二叉樹來說其有k個葉子節點 我們隻需要求出$\sum_{k}$即可。

考慮我們把這k個節點分别給去掉 那麼會生成k-1個二叉樹 顯然我們隻需要求出有多少個n-1個由這種方法生成的二叉樹即可。

我們發現一個二叉樹有n個位置都可以再挂一個兒子 這說明了每個二叉樹有n次機會成為一個n叉樹 綜上可以發現這種二叉樹的個數剛好為$nf_{n-1}$.

而f數組顯然是卡特蘭數 是以直接利用卡特蘭數的通項即可。

[SDOI2017 序列計數](https://www.luogu.com.cn/problem/P3702)

題目很好懂 但是我們發現為|p這個條件沒有任何的強力條件。