本文共 1218 字，大约阅读时间需要 4 分钟。

简单说明一下母函数：

G(x)=(1+a1x)(1+a2x²)…(1+anxⁿ) 称G(x)为a1,a2,…,an,的母函数。 当a1=a2=…=an=1时， G(x)=(1+x)(1+x²)…(1+xⁿ)。 现在假设有这么一个问题：有四种硬币1，2，3，4各一枚，问这些硬币可以组成多少种面额？方案有多少种？ 现在令 G(x)=(1+x)(1+x²)(1+x³)(1+x⁴)=(1+x+x²+x³)(1+x³+x⁴+x⁷) =1+x³+x⁴+x⁷+x+x⁴+x⁵+x⁸+x²+x⁵+x⁶+x⁹+x³+x⁶+x⁷+x¹⁰ =1+x+x²+2x³+2x⁴+2x⁵+2x⁶+2x⁷+x⁸+x⁹+x¹⁰ 于是，这个问题的答案就分别为10，15，怎么知道的呢？首先对于第一个答案，我们可以看x的幂次的个数（不包括1），第二个答案，我们就看x的每一项的系数（不包括1）。因此我们可以知道，母函数中，x的幂次表示价格，如x²就表示价格2，而x的系数就表示组成这种价格的方案数，如2x³就表示价格3的组成方案有2种。 那代码怎么实现呢？ 本质上就是模拟前i-1个多项式与第i个多项式的相乘 杭电1028题的AC代码即为母函数的模板，如下：

#include
   
    #include
    
     #include
     
      #include
      
       typedef long long ll;using namespace std;ll c1[121],c2[121]; //c1用于模拟操作，c2记录下结果，c1[i]的下标i表示x的幂次，c1[i]表示系数，c2同理int main(){	int i,j,k; 	int n;	while(cin>>n) //输入的n表示最高次幂	{		for(i=0;i<=n;i++)  //一开始c1,c2分别初始为1，0，注意i要从0开始，c1一开始初始为1是因为c1一开始表示第一个多项式（1+x+x^2^+...x^n^），每项系数都为1		{			c1[i]=1;			c2[i]=0;		}		for(i=2;i<=n;i++)    // i 表示多项式的编号，亦表示种类，因不同的题而不同，这里是指数字		{			for(j=0;j<=n;j++)  //这两步要理解好				for(k=0;k+j<=n;k+=i)  					c2[j+k]=c2[j+k]+c1[j];			for(j=0;j<=n;j++)  //c2的值返回给c1，c2重新初始为0			{				c1[j]=c2[j];				c2[j]=0;			}		}		cout<
       
        <
       
      
     
    
   

母函数的优点有：

1.题解相对固定，改一改模板一般就可以AC；

2.对于计数问题，母函数不会重复计算（如本题）。

转载地址：http://qbdci.baihongyu.com/