这几天看了Tanky Woo的母函数http://www.wutianqi.com/?p=596，感觉把数学和现实生活真正结合是在ACM里啊～～

我在这里把生成函数的解题思路再整理一下，一是把多项式的计算和物品的组合更直接的关联起来，二是通过举例补充一下Tanky Woo没有细讲的题目。

关键词：多“种”不同价值物品构成所需总价值的“方案数”——这里的“所需总价值”是一个上限

• 生成函数初印象

    (IMO 2001 HK Preliminary Selection Contest) Find the coefficient of x17 in the expansion of (1 + x 5 + x 7 ) 20 .

Solution.
The only way to form an x17 term is to gather two x5 and one x 7 . Since there are C220 = 190 ways to choose two x 5 from the 20 multiplicands and 18 ways to choose one x 7 from the remaining 18 multiplicands, the answer is 190 × 18 = 3420. To gain a preliminary insight into how generating functions is related to counting, let us describe the above problem in another way. Suppose there are 20 bags, each containing a $5 coin and a $7 coin. If we can use at most one coin from each bag, in how many different ways can we pay $17, assuming that all coins are distinguishable (i.e. the $5 coin from the first bag is considered to be different from that in the second bag, and so on)? It should be quite clear that the answer is again 3420 — to pay $17, one must use two $5 coins and one $7 coin. There are C220 = 190 ways to choose two $5 coins from the 20 bags, and 18 ways to choose a $7 coin from the remaining 18 bags. Using the notations we introduced at the very beginning, we could say that a17 = 3420 .

• 方法：

1. 根据每种物品可取的数目和其价值构造一个多项式
   例如：有8个5分硬币可用(x^₅0+x^₅1+x^₅2+...+x^₅8)
2. 根据上限计算构造出所有多项式的乘积，乘积的结果是多项式，每一个小项的指数是组合出来的价值，小项的系数是方案数

举个具体的例子：HDU 1398 Squre Coin

题目大意：用1，4，9……289等平方数组合，求所给数n（n不大于300）的组合方案数

S1：构造多项式的乘积(x^₁0+x^₁1+x^₁2+...+x^₁n) * (x^₄0+x^₄1+x^₄2+...x^₄(n/4))*(x^₉0+x^₉1+x^₉2+...x^₉(n/9))*...

S2：根据上限n计算（定义N=305）

1. 开两个数组存多项式，数组的index是多项式项的指数，element里的数是方案数
   C1[N]和C2[N]，C1存之前已经算好的多项式结果的系数，C2存运算当前项的系数，C1[i]的i是组合出来的价值
2. 初始化C1：对于第一项从0至n的系数都是1，因为当前就这一种组合方法——全选1
   

   for(int i=0; i<=n; i++)
   {
       c1[i] = 1;
       c2[i] = 0;
   }
   

3. 每一个多项式的计算：
   因为C1里存的是上一轮已经算好的结果多项式，所以对当前多项式的每一项遍历C1，两者相乘，并把系数加到C2上
   

   for(int j=0; j<=n; j++) // 遍历C1，j是项的指数
   {
        for(int k=0; k+j<=n; k+=i*i) // 当前多项式的指数是i方^0，i方^1,i方^2...直到(j+i方^k)>0为止
        {
            c2[k+j] += c1[j]; // 把之前的结果多项式项的系数加过来
        }
   }
   

4. 计算n-1个多项式，记得每次要更新C1，C2
   

   for(int i=2; i*i<=n; i++) // 已经初始化过1了，所以从2*2=4开始，知道i*i<=n结束
   {
         // 上面解释的第三步
         for(int j=0; j<=n; j++)
         {
               for(int k=0; k+j<=n; k+=i*i)
               {
                       c2[k+j] += c1[j];
               }
         }
         // 更新C1，C2
         for(int j=0; j<=n; j++)
         {
               c1[j] = c2[j];
               c2[j] = 0;
         }
   }
   

5. 最后C1里存的就是结果啦～

完整代码见http://bonniebbs.is-programmer.com/posts/40074.html

• 变化一：有正有负 HDU 1709 天平

题目大意：已知砝码的各种重量，求不能够称出来的重量。注：砝码可以放在天平的左边或右边

基本计算里多项式系数都是正的，所以每次都只要加就好了，但是这道题就要求C1里的系数可能为负的情况

而本题里的多项式的正项和副项具有对称性，所以我们只要正项就可以了

for(int j=0; j<=s; j++) // s是一个上限
{
        if(c1[j])
       {
                c2[j+a] += c1[j];
                c2[j] += c1[j];
        }
}
// 这里开始计算系数为负的情况
for(int j=1; j<=s; j++) // 注意零已经算过不用算了
{
        if(c1[j])
        {
               c2[abs(j-a)] += c1[j]; // abs返回其绝对值
        }
}

