前言
出来混的总是要还的
正文
问题来源
看博客的时候看到的，是个基础的算法，本应该早点掌握的。
问题描述
在谈论母函数问题之前，我们先看一个简单的问题描述：假如有两组数据(A,B)和(C,D)，每组中选出一个构成一个组合，总共有几种选法？很显然总共有4种选法：AC,AD,BC,BD。而且很容易联想到这个式子(A+B)(C+D)=AC+AD+BC+BD。式子中的几个乘积项就是上面的4种选法。假如把问题换一下：每组中选出一个或0个数据构成组合，总共有几种组合？那么结果就变成：{空},A,B,C,D,AC,AD,BC,BD，而式子(1+A+B)(1+C+D)=1+C+D+A+AC+AD+B+BC+BD，正好和上面组合的结果又一致(1代表什么都没选)。从这2个例子我们可以发现多项式乘积和组合存在着某种关系。事实上我们可以这么理解：(1+A+B)可以理解为从第一组数据中取0个数据，取A或者取B，同样(1+C+D)可以理解为从第二组数据取0个数据，取C或者取D。两者相乘的结果就表示了所有的组合。再看一下这个多项式：
(1+x)*(1+x+x^2)*(1+x^3)=1+2x+2x^2+2x^3+2x^4+2x^5+x^6
这个多项式和上面的有一些区别了，它的幂级数超过1了。如果要从(1+x)、(1+x+x^2)和(1+x^3)中得到x的2次方的话，有两种选择：从(1+x) 和(1+x+x^2)中分别选择一个x或者从(1+x+x^2)中选择x^2；如果要得到x的6次方的话，只有1种选择，就是从(1+x) 中选择x、(1+x+x^2)中选择x^2、(1+x^3)中选择x^3。也就是说乘积结果的每一项an * x^n的前面的系数an表示了从(1+x)、(1+x+x^2)和(1+x^3)中得到x^n的组合数。
其实上面的例子就利用了母函数的思想，下面来具体讨论一下母函数。
一.什么是母函数
下面这个对于母函数的描述摘自维基百科：
在数学中，某个序列 的母函数是一种形式幂级数，其每一项的系数可以提供关于这个序列的信息。
也就是说母函数是针对某个序列的，它的外在表现形式是一种形式幂级数。比如说有这样一个序列a0，a1，……an，构造一个函数
f(x)=a0+a1x+a2x^2+……+anx^n
则f(x)是序列a0，a1，……an的母函数。比如说最常见的(1+x)n，它是序列C(n,0)，C(n,1)，C(n,2)…C(n,n)的母函数。
母函数包括几种，其中最常见的是普通型母函数和指数型母函数。普通型母函数是形如 f(x)=a0+a1x+a2x^2+……+anx^n的函数，而指数型母函数是形如G(x) = a0 + a1*(x)/1! + a2*(x^2)/ 2! + a3*(x^3)/3! + …… an*(x^n)/k!的函数。
二.利用普通型母函数解决组合问题
利用母函数的思想可以解决很多组合问题，下面举例说明：
1.口袋中有白球2个，红球3个，黄球1个，从袋中摸出3个球有几种取法？
和上面描述的例子类似，我们可以用次数代表球的个数，多项式的每一项前面的系数代表取法的种树。
可以很容易地写出下面这个式子：
(1+x+x^2)(1+x+x^2+x^3)(1+x)
(1+x+x^2)表示有白球2个，1表示白球不取，x代表取1个白球，x2代表取2个白球，即用x的次数表示取球的个数，后面的也是类似。那么这个多项式的乘积就把所有的情况都表示出来了，对于最终乘积的每一项anxn，表示取n个球有an种取法。
2.有若干个1克，2克，5克的砝码，要称出20克的重量，有多少种称法？
这里不限制砝码的个数，无所谓，照样写出母函数：
(1+x+x^2+x^3+……x^k+….)(1+x^2+x^4+x^6……+x^2n+……)(1+x^5+x^10+……x^5m+……)
因为要称出20克，所以只需要找找到结果中次数为20 的那一项就可以得到结果。
3.同样对于正数划分也可以解决，比如有整数20，划分成1，2，5，有多少种划分方法？
解法和2的类似。
还有一类题目和这类似，有n个球放到m个盒子中，有多少种不同的放法？
(1+x+x^2+x^3+…x^k+…)(1+x+x^2+x^3+…x^k+…)(1+x+x^2+x^3+…x^k+…)总共有m项，然后找出乘积中次数为n的那一项系数。
三.利用指数型母函数解决排列问题
1.口袋中有白球2个，红球3个，黄球1个，任取3个作为一个排列，总共有多少种排列？
类似地用指数型母函数解决
用(1+x/1!+x^2/2!)表示取白球0个，1个或者2个
那么(1+x/1!+x^2/2!)(1+x/1!+x^2/2!+x^3/3!)(1+x/1!)来表示所有的排列结果。
=1+3x+4x^2+19x^3/6+19x^4/12+6x^5/12+x^6/12
=1+3(x/1!)+8(x^2/2!)+19(x^3/3!)+38(x^4/4!)+60(x^5/5!)+60(x^6/6!)
找到次数为3的那一项，系数为19，那么总共有19种排列。
2.用1，2，3，4能够组成多少个5位数，要求1出现2次或者3次，2出现0次或者1次，3没有限制，4只出现偶数次。
(x^2/2!+x^3/3!)(1+x)(1+x/1!+x^2/2!+x^3/3!+…..x^k/k!+….)(1+x^2/2!+x^4/4!+……+x^2n/(2n)!+……)
每个式子的含义就不多解释了，读者应该能看懂它的含义。最终的结果就是x^5/5!这一项的系数。
用代码去实现母函数的计算过程很简单，它是模拟我们人工计算多项式乘积的过程，比如有多项式H1H2H3……
我们先计算H1和H2的乘积，得到结果H’，再用H’和H3相乘……依次类推下去，直到得到最终的结果。
例题：
整数拆分
输入一个整数n，把它拆成若干个整数相加，输出有多少种拆分的方法。
比如：4=3+1=2+2=2+1+1=1+1+1+1，有5种。
解：
所谓整数拆分即把整数分解成若干整数的和（相当于把n个无区别的球放到n个无标志的盒子，盒子允许空，也允许放多于一个球）。
G(x)=(1+x+x^2+…)(1+x^2+x^4+…)(1+x^3+x^6+…)…
#include <stdio.h>
#include <string.h>
int main()
{
int c1[200],c2[200]; //c1保存当前表达式里各项的系数，c2是中间量
int n,i,j,k;
while(scanf("%d",&n)!=EOF)
{
for(i=0;i<=n;i++) //n拆分的数必定小于或等于n，所以只用从0遍历到n,即母函数的第1个括号里的表达式只能是1+x+x^2+…+x^n
{
c1[i]=1; //初始化c1[],c1[]的下标是项的指数，值是项的系数
c2[i]=0;
}
for(i=2;i<=n;i++) //后面有n-1个表达式（括号里的式子），要展开n-1次，i指第i个表达式
{
for(j=0;j<=n;j++)
{
for (k=0;k+j<=n;k=k+i)
{
c2[k+j]+=c1[j]; //只用保留指数<=n的项，所以k+j<=n
} //j指当前表达式里项的第j个项，k指后一个表达式里项的指数，k=k+i
} //两个相邻表达式展开
for(j=0;j<=n;j++)
{
c1[j]=c2[j];
c2[j]=0;
} //每展开一次，就将c1[]更新，c2[]归0
}
printf("%d\n",c1[n]);
}
return 0;
}
钱币组合：
有面值为1，2，5的3种硬币，输入各硬币的个数，求最小的一个不能组合的成的价值。
比如输入1 1 3，输出4
解：
G(x)=(1+x+x^2+…)(1+x^2+x^4+…)(1+x^5+x^10+…)
3种面值，所以只有3个括号表达式。
#include <stdio.h>
#include <string.h>
int main()
{
int a,b,c,i,j,k,sum;
int c1[8008],c2[8008];
int elem[3]={1,2,5};
int num[4];
while(scanf("%d%d%d",&a,&b,&c)!=EOF)
{
if(a==0&&b==0&&c==0)
break;
sum=1*a+2*b+5*c;
num[1]=a;
num[2]=b;
num[3]=c; //num[]存放括号内表达式的项的个数
memset(c1,0,sizeof(c1));
memset(c2,0,sizeof(c2)); //c1[],c2[]全部归0
for(i=0;i<=a;i=i+elem[0]) //初始化第1个表达式里各项的系数
c1[i]=1;
for(i=2;i<=3;i++)
{
for(j=0;j<=sum;j++)
{
for(k=0;k<=num[i]*elem[i-1]&&k+j<=sum;k=k+elem[i-1])
{
c2[j+k]+=c1[j];
}
}
for(j=0;j<=sum+1;j++)
{
c1[j]=c2[j];
c2[j]=0;
}
}
for(i=0;i<=sum+1;i++)
{
if(c1[i]==0)
{
printf("%d\n",i);
break;
}
}
}
return 0;
}
总结：
咱们赶快趁热打铁，来几道题目：
（相应题目解析均在相应的代码里分析）
1. 题目：http://acm.hdu.edu.cn/showproblem.php?pid=1028
代码：http://www.wutianqi.com/?p=587
这题大家看看简单不？把上面的模板理解了，这题就是小Case!
看看这题：
2. 题目：http://acm.hdu.edu.cn/showproblem.php?pid=1398
代码：http://www.wutianqi.com/?p=590
要说和前一题的区别，就只需要改2个地方。 在i遍历表达式时（可以参考我的资料—《母函数详解》），把i<=nNum改成了ii<=nNum,其次在k遍历指数时把k+=i变成了k+=ii; Ok,说来说去还是套模板~~~
3. 题目：http://acm.hdu.edu.cn/showproblem.php?pid=1085
代码：http://www.wutianqi.com/?p=592
这题终于变化了一点，但是万变不离其中。
大家好好分析下，结合代码就会懂了。
4. 题目：http://acm.hdu.edu.cn/showproblem.php?pid=1171
代码：http://www.wutianqi.com/?p=594
还有一些题目，大家有时间自己做做：
HDOJ：1709，1028、1709、1085、1171、1398、2069、2152
附：
1.在维基百科里讲到了普通母函數、指數母函數、L級數、貝爾級數和狄利克雷級數：
http://zh.wikipedia.org/zh-tw/%E6%AF%8D%E5%87%BD%E6%95%B0
2．Matrix67大牛那有篇文章：什么是生成函数：
http://www.matrix67.com/blog/archives/120
3.大家可以看看杭电的ACM课件的母函数那篇，我这里的图片以及一些内容都引至那。
结语
查漏补缺。
