1398s square coins.cpp

来自「ACM 威士忌部分答案」· C++ 代码 · 共 41 行

/*
1398s Square Coins
Time Limit : 1000 ms  Memory Limit : 32768 K  Output Limit : 256 K

46 MS 348 KB 514 B 
GUN C++
*/
/*
母函数应用
典型的利用母函数可解的题目。

G(x)=(1+x+x2+x3+x4+…)(1+x4+x8+x12+…)(1+x9+x18+x27+…)…
*/

#include <iostream>
using namespace std;
const int lmax=300;
int c1[lmax+1],c2[lmax+1];

int main(void)
{	int n,i,j,k;
	while (cin>>n && n!=0)
	{	
        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)//重复使用所以为 +=i*i
				{	c2[j+k]+=c1[j];	}
				
			for (j=0;j<=n;j++)
			{	c1[j]=c2[j];	c2[j]=0;	}//数据转移
		}
		cout<<c1[n]<<endl;
	}
	return 0;
}