轉(zhuǎn)載至

http://blog.csdn.net/xiaofei_it/article/details/17042651

母函數(shù)，又稱生成函數(shù)，是ACM競賽中經(jīng)常使用的一種解題算法，常用來解決組合方面的題目。

本文講解母函數(shù)，但不講解該算法的基礎理論。讀者隨便找一本組合數(shù)學教材便可找到相應的內(nèi)容，或者直接在網(wǎng)上搜索一下。

母函數(shù)通常解決類似如下的問題：

給5張1元，4張2元，3張5元，要得到15元，有多少種組合？

某些時候會規(guī)定至少使用3張1元、1張2元、0張5元。

某些時候會規(guī)定有無數(shù)張1元、2元、5元。

……

解題過程

解題時，首先要寫出表達式，通常是多項的乘積，每項由多個x^y組成。如(1+x+x^2)(1+x^4+x^8)(x^5+x^10+x^15)。

通用表達式為

(x^(v[0]*n1[0])+x^(v[0]*(n1[0]+1))+x^(v[0]*(n1[0]+2))+...+x^(v[0]*n2[0]))(x^(v[1]*n1[1])+x^(v[1]*(n1[1]+1))+x^(v[1]*(n1[1]+2))+...+x^(v[1]*n2[1]))...(x^(v[K]*n1[K])+x^(v[K]*(n1[K]+1))+x^(v[K]*(n1[K]+2))+...+x^(v[K]*n2[K]))

K對應具體問題中物品的種類數(shù)。

v[i]表示該乘積表達式第i個因子的權(quán)重，對應于具體問題的每個物品的價值或者權(quán)重。

n1[i]表示該乘積表達式第i個因子的起始系數(shù)，對應于具體問題中的每個物品的最少個數(shù)，即最少要取多少個。

n2[i]表示該乘積表達式第i個因子的終止系數(shù)，對應于具體問題中的每個物品的最多個數(shù)，即最多要取多少個。

對于表達式(1+x+x^2)(x^8+x^10)(x^5+x^10+x^15+x^20)，v[3]={1,2,5}，n1[3]={0,4,1}，n2[3]={2,5,4}。

解題的關(guān)鍵是要確定v、n1、n2數(shù)組的值。

通常n1都為0，但有時候不是這樣。

n2有時候是無限大。

之后就實現(xiàn)表達式相乘，從第一個因子開始乘，直到最后一個為止。此處通常使用一個循環(huán)，循環(huán)變量為i。每次迭代的計算結(jié)果放在數(shù)組a中。計算結(jié)束后，a[i]表示權(quán)重i的組合數(shù)，對應具體問題的組合數(shù)。

循環(huán)內(nèi)部是把每個因子的每個項和a中的每個項相乘，加到一個臨時的數(shù)組b的對應位（這里有兩層循環(huán)，加上最外層循環(huán)，總共有三層循環(huán)），之后就把b賦給a。

這些過程通常直接套用模板即可。

通用模板

下面我直接給出通用模板：

如果n2是無窮，那么第二層循環(huán)條件j<=n2[i]可以去掉。

如何提高效率？

用一個last變量記錄目前最大的指數(shù)，這樣只需要在0..last上進行計算。

這里給出第二個模板：

[cpp] view%20plain copy //初始化a，因為有l(wèi)ast，所以這里無需初始化其他位  a[0]=1;  int last=0;  for (int i=0;i<K;i++)  {      int last2=min(last+n[i]*v[i],P);//計算下一次的last      memset(b,0,sizeof(int)*(last2+1));//只清空b[0..last2]      for (int j=n1[i];j<=n2[i]&&j*v[i]<=last2;j++)//這里是last2          for (int k=0;k<=last&&k+j*v[i]<=last2;k++)//這里一個是last，一個是last2              b[k+j*v[i]]+=a[k];      memcpy(a,b,sizeof(int)*(last2+1));//b賦值給a，只賦值0..last2      last=last2;//更新last  }  例題

下面看幾個例題。

一、hdu 1085和hdu 1171兩題套用了第二個模板，省略了代碼中二三層循環(huán)里關(guān)于last2的條件（其實也可以加上）。

詳見：

hdu 1085：http://blog.csdn.net/xiaofei_it/article/details/17041467

hdu 1171：http://blog.csdn.net/xiaofei_it/article/details/17041709

二、hdu 1398套用了第一個模板，因為n2中每一項為無窮大，所以n2數(shù)組就省略了。

詳見：

hdu 1398：http://blog.csdn.net/xiaofei_it/article/details/17041815

三、hdu 2079、hdu 2082和hdu 2110三題直接套用了第二個模板。

詳見：

hdu 2079：http://blog.csdn.net/xiaofei_it/article/details/17042045

hdu 2082：http://blog.csdn.net/xiaofei_it/article/details/17042253

hdu 2110：http://blog.csdn.net/xiaofei_it/article/details/17042421

另外，至于什么時候用第一個模板，什么時候用第二個模板，就看題目規(guī)模。

通常情況下，第一個模板就夠用了，上面的那些用第二個模板的題目用第一個模板同樣能AC。

但如果數(shù)據(jù)規(guī)模比較大（通常不會有這種情況），就要使用第二個模板了。

以上題目n1均為0。

四、hdu 2152是一道n1不為0的題目，我在這里分別套用第一個和第二個模板解題。

詳見：

hdu 2152：http://blog.csdn.net/xiaofei_it/article/details/17042497