【母函数】hdu1028 Ignatius and the Princess III

大意是给你1个整数n，问你能拆成多少种正整数组合。比如4有5种：

4 = 4;
  4 = 3 + 1;
  4 = 2 + 2;
  4 = 2 + 1 + 1;
  4 = 1 + 1 + 1 + 1;

然后就是母函数模板题……小于n的正整数每种都有无限多个可以取用。

(1+x+x^2+...)(1+x^2+x^4+...)...(1+x^n+...)

答案就是x^n的系数。

#include<cstdio>

#include<cstring>

using namespace std;

int n,a[123],b[123];

int main()

{

	while(scanf("%d",&n)!=EOF)

	  {

	  	memset(a,0,sizeof(a));

	  	memset(b,0,sizeof(b));

	  	a[0]=1;

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

	  	  {

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

	  	  	  for(int k=0;k*i+j<=n;++k)

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

	  	  	memcpy(a,b,sizeof(a));

	  	  	memset(b,0,sizeof(b));

	  	  }

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

	  }

	return 0;

}

巴特西

【母函数】hdu1028 Ignatius and the Princess III

最新文章

热门文章