HDU 1028 Ignatius and the Princess III

题意：整数拆分，有多少本质不同的方案
比如4可以拆为{4}{3,1},{2,1,1},{2，2},{1,1,1,1}

考虑生成函数(G(x)=(1+x+x^2+...)(1+x^2+x^4+...)(1+x^3+x^6+...)...)

(x^n)系数即为所求

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 505;

int n;
long long f[MAXN][2];

void solve(){
	for(int i=0;i<=n;i++) f[i][1]=1,f[i][0]=0;
	for(int i=2;i<=n;i++){
		int u=i&1,v=1-(i&1);
		for(int j=0;j<=n;j++){
			for(int k=0;j+k<=n;k+=i){
				f[j+k][u]+=f[j][v];
			}
		}
		for(int j=0;j<=n;j++) f[j][v]=0;
	}
	cout<<f[n][n&1]<<endl;
}

int main(){
	while(~scanf("%d",&n)){
		solve();
	}
	return 0;
}