本篇文章前半部分的母函数定义及讲解，和后面的题目推荐，
在数学中，某个序列的母函数(Generating function，又称生成函数)是一种形式幂级数，其每一项的系数可以提供关于这个序列的信息。使用母函数解决问题的方法称为母函数方法。
母函数可分为很多种，包括普通母函数、指数母函数、L级数、贝尔级数和狄利克雷级数。对每个序列都可以写出以上每个类型的一个母函数。构造母函数的目的一般是为了解决某个特定的问题，因此选用何种母函数视乎序列本身的特性和问题的类型。
这里先给出两句话，不懂的可以等看完这篇文章再回过头来看：
1.“把组合问题的加法法则和幂级数的乘幂对应起来”
2.“母函数的思想很简单 — 就是把离散数列和幂级数一 一对应起来，把离散数列间的相互结合关系对应成为幂级数间的运算关系，最后由幂级数形式来确定离散数列的构造. “
我们首先来看下这个多项式乘法：
母函数图(1)
由此可以看出:
1.x的系数是a1,a2,…an 的单个组合的全体。
2. x^2的系数是a1,a2,…a2的两个组合的全体。
………
n. x^n的系数是a1,a2,….an的n个组合的全体（只有1个）。
进一步得到：
母函数图(2)
母函数的定义
对于序列a0，a1，a2，…构造一函数：
母函数图(3)
称函数G(x)是序列a0，a1，a2，…的母函数。
这里先给出2个例子，等会再结合题目分析：
第一种：
该题在下面给出代码。底下的第三个代码。
有1克、2克、3克、4克的砝码各一枚，能称出哪几种重量？每种重量各有几种可能方案？
考虑用母函数来解决这个问题：
我们假设x表示砝码，x的指数表示砝码的重量，这样：
1个1克的砝码可以用函数1+1*x^1表示，
1个2克的砝码可以用函数1+1*x^2表示，
1个3克的砝码可以用函数1+1*x^3表示，
1个4克的砝码可以用函数1+1*x^4表示，
上面这四个式子懂吗？
我们拿1+x^2来说，前面已经说过，x表示砝码，x的指数表示砝码的重量！初始状态时，这里就是一个质量为2的砝码。
那么前面的1表示什么？按照上面的理解，1其实应该写为：1*x^0,即1代表重量为2的砝码数量为0个。
所以这里1+1*x^2 = 1*x^0 + 1*x^2，即表示2克的砝码有两种状态，不取或取，不取则为1*x^0，取则为1*x^2
不知道大家理解没，我们这里结合前面那句话：
“把组合问题的加法法则和幂级数的乘幂对应起来“
接着讨论上面的1+x^2，这里x前面的系数有什么意义？
这里的系数表示状态数(方案数)
1+x^2，也就是1*x^0 + 1*x^2，也就是上面说的不取2克砝码，此时有1种状态；或者取2克砝码，此时也有1种状态。(分析！)
所以，前面说的那句话的意义大家可以理解了吧？
几种砝码的组合可以称重的情况，可以用以上几个函数的乘积表示：
(1+x)(1+x^2)(1+x^3)(1+x^4)
=(1+x+x^2+x^4)(1+x^3+^4+x^7)
=1 + x + x^2 + 2*x^3 + 2*x^4 + 2*x^5 + 2*x^6 + 2*x^7 + x^8 + x^9 + x^10
从上面的函数知道：可称出从1克到10克，系数便是方案数。（！！！经典！！！）
例如右端有2^x^5 项，即称出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分的邮票贴出不同数值的方案数：
大家把这种情况和第一种比较有何区别？第一种每种是一个，而这里每种是无限的。
母函数图(4)
以展开后的x^4为例，其系数为4，即4拆分成1、2、3之和的拆分方案数为4；
即 ：4=1+1+1+1=1+1+2=1+3=2+2
这里再引出两个概念"整数拆分"和"拆分数"：
所谓整数拆分即把整数分解成若干整数的和（相当于把n个无区别的球放到n个无标志的盒子，盒子允许空，也允许放多于一个球）。 整数拆分成若干整数的和，办法不一，不同拆分法的总数叫做拆分数。
代码实现：
(1+x)(1+x^2)(1+x^3)(1+x^4)
我们要写的代码就是要计算上面的函数式相乘之后的结果，数组c1[]存函数G（x）的每一项系数。代码的实现方式是：通过循环，每次循环把前两个括号相乘，得到新的第一个括号，一直把所有的括号都乘完。
例如：(1+x)(1+x^2)(1+x^3)(1+x^4)
=(1+x+x^2+x^3)(1+x^3)(1+x^4)
这一步就实现了前两个括号融合成一个括号。
第一种代码，模板：
现在以上面的第二种情况每种种类个数无限为例，给出模板：
#include <iostream>
using namespace std;
const int _max = 10001;
// c1是保存各项质量砝码可以组合的数目
// c2是中间量，保存没一次的情况
int c1[_max], c2[_max];
int main()
{
int nNum; //你想用已有的面值组成nNum大小的面值
int i, j, k;
//该代码的前提是假设所有面值为1、2、3、4、5.....的连续数，即下面的 i
//数量无限
while(cin >> nNum)
{
for(i=0; i<=nNum; ++i) //此时的nNum是第一个括号的所有项个数 // ---- ①
{
c1[i] = 1;
c2[i] = 0;
}
for(i=2; i<=nNum; ++i) //nNum 括号个数 // ----- ②
{
for(j=0; j<=nNum; ++j) //j是第一个括号里的每一项x^j的指数j
for(k=0; k+j<=nNum; k+=i) // k第二个括号的每一项x^k的指数
{
c2[j+k] += c1[j]; //目前的第一括号与第二括号两两相乘
//由于第二括号的系数全为1，相乘后的系数就是c1[j],累加即可
}
for(j=0; j<=nNum; ++j) // 把c2中的值给c1,并把c2清0
{
c1[j] = c2[j];
c2[j] = 0;
}
}
cout << c1[nNum] << endl;//输出能组成nNum大小的方案数
}
return 0;
}
第二种代码：
上面的代码只是模板，解决问题是要做许多变动才能适应题目本身，
以这个题为例，就是上面的例题做了修改。
有砝码2克的4个、3克的3个、5克的1个、6克的4个，能称出哪几种重量？每种重量各有几种可能方案？
下面给出面值大小与个数都不连续的示例代码：
#include<stdio.h>
#include <iostream>
using namespace std;
const int _max = 10001;
// c1是保存各项质量砝码可以组合的数目
// c2是中间量，保存每一次的情况
//c1的下标表示的是每一项x^i的系数，函数中的每一项系数
int c1[_max], c2[_max];
int main()
{
int i, j, k;
int max=0,count;
int temp;
int a[_max]={0};//我们用下标来表示砝码重量，用a[i]值来表示i的数量
// 2克的4个、3克的3个、5克的1个、6克的4个
a[2]=4;
a[3]=3;
a[4]=1;
a[5]=4;
for(i=1;i<=5;i++)
max+=a[i]*i; //max记下所有砝码可以组成的最大重量，即总和最大
//因为最小的重量是2，所以第一括号的幂，是2的倍数
for(i=0; i<=4*a[2]; i+=2) //i是第一个括号的每一项x^i的指数,第一括号系数初始为 1
{
c1[i] = 1;
c2[i] = 0;
}
temp=a[2]*4; //始终代表第一括号的最大的指数
for(i=3; i<=5; i++) //i代表砝码重量，可以认为这层循环是对每一个括号的计算
{ //每一次循环把前两个括号乘起来，组成新的第一括号
if(a[i]==0)
continue; //i重量砝码有0个，所以没必要计算
for(j=0; j<=temp; ++j) //j是第一个括号里的每一项x^j的指数
for(k=0; k<=a[i]*i; k+=i) //k第二个括号的每一项x^k的指数
{
c2[j+k] += c1[j]; //目前的第一括号与第二括号两两相乘
//由于第二括号的系数全为1，相乘后的系数就是c1[j],累加即可
}
//上面的k<=a[i]*i 表示第二括号的结束条件，a[i]*i是目前的第二括号最大指数
//temp总是记下第一括号的最大的x^j的指数j，便于下一次循环作为结束条件
temp+=a[i]*i;
for(j=0; j<=max; ++j) // 把c2中的值给c1,并把c2清0
{
c1[j] = c2[j];
c2[j] = 0;
}
}
//计算完成后就得到了每一种重量的方案数，存在c1中
count=0;
for(i=0;i<=max;i++)
{
if(c1[i]==0)//说明无法组成这个重量
continue;
printf("组成%d 重量的方案数：%d\n",i,c1[i]);
count++;
}
printf("能组成的重量有 %d 种\n",count);
}
第三种代码：
回到上面的第一种情况，有1克、2克、3克、4克的砝码各一枚，能称出哪几种重量？每种重量各有几种可能方案？
现在这个问题，砝码是连续的1、2、3....，而且都只有一个。
相比于第二种代码，我们就省去了数组a来存
#include<stdio.h>
#include <iostream>
using namespace std;
const int _max = 10001;
// c1是保存各项质量砝码可以组合的数目
// c2是中间量，保存每一次的情况
//c1的下标表示的是每一项x^i的系数，函数中的每一项系数
int c1[_max], c2[_max];
int main()
{
int i, j, k;
int max=0,count;
for(i=1;i<=4;i++)
max+=i; //max记下所有砝码可以组成的最大重量，即总和最大
//因为最小的重量是1，所以第一括号的幂，是1的倍数
for(i=0; i<=1; i++) //i是第一个括号的每一项x^i的指数，第一括号系数初始为1
{
c1[i] = 1;
c2[i] = 0;
}
for(i=2; i<=4; i++) //i代表砝码重量，可以认为这层循环是对每一个括号的计算
{ //每一次循环把前两个括号乘起来，组成新的第一括号
for(j=0; j<=max; ++j) //j是第一个括号里的每一项x^j的指数
for(k=0; k<=i; k+=i) //k第二个括号的每一项x^k的指数
{
c2[j+k] += c1[j]; //目前的第一括号与第二括号两两相乘
//由于第二括号的系数全为1，相乘后的系数就是c1[j],累加即可
}
for(j=0; j<=max; ++j) // 把c2中的值给c1,并把c2清0
{
c1[j] = c2[j];
c2[j] = 0;
}
}
//计算完成后就得到了每一种重量的方案数，存在c1中
count=0;
for(i=0;i<=max;i++)
{
printf("组成%d 重量的方案数：%d\n",i,c1[i]);
count++;
}
printf("能组成的重量有 %d 种\n",count);
return 0;
}