（因為我是用Word寫好了貼上來的，不知為何圖片點插入不管用，這是原文：http://www.wutianqi.com/?p=596，大家可以直接去這里看。）

前段時間寫了一篇《背包之01背包、完全背包、多重背包詳解》，看到支持的人很多，我不是大牛，只是一個和大家一樣學習的人，寫這些文章的目的只是為了一是希望讓大家學的輕松，二是讓自己復習起來更方便。

（PS：大家覺得我的文章還過的去就幫我支持下我的個人獨立博客---Tanky Woo的程序人生：http://www.wutianqi.com/，謝謝）

(以下內(nèi)容部分引至杭電ACM課件和維基百科)

在數(shù)學中，某個序列的母函數(shù)是一種形式冪級數(shù)，其每一項的系數(shù)可以提供關于這個序列的信息。使用母函數(shù)解決問題的方法稱為母函數(shù)方法。

母函數(shù)可分為很多種，包括普通母函數(shù)、指數(shù)母函數(shù)、L級數(shù)、貝爾級數(shù)和狄利克雷級數(shù)。對每個序列都可以寫出以上每個類型的一個母函數(shù)。構造母函數(shù)的目的一般是為了解決某個特定的問題，因此選用何種母函數(shù)視乎序列本身的特性和問題的類型。

這里先給出兩句話，不懂的可以等看完這篇文章再回過頭來看：

"把組合問題的加法法則和冪級數(shù)的t的乘冪的相加對應起來"

"母函數(shù)的思想很簡單—就是把離散數(shù)列和冪級數(shù)一一對應起來，把離散數(shù)列間的相互結合關系對應成為冪級數(shù)間的運算關系，最后由冪級數(shù)形式來確定離散數(shù)列的構造

由此可以看出:

1. x的系數(shù)是a₁,a₂,…a_{n的單個組合的全體。}

2. x²的系數(shù)是a₁,a₂,…a₂的兩個組合的全體。

………

n. xⁿ的系數(shù)是a₁,a₂,….a_n的n個組合的全體（只有1個）。

由此得到

母函數(shù)的定義：

對于序列a₀，a₁，a₂，…構造一函數(shù)：

稱函數(shù)G(x)是序列a₀，a₁，a₂，…的母函數(shù)

這里先給出2個例子，等會再結合題目分析：

第一種：

有1克、2克、3克、4克的砝碼各一 枚，能稱出哪幾種重量？每種重量各有幾種可能方案？ 

考慮用母函數(shù)來接吻這個問題：

我們假設x表示砝碼，x的指數(shù)表示砝碼的重量，這樣：

1個1克的砝碼可以用函數(shù)1+x表示，

1個2克的砝碼可以用函數(shù)1+x²表示，

1個3克的砝碼可以用函數(shù)1+x³表示，

1個4克的砝碼可以用函數(shù)1+x⁴表示，

上面這四個式子懂嗎？

我們拿1+x²來說，前面已經(jīng)說過，x表示砝碼，x的指數(shù)表示重量，即這里就是一個質(zhì)量為2的砝碼，那么前面的1表示什么？1代表重量為2的砝碼數(shù)量為0個。（理解！）

不知道大家理解沒，我們這里結合前面那句話：

"把組合問題的加法法則和冪級數(shù)的t的乘冪的相加對應起來"

1+x²表示了兩種情況：1表示質(zhì)量為2的砝碼取0個的情況，x²表示質(zhì)量為2的砝碼取1個的情況。

這里說下各項系數(shù)的意義：

在x前面的系數(shù)a表示相應質(zhì)量的砝碼取a個，而1就表示相應砝碼取0個，這里可不能簡單的認為相應砝碼取0個就該是0*x²(想下為何？結合數(shù)學式子)。

Tanky　Woo 的程序人生：http://www.wutianqi.com/

所以，前面說的那句話的意義大家可以理解了吧？

幾種砝碼的組合可以稱重的情況，可以用以上幾個函數(shù)的乘積表示：

(1+x)(1+x²)(1+x³)(1+x⁴)

=(1+x+x²+x³)(1+x³+x⁴+x⁷)

=1+x+x²+2x³+2x⁴+2x⁵+2x⁶+2x⁷+x⁸+x⁹+x¹⁰  

