hdu1398Square Coins

经典问题。有n种硬币，每种硬币都有不同的价值，若需要组合出总价值m，问有多少种组合方式。这题中限制硬币价值都是平方数。

比如：

pay ten credits:10分 

ten 1-credit coins,10个1

one 4-credit coin and six 1-credit coins,4+6

two 4-credit coins and two 1-credit coins, and 2*4+2*1

one 9-credit coin and one 1-credit coin. 9+1

链接

1+x+x2+x4...+xn
1+x+x4+x8...+xn 
1+x+x9+x18...+xn
... 
1+x289+x578...+xn 
提到的重要两点：
在i遍历表达式时，把i<=n 改成了i*i<=n
,其次在k遍历指数时把k+=i变成了k+=i*i; 
这里的K还可以这样呢：
     int elem[17]={1,4,9,16,25,36,…,169,196,225,256,289}
i=1时，以1递增
i=2时，以4递增
i=3时，以9递增
。。。。。。
k+=elem[i]

#include<stdio.h>



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

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

        // 计算的方法还是模拟手动运算，一个括号一个括号的计算，
        // 从前往后
        //对于 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 ,i*i提早结束根据题意
        for(i=2;i*i<=n;i++)
        {
            for(j=0;j<=n;j++)
            {
                for(k=0;k+j<=n;k+=(i*i))//k的变化，要根据每一个括号的数列来表示
                {                        //体现组合的不同，也就是多项式的指数不同
                    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;
}