普通型母函数总结
从这里母函数（Generating function）详解学习了普通型母函数
#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每次是从一个表达式中开始的。
讲得不错，之前第三点注释有问题没想到现在已经改过来了2333.
说说我的理解：母函数其实形式上就是函数...但是关注的是系数。。就像一排挂衣架一样。
普通型母函数的作用就是通过模拟多项式乘法的方式解决一类组合计数问题。
一般能由普通型母函数解决的问题也能由dp或者递推来解决，但是母函数可能更容易理解（对我个人来说
这类问题呢，一般有如下几种问法。
一种是对于每类物品的个数，可能每类个数有限，也可能无限。
如果无限个，那么就根据n的大小作为一个循环的上限，因为n+1以及以后的指数肯定对答案没有贡献。
比如这道题： hdu1028解题报告
如果每类都有限，那么就根据每类物品作为上限。这时j那一层循环要不断累加（变量cur）当前能得到的最大价值（也就是多项式的最大指数） 比如这道hdu1085解题报告 也可能不仅要求上限，还要求有下限，也就是要求每类物品的个数必须在一个范围内。比如这道hdu2152解题报告
也可能两种要同时考虑。比如这道hdu2082解题报告 不过如果就算把所有数量算上也不会太大（数组存不下）的话，不考虑也可以（我懒）
还有，每种元素并不一定像整数拆分一样是连续的，可能像硬币问题一样只有1分，2分，5分的硬币，或者只能是平方数hdu1398解题报告 只能是素数hdu2189解题报告
还有一点，不一定所有元素对答案都是正的贡献，也可能是负的贡献。 这类问题主要是和天平有关。给你若干砝码，问你能称量出多少的重量。由于砝码可以放左边也可以放右边，所以每个对答案有正负两种贡献（不放就是没贡献） 比如这道hdu1709解题报告和这道hdu5616解题报告
最后就是稍微难一点的一类问题：对单个元素的个数没有限制，但是对所有元素的总个数有限制。这类题我们需要增加一维。现在用a[i][j]表示由j个元素组成价值为i的方案数。具体见这里：hdu2069解题报告
20160303 update: 还有一种当个数特别多。。以至于不可能通过循环来实现的情况。需要通过泰勒展开来化简。比较经常用的一个式子是 1+x+x^2+..+x^n=(1-x^(n+1))(1-x)