母函式，又稱生成函式，是ACM競賽中經常使用的一種解題演算法，常用來解決組合方面的題目，
使用母函式解決問題的方法稱為母函式方法，
1．母函式的原理
對于序列C0、C1、C2、…、Cn，建構式G(x)=C0+C1x+C2x2+…+Cnxn，稱G(x)為序列C0、C1、C2、…、Cn的母函式，
先來看一道例題，
例1 砝碼稱重
有1克、2克、3克和4克的砝碼各一枚，能稱出哪幾種重量？每種重量各有幾種可能方案？
4個不同重量的砝碼，最小可稱重1克，最多可稱重10克（1+2+3+4），由于資料量較小，我們可以直接列舉，列舉情況如表1所示，
表1 4個砝碼稱重
|
可稱重量 |
方案組合情況 |
方案數 |
|
1 |
1（表示選用重量為1克的砝碼，下同） |
1 |
|
2 |
2 |
1 |
|
3 |
1+2、3 |
2 |
|
4 |
1+3、4 |
2 |
|
5 |
1+4、2+3 |
2 |
|
6 |
1+2+3、2+4 |
2 |
|
7 |
1+2+4、3+4 |
2 |
|
8 |
1+3+4 |
1 |
|
9 |
2+3+4 |
1 |
|
10 |
1+2+3+4 |
1 |
下面，我們用母函式來解決這個問題，
1個1克砝碼可以看成1+x1，1表示不取，x1表示取一個，以下同理，
1個2克砝碼可以看成1+x2
1個3克砝碼可以看成1+x3
1個4克砝碼可以看成1+x4
構造母函式g(x)=(1+x1)(1+x2)(1+x3)(1+x4)
=1+x+x2+2x3+2x4+2x5+2x6+2x7+x8+x9+x10
在這個函式中，若指數表示可稱出重量，系數表示方案數，則可以看出重量為3克、4克、5克、6克、7克的方案數均有兩種，而重量為1克、2克、8克、9克、10克的方案只有1種，與表1中列舉情況吻合，
當然，例1這個問題比較簡單，因為，4個砝碼在稱重時，每個砝碼或選用或不用，因此，稱重組合有2*2*2*2=16種情況，可以很方便地列舉，如果砝碼種類再多一些，或每種砝碼的個數有多個，仍然采用列舉的話并不容易，
例如，我們設有1克、2克和3克的砝碼各3個，用這9個砝碼能稱出哪幾種重量？每種重量各有幾種可能方案？
9個3種重量的砝碼，最小可稱重1克，最多可稱重18克（1+2+3）*3=18，雖說資料量略有增大，我們還是先列舉，列舉情況如表2所示，
表2 9個砝碼稱重
|
可稱重量 |
方案組合情況 |
方案數 |
|
1 |
1 |
1 |
|
2 |
1+1、2 |
2 |
|
3 |
1+1+1、1+2、3 |
3 |
|
4 |
1+1+2、1+3、2+2 |
3 |
|
5 |
1+1+1+2、1+1+3、1+2+2、2+3 |
4 |
|
6 |
1+1+1+3、1+1+2+2、1+2+3、2+2+2、3+3 |
5 |
|
7 |
1+1+1+2+2、1+1+2+3、1+2+2+2、1+3+3、2+2+3 |
5 |
|
8 |
1+1+1+2+3、1+1+2+2+2、1+1+3+3、1+2+2+3、2+3+3 |
5 |
|
9 |
1+1+1+2+2+2、1+1+1+3+3、1+1+2+2+3、1+2+3+3、2+2+2+3、3+3+3 |
6 |
|
10 |
與8對應（9個砝碼去掉8中的每種情況，不一一列舉） |
5 |
|
11 |
與7對應 |
5 |
|
12 |
與6對應 |
5 |
|
13 |
與5對應 |
4 |
|
14 |
與4對應 |
3 |
|
15 |
與3對應 |
3 |
|
16 |
1+1+1+2+2+3+3+3、1+2+2+2+3+3+3 （與2對應） |
2 |
|
17 |
1+1+2+2+2+3+3+3 （與1對應） |
1 |
|
18 |
1+1+1+2+2+2+3+3+3 |
1 |
下面，我們用母函式來解決這個問題，
3個1克砝碼可以看成1+x1+x2+x3，1表示1個不取，x1表示取1個，x2表示取2個，x3表示取3個，以下同理，
3個2克砝碼可以看成1+x2+x4+x6
3個3克砝碼可以看成1+x3+x6+x9
構造母函式
g(x)=( 1+x1+x2+x3)( 1+x2+x4+x6)( 1+x3+x6+x9)
=1+x+2x2+3x3+3x4+4x5+5x6+5x7+5x8+6x9+5x10+5x11+5x12+4x13+3x14+3x15+2x16+x17+x18
可以看出，各項前的系數與表2中也是一一吻合的，
下面再看一道例題，
例2 擲骰子
擲兩只骰子（每只點數為1~6之一），可擲出的點數中，哪個點數的方案數最多？
顯然，兩只骰子可擲出的點數最小為2（1+1），最多為12（6+6），兩只骰子的點陣列合有6*6=36種，資料不大，可以列舉，例如：
若兩個骰子之和是2，只有1+1這1種可能，
……
若兩個骰子之和是6，有可能是1+5、5+1、2+4、4+2、3+3，一共5種可能，
若兩個骰子之和是7，有可能是1+6、6+1、2+5、5+2、3+4、4+3，一共6種可能，
……
若兩個骰子之和是12，只有6+6這1種可能，
如果有m只骰子呢？顯然不好列舉，
用母函式來解決，
用（x+x2+…+x6）表示一只骰子的投擲程序，兩只骰子的投擲可構造母函式
G(x)= （x+x2+…+x6）（x+x2+…+x6）
= x2+2x3+3x4+4x5+5x6+6x7+5x8+4x9+3x10+2x11+x12
在母函式中，xn項前面的系數就表示了和為n的方案數目，
如果骰子的數目為m，構造母函式為
G(x)= （x+x2+…+x6）m 即可，
由上面兩個例子我們可以看成，使用母函式來解決組合類計數問題時非常方便，通過構造母函式，我們得到冪級數形式的多項式，對于這個多項式我們不關心x的取值，也不關心其函式值，只需關心各項前的系數，
2．母函式的應用
母函式可分為很多種，包括普通母函式、指數母函式等，構造母函式的目的一般是為了解決某個特定的問題，因此選用何種母函式視序列本身的特性和問題的型別，
母函式有普通型的，也有指數型的，而我們通常在解題中碰到的大多是普通型的，指數型的較少，下面主要介紹普通型母函式的應用，
采用母函式解決問題時，主要有兩個關鍵問題要解決：（1）母函式的構造；（2）構造母函式時多項式相乘的實作，
下面我們先討論例1中母函式 g(x)=( 1+x1+x2+x3)( 1+x2+x4+x6)( 1+x3+x6+x9)的計算方法，
由于母函式g(x)的最高冪次項為x18（3+6+9=18），可以定義兩個陣列C1[19]和C2[19]，其中陣列C1保存多項式相乘后各項的系數，陣列元素C1[i]保存xi的系數；C2用于中間運算，
初始時，可以定義C1和C2的各元素初值均為0（除C1[0]=1外），表示初始時g(x)=1；也可以定義C1[0]=C1[1]=C1[2]=C1[3]=1，其余元素均為0，表示初始時g(x)= 1+x1+x2+x3，此時可以少進行一次多項式的相乘運算，
為了加深對模板程式的撰寫方法的理解，我們采用g(x)=1時的定義來闡述，
初始時，c1[0]=1，需進行三次相乘運算（可寫成回圈for (i=1;i<=3;i++) ），
當i=1時，進行第1次相乘運算，每次運算將陣列C1中的非零元素（即多項式中的有效項）與當前多項式相乘，結果暫存到陣列C2的對應陣列元素中，
第1次相乘運算完成1*（1+x1+x2+x3），
由于此時只有C1[0]=1，它要與多項式1+x1+x2+x3中的4項分別相乘
因此，C2[0+0]= C2[0+0]+C1[0]=1，C2[0+1]= C2[0+1]+C1[0]=1，
C2[0+2]= C2[0+2]+C1[0]=1，C2[0+3]= C2[0+3]+C1[0]=1，
運算完成后，將陣列C2的各元素值轉存到陣列C1中，且重新置陣列C2的各元素值為0，
此時，C1陣列中保存的多項式為1+x1+x2+x3
當i=2時，進行第2次相乘運算，第2次相乘運算完成（1+x1+x2+x3）*（1+x2+x4+x6），
由于此時，C1[0]=1，，它要與多項式1+x2+x4+x6中的4項分別相乘
因此，C2[0+0]= C2[0+0]+C1[0]=1，C2[0+2]= C2[0+2]+C1[0]=1，
C2[0+4]= C2[0+4]+C1[0]=1，C2[0+6]= C2[0+6]+C1[0]=1，
C1[1]=1，它也要與多項式1+x2+x4+x6中的4項分別相乘
因此，C2[1+0]= C2[1+0]+C1[1]=1，C2[1+2]= C2[1+2]+C1[1]=1，
C2[1+4]= C2[1+4]+C1[1]=1，C2[1+6]= C2[1+6]+C1[1]=1，
C1[2]=1，它也要與多項式1+x2+x4+x6中的4項分別相乘
因此，C2[2+0]= C2[2+0]+C1[2]=2，C2[2+2]= C2[2+2]+C1[2]=2，
C2[2+4]= C2[2+4]+C1[2]=2，C2[2+6]= C2[2+6]+C1[2]=1，
C1[3]=1，它也要與多項式1+x2+x4+x6中的4項分別相乘
因此，C2[3+0]= C2[3+0]+C1[3]=2，C2[3+2]= C2[3+2]+C1[3]=2，
C2[3+4]= C2[3+4]+C1[3]=2，C2[3+6]= C2[3+6]+C1[3]=1，
運算完成后，同樣將陣列C2的各元素值轉存到陣列C1中，且重新置陣列C2的各元素值為0，
此時，C1陣列中保存的多項式為1+x+2x2+2x3+2x4+2x5+2x6+2x7+x8+x9
當i=3時，進行第3次相乘運算，第3次相乘運算完成（1+x+2x2+2x3+2x4+2x5+2x6+2x7+x8+x9）*（1+x3+x6+x9），我們可以像上面一樣進行運算，類似寫40個賦值運算式即可，但我們不這樣，而是將上面的運算用回圈的方法寫出來，
for (int j=0; j<=18; j++)
if (C1[j]!=0) 對多項式中的有效項進行乘法運算
{
for (int k=0;k<=3;k++) // 當前有效項與多項式1+x3+x6+x9中每項相乘
C2[k*i+j]=C2[k*i+j]+C1[j];
}
for (int j=0;j<=18;j++)
{ c1[j]=c2[j]; c2[j]=0; }
按上面回圈進行運算后，C1陣列中保存的多項式為：
1+x+2x2+3x3+3x4+4x5+5x6+5x7+5x8+6x9+5x10+5x11+5x12+4x13+3x14+3x15+2x16+x17+x18
這樣，例1中的擴展問題我們可以寫成如下的程式，
#include <stdio.h>
int main(void)
{
int c1[19],c2[19];
for (int i=0;i<19;i++)
{
c1[i]=c2[i]=0;
}
c1[0]=1;
for (int i=1;i<=3;i++)
{
for (int j=0;j<=18;j++)
if (c1[j])
for (int k=0; k<=3;k++)
c2[j+k*i]+=c1[j];
for(int j=0;j<=18;j++)
{ c1[j]=c2[j]; c2[j]=0; }
}
for (int i=0;i<=18;i++)
printf("%d ",c1[i]);
return 0;
}
更一般的，例如，有n種物品，且第i個物品有ki個，現要在這n種物品中取出m件物品，求取法的方案總數，采用母函式時，可以列n個多項式相乘 (x^0+x^1+...x^k1)*(x^0+x^1+...x^k2)*…*(x^0+x^1+...x^kn)，第i個多項式表示對于第i件物品，可以有(x^0+x^1+...x^ki)中取法，將這些多項式相乘后，結果中x^m項的系數就是組合成m件物品的所有方案數，同樣可以套用上面的程式，
例3 正整數的拆分
問題描述
給定一個正整數N，可以將其拆分成若干個小于或等于N的正整數之和，例如，N=4是，存在5種拆分方法，列舉如下：
4 = 4;
4 = 3 + 1;
4 = 2 + 2;
4 = 2 + 1 + 1;
4 = 1 + 1 + 1 + 1;
注意：4 = 3 + 1和4 = 1 + 3是同一種拆分方法，不能重復計數，
輸入格式
輸入包括多個測驗資料，每個測驗資料為一個正整數N (1<=N<=120)，輸入N=0作為結束，
輸出格式
對每個測驗資料，輸出將其拆分的不同方案數，每個結果占1行，
輸入樣例
4
10
20
0
輸出樣例
5
42
627
（1）編程思路，
對于正整數N，其拆分式中可以包括1~N這N個數，這N個數最多取N個，可以重復取某個數，
數字1最多可取N個，可以看成1+x1+x2+x3+…+xN，1表示1個不取，x1表示取1個1，x2表示取2個1，x3表示取3個1，表示取N個1，以下同理，
數字2可以看成1+x2+x4+x6+…+xN/2
……
數字N可以看成1+x1，
構造母函式
g(x)=( 1+x1+x2+x3+…)( 1+x2+x4+x6+…)( 1+x3+x6+x9+…)……（1+x1）
（2）源程式，
#include <stdio.h>
int main(void)
{
int c1[121],c2[121];
int n,i,j,k;
while(scanf("%d",&n)!=EOF)
{
for (i=0;i<=n;i++)
{
c1[i]=c2[i]=0;
}
c1[0]=1;
for (i=1;i<=n;i++)
{
for (j=0;j<=n;j++)
if (c1[j])
for (k=0; j+k*i<=n;k++)
c2[j+k*i]+=c1[j];
for (j=0;j<=n;j++)
{ c1[j]=c2[j]; c2[j]=0; }
}
printf("%d\n",c1[n]);
}
return 0;
}
例4 找單詞（HDU 2082）
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
（1）編程思路，
本題同樣采用母函式來解決，定義陣列int a[27]，其中陣列元素a[0]~a[25]分別保存字母A~Z可供選取的個數；定義陣列int b[27]，其中陣列元素b[0]~b[25]分別保存字母A~Z的價值，顯然b[i]=i+1，
構造母函式g(x)=(1+xb[0]+x2*b[0]+x3*b[0]+…+xa[0]*b[0])
(1+xb[1]+x2*b[1]+x3*b[1]+…+xa[1]*b[1])
……(1+xb[25]+x2*b[25]+x3*b[25]+…+xa[25]*b[25])
運算時，只保留冪次不超過50的項的系數，最后將求得的x1~x50項的系數全部加起來就是問題的答案，
（2）源程式，
#include <stdio.h>
int main()
{
int a[27],b[27],c1[51],c2[51];
int n,i,j,k,sum;
scanf("%d",&n);
while (n--)
{
sum=0;
for (i=0;i<26;i++)
{
scanf("%d",&a[i]);
b[i]=i+1;
}
for (i=0;i<=50;i++)
c1[i]=c2[i]=0;
c1[0]=1;
for (i=0;i<26;i++)
{
for (j=0;j<=50;j++)
if (c1[j])
for (k=0;k+j<=50&&k<=a[i]*b[i];k+=b[i])
{
c2[k+j]+=c1[j];
}
for(j=0;j<=50;j++)
{ c1[j]=c2[j]; c2[j]=0; }
}
for(i=1;i<=50;i++)
sum+=c1[i];
printf("%d\n",sum);
}
return 0;
}
例5 Square Coins （HDU1398）
Problem Description
People in Silverland use square coins. Not only they have square shapes but also their values are square numbers. Coins with values of all square numbers up to 289 (=17^2), i.e., 1-credit coins, 4-credit coins, 9-credit coins, ..., and 289-credit coins, are available in Silverland.
There are four combinations of coins to pay ten credits:
ten 1-credit coins,
one 4-credit coin and six 1-credit coins,
two 4-credit coins and two 1-credit coins, and
one 9-credit coin and one 1-credit coin.
Your mission is to count the number of ways to pay a given amount using coins of Silverland.
Input
The input consists of lines each containing an integer meaning an amount to be paid, followed by a line containing a zero. You may assume that all the amounts are positive and less than 300.
Output
For each of the given amount, one line containing a single integer representing the number of combinations of coins should be output. No other characters should appear in the output.
Sample Input
2
10
30
0
Sample Output
1
4
27
（1）編程思路，
本題同樣采用母函式來解決，由于可選數為12~172共17種數，因此
構造母函式g(x)=(1+x1+x2*1+x3*1+…) (1+x1*2*2+x2*2*2+x3*2*2+…)…(1+x1*17*17)
運算時，只保留冪次不超過300的項的系數，
（2）源程式，
#include <stdio.h>
int main(void)
{
int c1[301],c2[301];
int n,i,j,k;
for (i=0;i<=300;i++)
{
c1[i]=c2[i]=0;
}
c1[0]=1;
for (i=1;i<=17;i++)
{
for (j=0;j<=300;j++)
if (c1[j])
for (k=0; j+k*i*i<=300;k++)
c2[j+k*i*i]+=c1[j];
for (j=0;j<=300;j++)
{ c1[j]=c2[j]; c2[j]=0; }
}
while(scanf("%d",&n)!=EOF && n!=0)
printf("%d\n",c1[n]);
return 0;
}
例6 分硬幣
問題描述
有面值分別為1~6的6種硬幣，小明和小紅收集了這樣的硬幣若干枚，現在他們要將這些硬幣按價值平分，但他們發現有時沒法平分，例如，現有面值為1的硬幣1枚，面值為3的硬幣1枚，面值為4的硬幣2枚，這4枚硬幣他們就無法平分，
輸入格式
輸入包括多組測驗資料，每組資料占1行，有n1, n2, ..., n6共6個非負整數，其中ni表示面值為i的硬幣的個數，每種硬幣最多不超過20000枚，
輸入資料以“0 0 0 0 0 0”作為結束，
輸出格式
對每組測驗資料，輸出一行“Collection #k:”，其中k為測驗資料組的序號；然后如果能平分，輸出“Can be divided.”，否則輸出“Can't be divided.”，每組輸出后加1空行，
輸入樣例
1 0 1 2 0 0
1 0 0 0 1 1
0 0 0 0 0 0
輸出樣例
Collection #1:
Can't be divided.
Collection #2:
Can be divided.
（1）編程思路，
有6種硬幣，每種硬幣的枚數保存到陣列int a[7]中，其中a[i]保存面值為i的硬幣的枚數，如果各硬幣枚數的同時計算出這些硬幣的總價值sum，如sum為奇數，顯然不能平分；若為偶數，則構造母函式，若母函式中冪次為sum/2的項的系數不為0，可以平分，否則不能平分，
構造母函式為G(x)=(1+x+x2+x3+…+xa[1])(1+x2+x4+…+x2∗a[2])…(1+x6+x12+…+x6*a[6])
由于題目中規定每種硬幣最多不超過20000枚，但實際上1~6的最小公倍數為60，因此我們將每種硬幣的個數對60取模，不影響判斷結果，但可大大提高效率，避免大量重復計算，
（2）源程式，
#include <stdio.h>
int main(void)
{
int a[7];
int c1[631],c2[631];
int n=0,i,j,k;
while (1)
{
int sum=0;
for (i=1;i<=6;i++)
{
scanf("%d",&a[i]);
a[i]=a[i]%60;
sum+=i*a[i];
}
if (a[1]+a[2]+a[3]+a[4]+a[5]+a[6]==0) break;
printf("Collection #%d:\n",++n);
if (sum%2!=0) printf("Can't be divided.\n\n");
else
{
sum=sum/2;
for (i=0;i<=sum;i++)
{
c1[i]=c2[i]=0;
}
c1[0]=1;
for (i=1;i<=6;i++)
{
for (j=0;j<=sum;j++)
if (c1[j])
for (k=0; k<=a[i] && j+k*i<=sum; k++)
c2[j+k*i]+=c1[j];
for (j=0;j<=sum;j++)
{ c1[j]=c2[j]; c2[j]=0; }
}
if (c1[sum]!=0) printf("Can be divided.\n\n");
else printf("Can't be divided.\n\n");
}
}
return 0;
}
例7 換硬幣
問題描述
在一次促銷活動中，你收到了一堆硬幣，這些硬幣有1分、5分、10分、25分和50分共5種，在結算聘請的促銷員的報酬時你準備用這些硬幣支付，
例如，要支付某促銷員11分，你可以有如下4中支付方式：1個10分和1個1分，2個5分和1個1分，1個 5分和6個1分，11個1分，
設某促銷員的報酬為N分，用這5種硬幣進行支付的總方案數為多少？為避免一個促銷員拿一把硬幣的麻煩，支付時限定給某一個促銷員的硬幣總個數不能超過100個，
輸入格式
輸入包括多行，每行為一個正整數N（N≤250），
輸出格式
對每行的正整數N，輸出采用5中硬幣支付的方案數，每個輸出結果占1行，
輸入樣例
11
26
輸出樣例
4
13
（1）編程思路，
本題是母函式的擴展應用，因為題目中要求支付時限定給某一個促銷員的硬幣總個數不能超過100個，因此在記錄組成價值N的不同方案數時，需要同時記錄所用到的總硬幣個數，
將一般使用時采用的一維陣列定義為二維陣列int c1[251][101]={0},c2[251][101]={0};，其中元素c1[i][j]表示用j枚硬幣組成價值為i的方案數，
（2）源程式，
#include <stdio.h>
int c1[251][101]={0},c2[251][101]={0};
// 元素c1[i][j]表示用j枚硬幣組成價值為i的方案數
int main(void)
{
int v[5]={1,5,10,25,50};
int i,j,k,l;
for (i=0;i<=100;i++)
c1[i][i]=1; // 全采用面值為1的硬幣，i枚硬幣組成價值為i的方案數為1
for (i=1;i<=4;i++)
{
for (j=0;j<=250;j++)
for (k=0;k+j<=250;k+=v[i])
for (l=0;l+k/v[i]<=100;l++)
c2[k+j][l+k/v[i]]+=c1[j][l];
for (j=0;j<=250;j++)
for (k=0;k<=100;k++)
{
c1[j][k]=c2[j][k];
c2[j][k]=0;
}
}
int n;
while (scanf("%d",&n)!=EOF)
{
int sum=0;
for (i=0;i<=100;i++)
sum+=c1[n][i];
printf("%d\n",sum);
}
return 0;
}
例8 硬幣湊數
問題描述
設有num1個1元硬幣，num2個2元硬幣，num5個5元硬幣，問你用這些硬幣不能湊出的最小面值是多少？（0不算）
輸入格式
輸入包括多組測驗用例，每組測驗用例包括3個正整數num1、num2和num5 (0<=num_i<=1000)，以輸入0 0 0表示結束，
輸出格式
輸出不能湊出的最小值，
輸入樣例
1 1 3
0 0 0
輸出樣例
4
（1）編程思路，
因為硬幣有1分、2分和5分三種情況，每種硬幣有個數限制，因此構造母函式為：
G(x)=(1+x+x2+x3+…+xnum1)(1+x2+x4+…+x2∗num2)(1+x5+x10+…+x5∗num5)
將母函式多項式展開后，xi項對應的系數就是組成面值為i的方案數，
然后從i=1開始遍歷xi項對應的系數，若某項xi的系數為0，則i就是不能湊出的最小值，
（2）源程式，
#include <stdio.h>
int main(void)
{
int num[4],money[5]={0,1,2,5},c[8005];
while(scanf("%d%d%d",&num[1],&num[2],&num[3])!=EOF)
{
if(num[1]==0 && num[2]==0 && num[3]==0)
break;
int maxVal=0,i,j,k;
for (i=0;i<8002;i++)
c[i]=0;
c[0]=1;
for (i=1;i<=3;i++)
{
maxVal+=num[i]*money[i];
for (j=0;j<=maxVal;j++)
for (k=0;k<=num[i] && j+k*money[i]<=maxVal;k++)
c[j+k*money[i]]+=c[j];
}
for (i=1;;i++)
if(c[i]==0)
{
printf("%d\n",i);
break;
}
}
return 0;
}
例9 水果拼盤
問題描述
果農老根一共種了N種水果，有蘋果，梨子，香蕉，西瓜……不但味道好吃，樣子更是好看，由于今年收成很好，老根獲得了大豐收，于是，很多人慕名而來，找老根買水果，
老根決定推出水果拼盤，每份水果拼盤由M個水果組成，拼盤中的每種水果，個數上有限制，既不能少于某個特定值，也不能大于某個特定值，
問老根一共可以推出多少種不同組合方案的水果拼盤？
注意：水果是以個為基本單位，不能夠再分，對于兩種方案，如果各種水果的數目都相同，則認為這兩種方案是相同的，
輸入格式
本題目包含多組測驗，請處理到檔案結束(EOF)，
每組測驗第一行包括兩個正整數N和M（0<N,M<=100）
接下來有N行水果的資訊，每行兩個整數A，B(0<=A<=B<=100)，表示至少要買該水果A個，至多只能買該水果B個，
輸出格式
對于每組測驗，在一行里輸出總共能夠賣的方案數，
題目資料保證這個答案小于10^9
輸入樣例
2 3
1 2
1 2
3 5
0 3
0 3
0 3
輸出樣例
2
12
（1）編程思路，
本題同樣采用母函式來解決，定義陣列int a[101]和int b[101]，其中陣列元素a[i]和b[i]分別保存第i種水果在拼盤中的最少數目和最多數目，
構造母函式g(x)=(xa[1]+xa[1]+1+xa[1]+2+…+xb[1]) (xa[2]+xa[2]+1+xa[2]+2+…+xb[2])
……(xa[n]+xa[n]+1+xa[n]+2+…+xb[n])
運算時，只保留冪次不超過M的項的系數，
（2）源程式，
#include <stdio.h>
int main(void)
{
int c1[101],c2[101];
int a[101],b[101];
int n,m,i,j,k;
while (scanf("%d%d",&n,&m)!=EOF)
{
for (i=1;i<=n;i++)
scanf("%d%d",&a[i],&b[i]);
for (i=0;i<=m;i++)
{
c1[i]=c2[i]=0;
}
c1[0]=1;
for (i=1;i<=n;i++)
{
for (j=0;j<=m;j++)
if (c1[j])
for (k=a[i]; k<=b[i] && j+k<=m; k++)
c2[j+k]+=c1[j];
for (j=0;j<=m;j++)
{ c1[j]=c2[j]; c2[j]=0; }
}
printf("%d\n",c1[m]);
}
return 0;
}
例10 質數和分解
選自洛谷題庫（https://www.luogu.com.cn/problem/P2563）
題目描述
任何大于 1 的自然數 n 都可以寫成若干個大于等于 2 且小于等于 n 的質數之和運算式(包括只有一個數構成的和運算式的情況)，并且可能有不止一種質數和的形式，例如，9 的質數和運算式就有四種本質不同的形式：
9 = 2 + 5 + 2 = 2 + 3 + 2 + 2 = 3 + 3 + 3 = 2 + 7 ，
這里所謂兩個本質相同的運算式是指可以通過交換其中一個運算式中參加和運算的各個數的位置而直接得到另一個運算式，
試編程求解自然數 n 可以寫成多少種本質不同的質數和運算式，
輸入格式
檔案中的每一行存放一個自然數 n(2 < n < 200) ，
輸出格式
依次輸出每一個自然數 n 的本質不同的質數和運算式的數目，
輸入樣例
2
200
輸出樣例
1
9845164
（1）編程思路，
先將200以內的所有質數求出來，保存到陣列prime中，然后用陣列中每個質數的取法作為一個多項式構造母函式，
構造的母函式為g(x)=(1+x2+x4+x6+…) (1+x3+x2*3+x3*3+…) (1+x5+x2*5+x3*5+…)
……(1+x199+x2*199+x3*199+…)
且求得的母函式中最高冪次項的冪次不超過200.
（2）源程式，
#include <stdio.h>
int isPrime(int n)
{
if (n<2) return 0;
for (int i=2;i<=n/2;i++)
if (n%i==0) return 0;
return 1;
}
int main(void)
{
int prime[201],c1[201],c2[201];
int i,j,k;
int cnt=0;
for (i=0;i<201;i++)
{
c1[i]=c2[i]=0;
if (isPrime(i)==1) prime[cnt++]=i;
}
c1[0]=1;
for (i=0;i<cnt;i++)
{
for (j=0;j<=200;j++)
if (c1[j])
for (k=0; j+k*prime[i]<=200;k++)
c2[j+k*prime[i]]+=c1[j];
for(j=0;j<=200;j++)
{ c1[j]=c2[j]; c2[j]=0; }
}
int n;
while(scanf("%d",&n)!=EOF)
printf("%d\n",c1[n]);
return 0;
}
在理解了母函式及其應用方法的基礎上，可以刷一下如下的OJ題目，這幾道題目均可以采用普通型母函式解決，
（1）Big Event in HDU （http://acm.hdu.edu.cn/showproblem.php?pid=1171）
（2）Crisis of HDU （http://acm.hdu.edu.cn/showproblem.php?pid=2110）
（3）悼念512汶川大地震遇難同胞——來生一起走
（http://acm.hdu.edu.cn/showproblem.php?pid=2189）
（4）小A點菜 （https://www.luogu.com.cn/problem/P1164）
（5）砝碼稱重 （https://www.luogu.com.cn/problem/P2347）
（5）Ant Counting （http://poj.org/problem?id=3046）
（6）Dollar Dayz （http://poj.org/problem?id=3181）
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/43036.html
標籤：C
上一篇：開機方案題解