Author
Ignatius.L
下面解答copy以下链接（并非本人想出来的）：
http://blog.163.com/lyt9469@126/blog/static/17044235820108203120482/
该解答很好、很强大/(^o^)/~
参考解答：
源代码及简单分析：
把加法变为幂运算
这里先给出2个例子，等会再结合题目分析：
第一种：
有1克、2克、3克、4克的砝码各一 枚，能称出哪几种重量？每种重量各有几种可能方案？
考虑用母函数来接吻这个问题：
我们假设x表示砝码，x的指数表示砝码的重量，这样：
1个1克的砝码可以用函数1+x表示，
1个2克的砝码可以用函数1+x2表示，
1个3克的砝码可以用函数1+x3表示，
1个4克的砝码可以用函数1+x4表示，
上面这四个式子懂吗？
我们拿1+x2来说，前面已经说过，x表示砝码，x的指数表示重量，即这里就是一个质量为2的砝码，那么前面的1表示什么？1代表重量为2的砝码数量为0个。（理解！）
不知道大家理解没，我们这里结合前面那句话：
“把组合问题的加法法则和幂级数的t的乘幂的相加对应起来”
1+x2表示了两种情况：1表示质量为2的砝码取0个的情况，x2表示质量为2的砝码取1个的情况。
这里说下各项系数的意义：
在x前面的系数a表示相应质量的砝码取a个，而1就表示相应砝码取0个，这里可不能简单的认为相应砝码取0个就该是0*x2(想下为何？结合数学式子)。
所以，前面说的那句话的意义大家可以理解了吧？
几种砝码的组合可以称重的情况，可以用以上几个函数的乘积表示：
(1+x)(1+x2)(1+x3)(1+x4)
=(1+x+x2+x3)(1+x3+x4+x7)
=1+x+x2+2x3+2x4+2x5+2x6+2x7+x8+x9+x10
从上面的函数知道：可称出从1克到10克，系数便是方案数。（！！！经典！！！）
例如右端有2x5 项，即称出5克的方案有2：5=3+2=4+1；同样，6=1+2+3=4+2；10=1+2+3+4。
故称出6克的方案有2，称出10克的方案有1 。
接着上面，接下来是第二种情况：
求用1分、2分、3分的邮票贴出不同数值的方案数：
大家把这种情况和第一种比较有何区别？第一种每种是一个，而这里每种是无限的。
以展开后的x4为例，其系数为4，即4拆分成1、2、3之和的拆分数为4；
即 ：4=1+1+1+1=1+1+2=1+3=2+2
这里再引出两个概念整数拆分和拆分数（没有顺序）：
所谓整数拆分即把整数分解成若干整数的和（相当于把n个无区别的球放到n个无标志的盒子，盒子允许空，也允许放多于一个球）。
整数拆分成若干整数的和，办法不一，不同拆分法的总数叫做拆分数。
View Code
#include <iostream> using namespace std; const int N=120; int f[N+1],a[N+1],g[N+1]; int i,j,k,n,m; int main() { while(cin>>n) { for (i = 0; i <= n; ++i) // 母函数第一个因子，全为1 f[i]=1; for (i = 2; i <= n; ++i) // f[]保存前面i-1个因子相乘的结果 { for (j = 0; j <= n; ++j) a[j]=0; j=0; while (j <= n) // a[j]=k表示的是k*(x^j),a[]数组表示母函数的第i个因子 { a[j]=1; j+=i; } for (j = 0; j <= n; ++j) // 暂存f[]*a[]的结果 g[j] = 0; for (j = 0; j <= n; ++j) for(k = 0; k <= n-j; ++k) g[j+k] += f[j]*a[k]; // 为了不让f[]的值因为改动而影响以后的值，用g[]来暂存结果 // 两个母函数的因子相乘，若f[j]，a[k]分别属于第1、2个因子，那么f[j]*(x^j)*a[k]*(x^k)==f[j]*a[k]*(x^(j+k)) // 故有g[j+k]+=f[j]*a[k] for (j = 0; j <= n; ++j) f[j] = g[j]; } cout<<f[n]<<endl; } return 0; }