1.問題引入：

給定一個大小為n的集合a，求a的子集中有多少個的元素和為k。

（0）暴力：枚舉每個子集再求和，時間復雜度約為O（n*2^n），幾乎不可接受。

（OI生：這還不簡單，背包模板題）

（1）正解：構(gòu)建母函數(shù)

F(x)=(1+x^a1)(a+x^a1)……(1+x^an)

將其乘開，其中x^k項的系數(shù)即為答案。

（2）合理性證明：在乘開的同時，本質(zhì)上就是在枚舉所有的子集。

2.母函數(shù)的推導過程

（0）概念理解：x的意義

也許有人會跟你說x是沒有意義的，但是實際上，“x雖然不是一個具體的數(shù)，但并不抽象”。（請先三連）

（1）第一節(jié) 加法原理和乘法原理

以集合{1,2,3,4,5}為例。對于1，有選或不選共（1+1）種情況。同理，對于另外4個元素都是如此。因此，該集合的子集個數(shù)為

(1+1)(1+1)(1+1)(1+1)(1+1)=32

（包括空子集）

仔細觀察，這個式子與我們之前得出的母函數(shù)的形式幾乎完全一致：

本質(zhì)上，(1+1)……(1+1)就是

（選1或不選1）和（選2或不選2）……（選5或不選5）

同時，我們的母函數(shù)也是這樣如此構(gòu)造出來的。因此，這兩個式子同構(gòu)（這里是不是說得太簡略了一點）。

或 與 和，是有分配律的。

（Tips：這里的“或”與“和”與bool運算中的概念沒什么關系，只是名字差不多，切勿搞混了）

形象的展開：兩者同構(gòu)性得證（《數(shù)學頻道》）

但是，當我們把函數(shù)變?yōu)?/p>

F(x)=(1+a1)(1+a2)……(1+an)時，沒法算出來特定和的子集個數(shù)，而是所有子集的和（為什么答案是所有子集之和，我會在筆記最后說明）

原因分析：加法變成了乘法。

因此我們需要尋找一種方法，能夠?qū)⒊朔ㄟ\算變?yōu)榧臃ㄟ\算，“正巧，指數(shù)運算就有這種性質(zhì)”。也正是因此，x取任何數(shù)都無所謂。但是通過“x什么也不表示”來推導“x沒有意義”，是顛因為果的。

母函數(shù)出現(xiàn)了。

（2）不同的母函數(shù)（母函數(shù)的推廣）

將 “或” 與 “和” 推廣，運用結(jié)合律，可以得到如下的式子：

這與母函數(shù)形式及其相似。

原因：+ → 或 ，X → +1，x → 和，這三者是同構(gòu)的，只有名稱上的區(qū)別。

（這小寫的x怎么跟乘號一模一樣?。?/p>

新的問題：計算有3個元素的子集的個數(shù)

（注意，我們要用母函數(shù)的方式推導，而不是直接用組合數(shù)）

推導過程視頻說得已經(jīng)很清楚了。我簡單概括一下：先計算出每個數(shù)字的加入或不加入的影響，再以“和”運算（即乘法）連接，就得到了——

這也說明了，每一個組合數(shù)都是二項式的對應系數(shù)。

（3）數(shù)列

對于一個數(shù)列a，該數(shù)列的母函數(shù)為

P(x)=a0x^0+a1x^1+a2*x^2……

例：求斐波那契數(shù)列的通項公式：

得出F(x)=1/(1-x-x^2)，展開，得到其通項公式。

數(shù)列part：

用一個數(shù)列定義另一個數(shù)列（不推薦）：

以{bn}={S(a)n}來表示。這里S就不是一個什么數(shù)字了，而是類似于一個函數(shù)，稱作移位算子。

常見的有：

于是，嗯——

能不能像之前處理x那樣處理S呢？

可不可以安心地用麥克勞林展開呢？

對于任意的多項式，都有其唯一的逆。除以一個多項式，就相當于乘其逆（怎么有乘法逆元那味兒了）

因此，上面問題的答案均為是。

3.后記：

技術總結(jié)：一鍵三連。

結(jié)尾補充：

為什么對于任意的集合a，其中所有元素與1之和的乘積一定是a的所有子集的元素和呢？

對于第i個元素，不取時，貢獻為*1；當取時，貢獻即為*ai。

輕松得證。

（本蒟蒻第一次寫這么長的筆記，定然有錯誤，有不足，請各位dalao指教）