母函数的定义以及整数拆分模板 母函数（Generating function）详解

在数学中，某个序列的母函数是一种形式幂级数，其每一项的系数可以提供关于这个序列的信息。使用母函数解决问题的方法称为母函数方法。

母函数可分为很多种，包括普通母函数、指数母函数、L级数、贝尔级数和狄利克雷级数。对每个序列都可以写出以上每个类型的一个母函数。构造母函数的目的一般是为了解决某个特定的问题，因此选用何种母函数视乎序列本身的特性和问题的类型。

由此可以看出:

1.x的系数是a1,a2,…an的单个组合的全体。

2.x2的系数是a1,a2,…a2的两个组合的全体。

………

n.xn的系数是a1,a2,….an的n个组合的全体（只有1个）。

由此得到：

母函数的定义：

对于序列a0，a1，a2，…构造一函数：

称函数G(x)是序列a0，a1，a2，…的母函数

这里先给出2个例子，等会再结合题目分析：

第一种：

有1克、2克、3克、4克的砝码各一枚，能称出哪几种重量？每种重量各有几种可能方案？

考虑用母函数来接吻这个问题：

我们假设x表示砝码，x的指数表示砝码的重量，这样：

1个1克的砝码可以用函数1+x表示，

1个2克的砝码可以用函数1+x2表示，

1个3克的砝码可以用函数1+x3表示，

1个4克的砝码可以用函数1+x4表示，

上面这四个式子懂吗？

我们拿1+x2来说，前面已经说过，x表示砝码，x的指数表示重量，即这里就是一个质量为2的砝码，那么前面的1表示什么？1代表重量为2的砝码数量为0个。（理解！）

不知道大家理解没，我们这里结合前面那句话：

"把组合问题的加法法则和幂级数的t的乘幂的相加对应起来"

1+x2表示了两种情况：1表示质量为2的砝码取0个的情况，x2表示质量为2的砝码取1个的情况。

这里说下各项系数的意义：

在x前面的系数a表示相应质量的砝码取a个，而1就表示相应砝码取0个，这里可不能简单的认为相应砝码取0个就该是0*x2(想下为何？结合数学式子)。

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

所以，前面说的那句话的意义大家可以理解了吧？

几种砝码的组合可以称重的情况，可以用以上几个函数的乘积表示：

(1+x)(1+x2)(1+x3)(1+x4)

=(1+x+x2+x3)(1+x3+x4+x7)

=1+x+x2+2x3+2x4+2x5+2x6+2x7+x8+x9+x10

从上面的函数知道：可称出从1克到10克，系数便是方案数。（！！！经典！！！）

例如右端有2x5项，即称出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分的邮票贴出不同数值的方案数：

大家把这种情况和第一种比较有何区别？第一种每种是一个，而这里每种是无限的。

以展开后的x4为例，其系数为4，即4拆分成1、2、3之和的拆分数为4；

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

这里再引出两个概念整数拆分和拆分数：

所谓整数拆分即把整数分解成若干整数的和（相当于把n个无区别的球放到n个无标志的盒子，盒子允许空，也允许放多于一个球）。

整数拆分成若干整数的和，办法不一，不同拆分法的总数叫做拆分数。

现在以上面的第二种情况每种种类个数无限为例，给出模板：

模板

关于什么是母函数，以及在现实生活中的应用，请大家详看或者HDU母函数PPT：

http://www.cppblog.com/MiYu/archive/2010/08/05/122290.html

对于给出的母函数模板，让人理解起来比较费劲的！以下给出几种解释，和自己理解

//madebysyx
//time2010年9月11日10:17:27
//母函数例题

/*//整数拆分模板

由于 可以把x^1看成 是重量为1的砝码 对于重量为1的砝码数是无限的 所以就有了式子（1+x^1+x^2+x^3.....）

重量为2的砝码可以组成式子（1+x^2+x^4+x^6+.....）

。。。。。。。

之后各个式子相乘 则x^n前的系数便是方案数

注意这里的每种砝码数量是无限的 当是有限的时候就要做下限值了 具体看埋葬的其它文章

#include<iostream>
usingnamespacestd;
constintlmax=10000;
//c1是用来存放展开式的系数的，而c2则是用来计算时保存的，
//他是用下标来控制每一项的位置，比如c2[3]就是x^3的系数。
//用c1保存，然后在计算时用c2来保存变化的值。
intc1[lmax+1],c2[lmax+1];
intmain()
{
intn,i,j,k;
//计算的方法还是模拟手动运算，一个括号一个括号的计算，
//从前往后
while(cin>>n)

{
//对于1+x+x^2+x^3+他们所有的系数都是1
//而c2全部被初始化为0是因为以后要用到c2[i]+=x;
for(i=0;i<=n;i++)

{
c1[i]=1;//蓝色字体表示埋葬个人理解的第一次运行的意义
c2[i]=0;//第一次运行表示出第一个式子的各项系数放进c1
}
//第一层循环是一共有n个小括号，而刚才已经算过一个了
//所以是从2到n
for(i=2;i<=n;i++)//第一个式子表示完毕从第二个式子开始乘一共有n个括号

{
//第二层循环是把每一个小括号里面的每一项，都要与前一个
//小括号里面的每一项计算。
for(j=0;j<=n;j++)//j是控制的第一个式子中的每一项（即前一个式子）
//第三层小括号是要控制每一项里面X增加的比例
//这就是为什么要用k+=i;
for(k=0;k+j<=n;k+=i)//k是控制第二个式子中的系数（后一个式子）

{//而且要保持次数不会超过n因为最多分解为x的

//n次方即表示1个质量为n的砝码
//合并同类项，他们的系数要加在一起，所以是加法，呵呵。
//刚开始看的时候就卡在这里了。
c2[j+k]+=c1[j];//把乘的的结果即系数的变化放进c2
}
//刷新一下数据，继续下一次计算，就是下一个括号里面的每一项。
for(j=0;j<=n;j++)

{
c1[j]=c2[j];
c2[j]=0;
}
}
cout<<c1[n]<<endl;
}
return0;
}
这句c2[j+k]+=c1[j];的理解还要自己好好的体会体会啊！
*/

