hdu 1398 Square Coins （母函数）

母函数。。。

与模版有点不同

模版里，物品是1，2，3，4，5，......，n

这里是1，4，9，---17^2

#include"stdio.h"#define MAX 10000int c1[MAX],c2[MAX];int main(){int n,i,j,k;while(scanf("%d",&n)!=-1&&n){for(i=0;i<=n;i++){c1[i]=1;c2[i]=0;}for(i=2;i<=17;i++){for(j=0;j<=n;j++){for(k=0;k+j<=n;k+=i*i)c2[j+k]+=c1[j];}for(j=0;j<=n;j++){c1[j]=c2[j];c2[j]=0;}}printf("%d\n",c1[n]);}return 0;}