完整代码见：http://bonniebbs.is-programmer.com/posts/40075.html

• 变化二：物品的总个数也作为一个上限 HDU 2069 Coin Change

题目大意：求使用不超过100个1,2,5,10,25,50硬币组合成n的方案数——这里不超过100就是另一个上限

原来的C1是一维的，包含了项的指数和项的系数，现在增加一维，记录使用过的项的数目

    int c1[N][M], c2[N][M], ans[N];

所以循环里要增加一个控制项的量的循环，其实可以看作是将原来某指数项的系数用存储已用个数的一个维度延伸开来

        for(int j=0; j<=250; j++) // 遍历已有多项式全部指数
        {
            for(int k=0; k*"mianzhi"+j<=250; k++) // 对当前多项式指数的循环控制，使用k作控制总体已用项的数量
            {
                for(int l=0; l+k<=100; l++) // 对当前多项式的某一项遍历——不同的个数
                {
                    c2[j+k*"mianzhi"][l+k] += c1[j][l]; // 考虑个数在内的更新
                }
            }
        }
        for(int x=0; x<=250; x++)
        {
            for(int y=0; y<=100; y++)
            {
                c1[x][y] = c2[x][y];
                c2[x][y] = 0;
            }
        }

最外面用个数组存储“mianzhi”

    int num[6] = {0,1,5,10,25,50};
    int c1[N][M], c2[N][M], ans[N];
    for(int i=1; i<6; i++)
    {
        for(int j=0; j<=250; j++)
        {
            for(int k=0; k*num[i]+j<=250; k++)
            {
                for(int l=0; l+k<=100; l++)
                {
                    c2[j+k*num[i]][l+k] += c1[j][l];
                }
            }
        }
        // 更新C1，C2，注意现在是二维，并且更新的地点总是在一个多项式算完的地方
        for(int x=0; x<=250; x++)
        {
            for(int y=0; y<=100; y++)
            {
                c1[x][y] = c2[x][y];
                c2[x][y] = 0;
            }
        }
    }
    // 跟据指数合并不同个数的组成
    for(int i=0; i<=250; i++)
        for(int j=0; j<=100; j++)
            ans[i] += c1[i][j];

完整代码见：http://bonniebbs.is-programmer.com/posts/40077.html

• 生成函数Steps

Step 0 HDU 1208

Step 0.5 HDU 2152

Step 1 HDU 1398

Step 2 HDU 1085

Step 3 HDU 1171

Step 4 HDU 1709

Step 5 HDU 2069

• Tanky Woo 的最基本模板（以下内容摘自http://www.wutianqi.com/?p=596）

求用1分、2分、3分的邮票贴出不同数值的方案数：这里每种是无限的。

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

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

#include <iostream>
using namespace std;
// Author: Tanky Woo
// www.wutianqi.com
const int _max = 10001; 
// c1是保存各项质量砝码可以组合的数目
// c2是中间量，保存没一次的情况
int c1[_max], c2[_max];   
int main()
{	//int n,i,j,k;
	int nNum;   // 
	int i, j, k;
 
	while(cin >> nNum)
	{
		for(i=0; i<=nNum; ++i)   // ---- ①
		{
			c1[i] = 1;
			c2[i] = 0;
		}
		for(i=2; i<=nNum; ++i)   // ----- ②
		{
 
			for(j=0; j<=nNum; ++j)   // ----- ③
				for(k=0; k+j<=nNum; k+=i)  // ---- ④
				{
					c2[j+k] += c1[j];
				}
			for(j=0; j<=nNum; ++j)     // ---- ⑤
			{
				c1[j] = c2[j];
				c2[j] = 0;
			}
		}
		cout << c1[nNum] << endl;
	}
	return 0;
}

我们来解释下上面标志的各个地方：(***********！！！重点！！！***********)

①  、首先对c1初始化，由第一个表达式(1+x+x^2+..x^n)初始化，把质量从0到n的所有砝码都初始化为1.

②  、 i从2到n遍历，这里i就是指第i个表达式，上面给出的第二种母函数关系式里，每一个括号括起来的就是一个表达式。

③、j 从0到n遍历，这里j就是(前面i個表达式累乘的表达式)里第j个变量，(这里感谢一下seagg朋友给我指出的错误，大家可以看下留言处的讨论)。如(1+x)(1+x^2)(1+x^3)，j先指示的是1和x的系数，i=2执行完之后变为

（1+x+x^2+x^3）(1+x^3)，这时候j应该指示的是合并后的第一个括号的四个变量的系数。

④ 、 k表示的是第j个指数，所以k每次增i（因为第i个表达式的增量是i）。

⑤  、把c2的值赋给c1,而把c2初始化为0，因为c2每次是从一个表达式中开始的。