自己理解：对于（#式）(1+x+x^2+x^3+x^4+x^5+....)*(1+x^2+x^4+x^6+x^8+x^10+....)*(1+x^3+x^6+x^9+x^12....).....

第一个for给c1和c2赋值，把上面#式的第一个括号(1+x+x^2+x^3+x^4+x^5+....)的系数给放在c1中，

从而再次计算从#的第二个括号开始，所以i就是代表的#式第几个括号，

而用程序模拟手工计算，就是先计算第一个括号与第二个括号计算，把结果放到c2中，

在把结果与第三个括号计算，把结果放到c2中，在和第四个括号计算，........

所以j就是指的已经计算出的各项的系数，比如第一次之后1+x+x^2+x^3+x^4+x^5+...，j=0指向1，

j=2指向x，....，而k就是指将要计算的那个括号中的项，因为第i个括号，中的指数为0，i，2i....所以k要+i；

而结果c2[j+k]+=c1[j];就是把以计算出的j项的系数和现在正在计算的括号的k项相乘，所以指数为j+k，所以结果放到c2[j+k]中，这就是这几个for的作用！

最后刷新下结果，下一组数据计算！

埋葬个人的理解

对于（#式）(1+x+x^2+x^3+x^4+x^5+....)*(1+x^2+x^4+x^6+x^8+x^10+....)*(1+x^3+x^6+x^9+x^12....).....

1第一个for给c1和c2赋值，把上面#式的第一个括号(1+x+x^2+x^3+x^4+x^5+....)的系数给放在c1中，

从而再次计算从#的第二个括号开始，

所以i就是代表的#式第几个括号

2j即第i个式子中的第j项

3而k就是指将要计算的那个括号中的项，因为第i个括号x中的指数为0，i，2i....所以k要+i；

4c2[j+k]+=c1[j];

c2[j]c1[j]是指即次数为j的系数；

c1是用来存放展开式的系数的而c2则是用来计算时保存的

这里指c1[j]乘以k之后次数也变成了j+k，故c2[j+k]的系数要增加c1[j]个；

5n是砝码的个数

新例题：hdu1085用125的硬币买不到的东西的价值（输出最小的）3者数量分别为num1num2num3

#include"stdio.h"

intc1[10000],c2[10000];

intmain()

{

inti,j,k,num1,num2,num3,n;

while(scanf("%d%d%d",&num1,&num2,&num3)!=EOF)

{

if(!num1&&!num2&&!num3)break;

n=num3*5+num2*2+num1;

for(i=0;i<=n;i++)

{

c1[i]=0;

c2[i]=0;

}

for(i=0;i<=num1;i++)

c1[i]=1;

for(j=0;j<=num1;j++)

//for(k=0;k+j<=num2*2;k=k+2)//num2*2表示最多可能达到的次数

for(k=0;k<=num2*2;k=k+2)//num2*2表示最多可能达到的次数

{//注意这里不要用k+j<=num2因为以前求整数拆分输入数n要保证次数小于n因为最大为

//x的n次方表示为1个重为n的砝码这里是求多项式相乘不用限制了

c2[j+k]+=c1[j];

}

for(j=0;j<=num2*2+num1;j++)//因为下面的c2[j]中的下标最大为j+k由上一步可以看出而j最大为num1k最大为num2*2

{

c1[j]=c2[j];

c2[j]=0;

}

for(j=0;j<=num2*2+num1;j++)//num1和num2*2不一定那个大那要表示出所有的项数所以要这样

for(k=0;k<=num3*5;k+=5)

c2[j+k]+=c1[j];

for(j=0;j<=num3*5+num2*2+num1;j++)

{

c1[j]=c2[j];

c2[j]=0;

}

for(i=0;i<=n;i++)

if(!c1[i]){printf("%d\n",i);break;}

if(i==n+1)printf("%d\n",i);

}

}

说白了就是求多项式的值