hdu 1398 Square Coins【生成函数】

预处理出完全平方数就和普通的生成函数解整数拆分一样了

#include<iostream>

#include<cstdio>

using namespace std;

const int N=605;

int n,m,q[N],a[N],b[N];

int main()

{

	for(int i=1;i<=18;i++)

		q[i]=i*i;

	while(scanf("%d",&m)&&m)

	{

		for(n=1;q[n+1]<=m;n++);

		for(int i=0;i<=m;i++)

			a[i]=1,b[i]=0;

		for(int i=2;i<=n;i++)

		{

			for(int j=0;j<=m;j++)

				for(int k=0;k<=m;k+=q[i])

					b[j+k]+=a[j];

			for(int j=0;j<=m;j++)

				a[j]=b[j],b[j]=0;

		}

		printf("%d\n",a[m]);

	}

	return 0;

}

巴特西

hdu 1398 Square Coins【生成函数】

最新文章

热门文章