学习母函数(Generation Function)

刚刚看了杭电的acm的ppt，里面有一讲的主题是母函数。开始并没有理解母函数的用处，知道后面看到那个例子，顿时感觉这个构造函数的方法真是巧妙。

问题描述：若有1克、2克、3克、4克的砝码各一枚，能称出哪几种重量？各有几种可能方案？

初看这题，感觉应该用枚举吧，当然这题的数据很简单，但是当数据量大到一定程度时这么做是很慢的。一种巧妙的做法就是构造母函数，做法如下：

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

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

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

  1个4克的砝码可以用函数1+x⁴表示。

这样一来，只需通过计算 (1+x)(1+x²)(1+x³)(1+x⁴) = 1+x+x²+2x³+2x⁴+2x⁵+2x⁶+2x⁷+x⁸+x⁹+x¹⁰ 就能得出这样一个结论：用这4个砝码可以称出1克到10克的所有重量，而对应项的系数就是相应的方案数。

这样看来，母函数的使用可以大大简化对整数拆分类题目分析的难度。而问题的关键就在于如何用程序实现多项式乘积的展开，从而得到对应的方案数。

下面的程序用来计算 G(x) = (1+x+x²+...)(1+x²+x⁴+...)(1+x³+x⁶+...)... 这个算式中指数为n的项的系数。

int c1[N],c2[N];

int genFun(int n)
{
    for(int i=0;i<=n;i++)
    {
        c1[i] = 1;
        c2[i] = 0;
    }
    for(int i=2;i<=n;i++)
    {
        for(int j=0;j<=n;j++)
            for(int k=0;k<=n-j;k+=i)
                c2[j+k] += c1[j];
        for(int j=0;j<=n;j++)
        {
            c1[j] = c2[j];
            c2[j] = 0;
        }
    }
    return c1[n];
}