Ignatius and the Princess III
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 9306 Accepted Submission(s): 6563
"The second problem is, given an positive integer N, we define an equation like this:
N=a[1]+a[2]+a[3]+...+a[m];
a[i]>0,1<=m<=N;
My question is how many different equations you can find for a given N.
For example, assume N is 4, we can find:
4 = 4;
4 = 3 + 1;
4 = 2 + 2;
4 = 2 + 1 + 1;
4 = 1 + 1 + 1 + 1;
so the result is 5 when N is 4. Note that "4 = 3 + 1" and "4 = 1 + 3" is the same in this problem. Now, you do it!"
4 10 20
5 42 627
源代码及简单分析：
把加法变为幂运算
这里先给出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个无标志的盒子，盒子允许空，也允许放多于一个球）。
整数拆分成若干整数的和，办法不一，不同拆分法的总数叫做拆分数。
#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++) f[i]=1; //母函数第一个因子，全为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]=1; //a[j]=k表示的是k*(x^j),a[]数组表示母函数的第i个因子
j+=i;
}
for(j=0; j<=n; j++) g[j]=0; //暂存f[]*a[]的结果
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;
}