2013
11-26

# Ignatius and the Princess III

"Well, it seems the first problem is too easy. I will let you know how foolish you are later." feng5166 says.

"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!"

The input contains several test cases. Each test case contains a positive integer N(1<=N<=120) which is mentioned above. The input is terminated by the end of file.

For each test case, you have to output a line contains an integer P which indicate the different equations you have found.

4
10
20

5
42
627

1个1克的砝码可以用函数1+x表示，

1个2克的砝码可以用函数1+x2表示，

1个3克的砝码可以用函数1+x3表示，

1个4克的砝码可以用函数1+x4表示，

“把组合问题的加法法则和幂级数的t的乘幂的相加对应起来”

1+x2表示了两种情况：1表示质量为2的砝码取0个的情况，x2表示质量为2的砝码取1个的情况。

(1+x)(1+x2)(1+x3)(1+x4)

=(1+x+x2+x3)(1+x3+x4+x7)

=1+x+x2+2×3+2×4+2×5+2×6+2×7+x8+x9+x10

#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;
}

1. 这道题目虽然简单，但是小编做的很到位，应该会给很多人启发吧！对于面试当中不给开辟额外空间的问题不是绝对的，实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟，今天看到小编这篇文章相见恨晚。

2. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.