HDU2082母函數模板題

Problem Description 假設有x1個字母A， x2個字母B,..... x26個字母Z，同時假設字母A的價值為1，字母B的價值為2,..... 字母Z的價值為26。那麼，對於給定的字母，可以找到多少價值<=50的單詞呢？單詞的價值就是組成一個單詞的所有字母的價值之和，比如，單詞ACM的價值是1+3+14=18，單詞HDU的價值是8+4+21=33。(組成的單詞與排列順序無關，比如ACM與CMA認為是同一個單詞）。

Input 輸入首先是一個整數N，代表測試實例的個數。
然後包括N行數據，每行包括26個<=20的整數x1,x2,.....x26.

Output 對於每個測試實例，請輸出能找到的總價值<=50的單詞數,每個實例的輸出占一行。
Sample Input 2 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 2 6 2 10 2 2 5 6 1 0 2 7 0 2 2 7 5 10 6 10 2 10 6 1 9
Sample Output 7 379297
Source

知識點:

母函數(生成函數):

生成函數有普通型生成函數和指數型生成函數兩種(本題是普通型)。

形式上，普通型母函數用於解決多重集的組合問題，

指數型母函數用於解決多重集的排列問題。

母函數還可以解決遞歸數列的通項問題（例如使用母函數解決斐波那契數列，Catalan數的通項公式）。

普通母函數：

構造母函數G(x), G(x) = a0 + a1*x + a2*+ a3*+....+ an*， 則稱G(x)是數列a0,a1…an的母函數。

通常普通母函數用來解多重集的組合問題，其思想就是構造一個函數來解決問題，一般過程如下：

1.建立模型：物品n種,每種數量分別為k1,k2,..kn個，每種物品又有一個屬性值p1,p2,…pn,(如本題的字母價值)，

求屬性值和為m的物品組合方法數。（若數量ki無窮 也成立，即對應下面式子中第ki項的指數一直到無窮）

2.構造母函數：G(x)=(1++…)(1+++…)…(1+++…) （一）

=a0 + a1*x + a2*+ a3*+....+ akk* (設kk=k1·p1+k2·p2+…kn·pn) （二）

G(x)含義： ak 為屬性值和為k的組合方法數。

母函數利用的思想：

1.把組合問題的加法法則和冪級數的乘冪對應起來。

2.把離散數列和冪級數對應起來，把離散數列間的相互結合關系對應成為冪級數間的運算關系，最後由冪級數形式來

確定離散數列的構造。

代碼實現：

求G(x)時一項一項累乘。先令G=1=(1+0*x+0*+…0*),再令G=G*(1++…)得到形式(二)的式子…最後令G=G*(1+++…)。

 

題解：

1.建模：物品(字母)26種，每種數量x1,x2…x26，屬性值為1,2,3..26,求屬性值和<=50的組合方法數。

2.G(x)=(1++…)(1+++…)…(1++…)

#include 
#include 
#include 
#include 


using namespace std;
int c1[100],c2[100];
int a[30];
int main()
{
int t;
cin >> t;
while(t --)
{
for(int i = 1; i <= 26; i ++)
cin >> a[i];
memset(c1,0,sizeof(c1));
memset(c2,0,sizeof(c2));
c1[0] = 1;///初始化
for(int i = 1; i <= 26; i ++)///對應26個多項式
{
for(int j = 0; j <= 50; j ++) ///每個多項式中對應的指數
for(int k = 0; k <= a[i] && k * i + j <= 50; k ++) ///k*i表示被乘多項式各項的指數
c2[j + k * i] += c1[j];
memcpy(c1,c2,sizeof(c2));///c2數組的值賦值給c1
memset(c2,0,sizeof(c2));///c2初始化
}
///累加
int sum = 0;
for(int i = 1; i <= 50; i ++)
sum += c1[i];
cout << sum << endl;
}
return 0;
}