母函数

问题引入

有1元，2元，5元面额的纸币数张，请问支付n元有几种支付方式？
我们设1元面额为$(1+x)$,2元面额为$(1+x^2)$,5元面额为$(1+x^5)$，将这三个式子相乘，得到$(1+x)(1+x^2)(1+x^5)$
拆分得到$1+x+x^2+x^3+x^5+x^6+x^7+x^8$
那么x的幂就是能组合得到的数目，x边上的系数就是组合的方式

思考:为什么每个括号有1这一项？
答:1代表不取

母函数定义

对于序列$a_0,a_1,a_2……a_n$,构造函数$G(x) = a_0 + a_1x + a_2x + ……+ a_nx^n$
则称$G(x)$是序列$a_0,a_1,a_2……a_n$的母函数
例：$f(x) = {(x+1)}^2 = 1 + 2x + x^2$
那么$f(x)$就是序列$1,1,2$的母函数

例题

例1：求用1分，2分，3分邮票贴出不同数值的方案数。
得出母函数：$(1 + x + x^2 + x^3 +…)(1 + x^2 + x^4 + …)(1 + x^3 + x^6 +…)$
因为没有限制使用的数量，所以每种邮票都可以取数张，体现在每一个括号之中。

例2：整数拆分，给出一个整数，将它拆分成几个数的和的形式，求有几种拆法。
得出母函数$(1+x+x^2…)(1+x2+x^4…)(1+x^3+x^6…)…(1+x^{n-1})(1 + x^n)$

核心问题——如何实现？

模板题
HDOJ1028 整数拆分
给出一个整数，求拆分的种数

模板代码

#include<stdio.h>
#define lmax 10000
int c1[lmax + 1],c2[lmax + 1];  // 用数组表示多项式,下标表示指数，值表示系数
//c1 表示第一个括号中的内容，c2是一个临时数组，记录当前循环下各个项的系数
int main()
{
  int n,i,j,k;
  while(scanf("%d",&n) != EOF)
  {
    for(i=0;i<=n;i++) //初始化
    {
      c1[i] = 0;
      c2[i] = 0;
    }
    for(i=0;i<=n;i++) c1[i] = 1; //方便修改。考虑：不能用到1的情况
    for(i=2;i<=n;i++)  //n个括号，执行n-1趟合并。控制合并次数
    {
      for(j=0;j<=n;j++)  //第i-1个括号和第i个括号依次相乘
      {
        for(k=0;k+j<=n;k+=i)  // k+=i代表后面一个括号每一项的幂
          {c2[j+k] += c1[j];}  
          //幂为j+k的那一项的系数，思考1:第二个括号中的系数需要考虑吗？(不需要，后面那个括号的系数必为1)
          //思考2:为什么一个语句也加大括号？(方便修改，题目可能会有变种)
      }
        for(j=0;j<=n;j++)
        {
          c1[j] = c2[j];
          c2[j] = 0;  //临时变量清空
        }
      }
      printf("%d\n",c1[n]); 幂为n的系数即能组成x的n次方的种数
    }
  }