HDU：1028 Ignatius and the Princess III
Problem Description
"Well,it seems the first problem is too easy. I will let you know how foolish you arelater." feng5166 says. "The second problem is, given an positive integer N, we define an equationlike 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!"
Input
Theinput contains several test cases. Each test case contains a positive integerN(1<=N<=120) which is mentioned above. The input is terminated by the endof file.
Output
Foreach test case, you have to output a line contains an integer P which indicatethe different equations you have found.
SampleInput
4
10
20
SampleOutput
5
42
627
题目思路：
就如题目中所说的那样，给出测试数据4，
4 = 4
4 = 1+3
4 = 1+1+2
4 = 2+2
4 = 1+1+1+1
可以构造母函数。想想为什么呢？
我们在数学中学过这样的公式：x^m*x^n= x^(m+n),由此我们知道可以由x的m次方乘上x的n次方，得到x的（m+n）次方，这样可以将乘积转化为和，则这就是m和n的组合。
因此这个题目可以构造母函数：
G(x)=(x^0+x^1+x^2+x^3+x^4)*(x^0+x^2+x^4)*(x^0+x^3)*(x^0+x^4);
=（1+ x^1+x^2+x^3+x^4）*(1+ x^2+x^4)*(1+ x^3)*(1+x^4)
其中x代表数，不管这个数是几，要记住x只是数.
则式子（x^0+x^1+x^2+x^3+x^4）的解释为：x^0代表1取0个，则和为0，则x的幂为0；x^1代表1取了一个，和为1，则x的幂为1，x^2代表1取了两个，和为2，则x的幂为2;x^3代表取了3个1，和为3，则x的幂为3；x^4代表取了4个1，和为4，则x的幂为4；因为要求组成4的组合，因此最多就有4个1，则1的情况已经考虑完了。
同理式子（x^0+x^2+x^4）的解释为，x^0代表数字2取0个，和为0，则x的幂为0；x^2代表数字2取1个，和为2，则x的幂为2，x^4代表数字2取两个，和为4，则x的幂为4；
因为4最多由两个2构成，因此2的个数只能取0,1,2.
同理式子(x^0+x^3)的解释为，x^0代表数字3取0个，和为0，则x的幂为0；x^3代表数字3取1个，和为3，则x的幂为3；因为4中最多包含一个3，则3的个数只取0个或1个。
同理式子(x^0+x^4)的解释为，x^0代表数字4取0个，和为0，则x的幂为0；x^4代表数字4取1个，和为4，则x的幂为4；因为4中最多包含一个4，则4的个数只取0个或1个。
G(x)=(x^0+x^1+x^2+x^3+x^4)*(x^0+x^2+x^4)*(x^0+x^3)*(x^0+x^4);
=（1+ x^1+x^2+x^3+x^4）*(1+ x^2+x^4)*(1+ x^3)*(1+x^4)
代表0个1与2个2的组合
代表0个1与1个2的组合
代表0个1与0个2的组合
=（1+ x^1+x^2+x^3+x^4）*(1+ x^2+x^4)*( …………………)
=[(1+1*X^2+1*x^4)+(x^1*1+x^1*x^2+x^1*x^4)+(x^2*1+x^2*x^2+x^2*x^4)+……(x^4*1+x^4*x^2+x^4*x^4)]*(……………………)
=(1+x+2x^2+2x^3+3x^4+2x^5+2x^6+x^7+x^8)* *(……………………)
要求的是组成4的方案数，幂为5,6,7,8的相超界直接不予考虑
=（1+x+2x^2+2x^3+3x^4）*(……………………)
这些项代表当前由（0,1,2,3,4）个1与（0,1,2）个2所构成的组合，其系数等于当前的方案数。
例如x^1系数为1，构成1的只有1
这一种，x^2的系数为2，构成2的
方案有两种：1+1，2；构成x^3的方案也有两种，1+1+1,1+2；X^4系数为3，代表构成4的方案数有3种。1+1+1+1，1+1+2,2+2这三种。
继续向下求。
=（1+x+2x^2+2x^3+3x^4）*（1+x^3）*() 求1,2组合后产生的结果在和3进行组合。
=（1+x+2x^2+3x^3+4x^4+2^x5+2x^6+3x^7）*（） 幂大于4的项不予考虑
=（1+x+2x^2+3x^3+4x^4）*（1+x^4）
=1+x+2^2+3x^3+5^x4;
则x^4前的系数就是就是构成4的方案数。答案就是5.
明白了母函数的构造以及这样构造的道理，接下来就是怎么将这个思路用代码实现。
int main() { int n; while(~scanf("%d",&n)) { int i,j,k; int a[130]; ///a[i]存放当前组成数字i的方案数 int b[130]; ///b[i]用来前面已经求出的x^i的系数 for(i = 0; i <= n; i++) { a[i]=0; //初始化，刚开始构成任何数i的方案数都是0 b[i]=1; //(x^0+x^1+x^2+x^3+x^4)的系数都是1 } for(i = 2; i <= n; i++) //从2开始考虑 { for(j = 0; j <= n; j++) for(k = 0; k+j <= n; k=k+i) a[j+k] += b[j]; for(j = 0; j <= n; j++) { b[j]=a[j]; ///更新x^j前的系数 a[j]=0; } } printf("%d\n",b[n]); } return 0; }
