回顾了以前的一些没有完成的题目，发现自己的知识漏洞还挺多的，比如这个生成函数【以前用多重背包一直WA】
生成函数干嘛的？
比较功利的来说，就是用来求解各种排列组合的问题。如果是求组合问题，那就是构造普通型生成函数，如果是求排列的问题，那就是构造指数型生成函数。
最关键的是，这个不像DP，这个是有固定的模板的~那就很简单了。以下是我找的一些生成函数的题目，基本都是一个思想，主要就是通过例子来熟练使用生成函数
普通型生成函数
假设你手里有1张1块，1张2块，1张5块的纸币，能够组成多少种数量的钱，每种数量的钱有几种组成方案
1块 -> 金额1
2块 -> 金额2
5块 -> 金额5
1块 + 2块 -> 金额3
1块 + 5块 -> 金额6
2块 + 5块 -> 金额7
1块 + 2块 + 5块 -> 金额8
（省略了一张都不用，金额0的情况）
设有函数：
其中，x2表示金额2的情况，x5表示金额5的情况，而前面的系数a2表示金额2的组成方案数量，a5表示金额5的组成方案数量
所以刚才举例中可得到的函数是：
把这个函数分解开可以得到
- 只有一张1块的生成函数 G(x) = x0 + x1 【可以有0块和1块这两种金额】
- 只有一张2块的生成函数 G(x) = x0 + x2
把这两个式子相乘可以得到1块和2块的生成函数：
- 1块和2块的生成函数 G(x) = x0 + x1 + x2 + x3
- 只有一张5块的生成函数 G(x) = x0 + x5
把这两个式子相乘可以得到1块、2块和5块的生成函数：
组合问题其实就是与非运算的加法问题。比如上述方案中，就是1、2、5都要；1、2要，5不要；1、5要，2不要；……构成的方案，而这种运算方式恰好可以与幂级数的乘积对应起来
HDU2082
26个字母价值各不相同，且每个字母的数量不一，最后问能组成多少种总价值为50的单词的方案
在上面的例子中，只用到了一张1块，1张2块和1张5块。假设有2张2块，那么就应该能组成0、2、4三种金额；假如有3张2块，那么就能组成0，2，4，6四种金额。也就是说，3张2块的生成函数为：
如果数量不限，那么无数张2块的生成函数为：
在这个基础之上，这类题目其实就变成了多项式的乘积问题。在实际编码时，多项式用数组表示，数组的下标就是对应的多项式的次数。
首先初始化三个数组，a数组记为目前计算完成的生成函数，b数组是当前正在计算的生成函数，将a数组和b数组进行多项式的乘积操作，将计算的答案存储到c数组中，最后将c数组拷贝到a数组中，更新生成函数，具体的编码过程如下：
memset(a,0,sizeof(a));
memset(c,0,sizeof(c));
a[0] = 1;
for (int k=1; k<=26; k++) {
memset(b,0,sizeof(b));
cin>>num;
if (num==0) continue;
for (int i=0; i<=num && k*i<=50; i++)
b[i*k] = 1; //当前价值的生成函数，对应倍数的系数置1
for (int i=0; i<=50; i++)
for (int j=0; j<=50 && i+j<=50; j++)
c[i+j] += a[i]*b[j]; //i+j表示幂指数相加，a[i]*b[j]表示系数相乘
for (int i=0; i<=50; i++) { //拷贝c数组
a[i] = c[i];
c[i] = 0;
}
}
具体的思路就是不断累乘多项式，每个多项式就是每个价值的生成函数，最后得到的就是所有价值的生成函数，也就是所有组成的方案数量，上面题目中，x50的系数就是对应的方案数，也就是a[50]的值
简化累乘过程
上述代码中用到了三个数组，其实可以只用两个数组，因为每一个新的生成函数，系数都是1，比如 4个价值为2 的字母的生成函数：
而相乘的过程就是x0乘以数组a中的每一项，x2乘以数组a中的每一项……所以可以得到如下的简化代码
for (int i=0; i<=num && k*i<=50; i++)
//当前指数是i*k，系数是1
for (int j=0; j<=50 && i*k+j<=50; j++)
c[i*k+j] += a[j];
其中i*k就是当前价值的生成函数的指数，当字母价值为2时，k=2，i从0到4，也就对应了当前每一项的指数，对于每一项指数都需要乘以已经计算好的a数组中的每一项，而a数组中的每一项的系数就是a[j]，指数是j，所以i*k+j就是新的指数，而相应的系数，因为当前系数是1，所以相当于加上a[j]
最后需要求的是小于等于价值为50的单词的方案总数，那就是a[1]累加到a[50]即可，也就是系数和相加
HDU2110
这里的总数不再是50这个固定的值了，而是所有给出的量的总和除以3，也就是1/3的总资产。
核心代码还是一样，只是替换了部分变量而已。下满的p[i]存储的是每个资产的价值，m[i]存储的每个资产的数量，因为上题中资产的价值是固定的，所以这题需要增加数组存储每个资产的价值和数量
for (int k=1; k<=n; k++) {
for (int i=0; i<=m[k] && p[k]*i<=total; i++) {
for (int j=0; j<=total && i*p[k]+j<=total; j++) {
b[i*p[k]+j] += a[j];
b[i*p[k]+j] %= 10000;
}
}
for (int i=0; i<=total; i++) {
a[i] = b[i];
b[i] = 0;
}
}
HDU1028
这题和上面两题不同的是，在这题中，每一个价值的数量是无限的，有无限个1、无限个2……而循环的终点就是目标价值量N
核心代码与上面两题基本相同
for (int k=1; k<=N; k++) {
for (int i=0; k*i<=N; i++)
for (int j=0; j<=N && i*k+j<=N; j++)
b[i*k+j] += a[j];
for (int i=0; i<=N; i++) {
a[i] = b[i];
b[i] = 0;
}
}
HDU1171
这题是大一的时候用多重背包做了很久，一直没做出来，最后就放着的一题。现在去看看当初写的代码量，都快到200行了。
在这题中，目标价值不是固定的了。题意是尽可能的将所有资产平分，那也就是说，目标价值是尽量接近总价值的一半，且存在可能的方案（系数不为0）
核心代码与HDU2110一样
for (int k=1; k<=N; k++) {
for (int i=0; i<=m[k] && i*v[k]<=total; i++)
for (int j=0; j<=total && i*v[k]+j<=total; j++)
b[i*v[k]+j] += a[j];
for (int i=0; i<=total; i++) {
a[i] = b[i];
b[i] = 0;
}
}
在计算完成之后，从中点向起点遍历，找到第一个系数不为0的指数即可，因为存在只有一种资产的情况，所以遍历时不能只遍历到1，而需要遍历到0，也就是说一方什么都没分到，另一方拿走全部
int t = total/2;
for (int i=t; i>=0; i--) { //注意这里是大于等于0，而不是大于0
if (a[i]!=0) {
cout<<total-i<<" "<<i<<endl;
break;
}
}
HDU2152
在这题中，加上了每个价值量（水果）最少出现的次数和最多出现的次数，且题意中总数不大于100
因为第二个循环代表的是当前价值量的使用次数，所以修改第二层循环即可，另外，由于在题意中，每个水果的价值量单位都是1，所以前面几题中的p[k]、v[k]都可以省略
for (int k = 1; k<=N; k++) {
for (int i = mins[k]; i<=maxs[k] && i<=100; i++)
for (int j = 0; j<=100 && i+j<=100; j++)
b[i+j] += a[j];
for (int i=0; i<=100; i++) {
a[i] = b[i];
b[i] = 0;
}
}
以上就是普通型生成函数的例题，通过这几题，大概能得到一个通用的组合方案数计算的模板，理解之后，修改代码就方便了
指数型生成函数
上面已经提到，指数型生成函数是用来处理排列问题的。排列问题存在重复的排列项，比如11333，有2个1和3和3，就需要除以重复项2!3!，所以得到指数型的生成函数：
假设有3个红球，2个黄球，4个绿球。
那么我们规定3个红球的生成函数是：
2个黄球的生成函数是：
3个红球和2个黄球的生成函数是：
4个绿球的生成函数是：
所以：3个红球、2个黄球、4个绿球的生成函数为：
也就是说，从这些球中，取2个的排列数为9，取3个的排列数为26，去4个的排列数为71……
非固定数量的球的生成函数
- 无限数量
- 奇数个
- 偶数个
具体计算时，按固定数量的一样，相乘即可，非固定数量可以直接用级数和来代替
HDU1521
这是固定数量的球，我们同样使用数组来表示多项式，数组下标对应的是指数，数组中的值对应的是系数
double Factorial(int n) { //计算n!
double ans = 1;
for (int i=1; i<=n; i++) ans*=i;
return ans;
}
int main() {
double a[11],b[11];
int n,m,num[11];
while (cin>>n>>m) {
for (int i=1; i<=n; i++)
cin>>num[i];
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
a[0] = 1.0; //初始化数组为1*x^0 = 1
for (int k=1; k<=n; k++) { //计算第k个数
for (int i=0; i<=num[k]; i++) //当前计算的数的指数遍历
for (int j=0; j<=m; j++) //对于每一个指数，都分别乘以已经计算好的多项式
b[j+i] += a[j]/Factorial(i); //每一个项初始化的都是x^n/n!，计算时，相当于指数相加，系数除以n!
for(int j=0;j<=m;j++){
a[j] = b[j];
b[j] = 0;
}
}
cout<<fixed<<setprecision(0)<<a[m]*Factorial(m)<<endl; //保证无小数输出
}
return 0;
}
我们发现核心代码还是相同的，由于数组没项存储的还是指数对应的系数，而指数是1/n!，所以计算时存在小数，所以用double类型
核心代码中的计算b[j+i] += a[j]/Factorial(i); ，由于刚初始化时的每一个数的生成函数的每一项的系数都是1/i! (i表示的是当前的指数)，所以多项式相乘就相当于指数相加，系数等于原系数除以i！
大致上与普通型生成函数相比，核心代码还是一致的，只是计算时多出了计算阶乘的步骤
HDU2065
这题的与上题相比不同的是，数字（字母）有无限个，出现的次数不限或者限奇数次、偶数次
根据上面的公式，得到无限次的生成函数和偶数次的生成函数分别是：
和
而题意中，无限次的有两个字母，偶数次的也有两个字母，所以生成函数为：
现在我们需要求的是排列的个数是n的时候的方案数量，也就是的系数是多少
我们把e4x和e2x在x=0处进行泰勒展开，变为多项式【总算用到高等数学中的东西了】。展开式就不累赘了，展开后，e4x的的系数为4n；e2x的
的系数为2n
所以，所求的系数为
所以只要将n带入这个式子即可，当然由于题中的n很大，所以要用到快速幂，快速幂在前面的文章中已经有介绍了，矩阵快速幂——入门
所以最后的答案就是(quickPow(4,n-1)+quickPow(2,n-1))%100
POJ3734和上题相同，题意表述不同而已
