(最经典)整数拆分HDU1028

整数拆分
为什么1~n,因为它可以从1~m，取值，并且可以取多次，而m<=n;
(1+x+x2+x3...xn)*(1+x2+x4..xn)*(1+x3+x6..xn)*...(1+xn+x2n+...xnn)
两点要注意：
k的变化:k在第2 括号  k=k+2;这样递增
     k在第3 括号 k=k+3;
     k在第4 括号 k=k+4;  
     所以k=k+i;
i的变化：究竟有多少个括号；i=2从第二个括号开始
             看每个括号的第二项，可以推出x2,x3,...xn
             那就一定是n个括号啦 
只是一个括号数，i以上两点，构成母函数的变化，基于它的变化可以解决很多问题
              
所以输出c1[n],就是xn的系数( n 的组合数)

Problem Description

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

 

Input

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.

 

Output

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

#include<stdio.h>



/*
//c1是用来存放展开式的系数的，而c2则是用来计算时保存的，
//他是用下标来控制每一项的位置，比如 c2[3] 就是 x^3 的系数。
//用c1保存，然后在计算时用c2来保存变化的值。
*/
const int max=120;
int c1[max+1],c2[max+1];

int main()
{
    int n,i,j,k;
    while(scanf("%d",&n)!=EOF)
    {

        // 计算的方法还是模拟手动运算，一个括号一个括号的计算，
        // 从前往后
        //对于 1+x+x^2+x^3+ 他们所有的系数都是 1
        // 而 c2全部被初始化为0是因为以后要用到 c2[i] += x ;
        for(i=0;i<=n;i++)
        {
            c1[i]=1;
            c2[i]=0;
        }

        //第一层循环是一共有 n 个小括号，而刚才已经算过一个了
        //所以是从2 到 n
        for(i=2;i<=n;i++)
        {
            for(j=0;j<=n;j++)
            {
                for(k=0;k+j<=n;k+=i)
                {
                    c2[k+j]+=c1[j];
                }
            }

            for(j=0;j<=n;j++)
            {
                c1[j]=c2[j];
                c2[j]=0;
            }
        }

        printf("%d\n",c1[n]);
    }
    return 0;
}