從上面的函數(shù)知道：可稱出從1克到10克，系數(shù)便是方案數(shù)。（！！！經(jīng)典！！！）

    例如右端有2x⁵ 項，即稱出5克的方案有2：5=3+2=4+1；同樣，6=1+2+3=4+2；10=1+2+3+4。

    故稱出6克的方案有2，稱出10克的方案有1 。

接著上面，接下來是第二種情況：

求用1分、2分、3分的郵票貼出不同數(shù)值的方案數(shù)：

大家把這種情況和第一種比較有何區(qū)別？第一種每種是一個，而這里每種是無限的。

以展開后的x⁴為例，其系數(shù)為4，即4拆分成1、2、3之和的拆分數(shù)為4；

即 ：4=1+1+1+1=1+1+2=1+3=2+2

這里再引出兩個概念整數(shù)拆分和拆分數(shù)：

所謂整數(shù)拆分即把整數(shù)分解成若干整數(shù)的和（相當于把n個無區(qū)別的球放到n個無標志的盒子，盒子允許空，也允許放多于一個球）。

整數(shù)拆分成若干整數(shù)的和，辦法不一，不同拆分法的總數(shù)叫做拆分數(shù)。

現(xiàn)在以上面的第二種情況每種種類個數(shù)無限為例，給出模板：

我們來解釋下上面標志的各個地方：

①  、首先對c1初始化，由第一個表達式(1+x+x²+..xⁿ)初始化，把質(zhì)量從0到n的所有砝碼都初始化為1.

②  、 i從2到n遍歷，這里i就是指第i個表達式，上面給出的第二種母函數(shù)關系式里，每一個括號括起來的就是一個表達式。

③、j 從0到n遍歷，這里j就是只一個表達式里第j個變量，比如在第二個表達式里：(1+x²+x⁴....)里，第j個就是x^2*j.

③  k表示的是第j個指數(shù)，所以k每次增i（因為第i個表達式的增量是i）。

④  、把c2的值賦給c1,而把c2初始化為0，因為c2每次是從一個表達式中開始的

咱們趕快趁熱打鐵，來幾道題目：

（相應題目解析均在相應的代碼里分析）

1.  題目：http://acm.hdu.edu.cn/showproblem.php?pid=1028

代碼：http://www.wutianqi.com/?p=587

這題大家看看簡單不？把上面的模板理解了，這題就是小Case!

看看這題：

2.  題目：http://acm.hdu.edu.cn/showproblem.php?pid=1398

代碼：http://www.wutianqi.com/?p=590

要說和前一題的區(qū)別，就只需要改2個地方。 在i遍歷表達式時（可以參考我的資料---《母函數(shù)詳解》），把i<=nNum改成了i*i<=nNum,其次在k遍歷指數(shù)時把k+=i變成了k+=i*i; Ok,說來說去還是套模板~~~

3.  題目：http://acm.hdu.edu.cn/showproblem.php?pid=1085

代碼：http://www.wutianqi.com/?p=592

這題終于變化了一點，但是萬變不離其中。

大家好好分析下，結合代碼就會懂了。

4.  題目：http://acm.hdu.edu.cn/showproblem.php?pid=1171

代碼：http://www.wutianqi.com/?p=594

還有一些題目，大家有時間自己做做：

HDOJ：1709，1028、1709、1085、1171、1398、2069、2152

附：

1.在維基百科里講到了普通母函數(shù)、指數(shù)母函數(shù)、L級數(shù)、貝爾級數(shù)和狄利克雷級數(shù)：

http://zh.wikipedia.org/zh-tw/%E6%AF%8D%E5%87%BD%E6%95%B0

2．Matrix67大牛那有篇文章：什么是生成函數(shù)：

http://www.matrix67.com/blog/archives/120

3.大家可以看看杭電的ACM課件的母函數(shù)那篇，我這里的圖片以及一些內(nèi)容都引至那。

文章暫時講完后，隨著以后更深入的了解，我會把資料繼續(xù)完善，供大家一起學習探討。(我的博客—Tanky Woo的程序人生：www.wutianqi.com ，大家?guī)臀抑С窒虏┛桶桑绻蠹矣袉栴}或者資料里的內(nèi)容有錯誤，可以留言給出，謝謝您的支持。)

Tanky Woo

原創(chuàng)文章，轉(zhuǎn)載請注明出處：http://www.wutianqi.com/?p=596

 我已把文章在csdn上上傳了，大家可以去下載。(Word)

鏈接：http://download.csdn.net/source/2591324

=========================================================================================