subset.cpp

USACO chapter two.Useful for beginners.

/*
ID: chenkai4
PROG: subset
LANG: C++
*/
#include <iostream>
using namespace std;

int des,N;

long long int f[40][1000]={0};

int main()
{
	freopen("subset.in","r",stdin);
	freopen("subset.out","w",stdout);
	scanf("%d",&N);
	if(((1+N)*N)%4==0)
	{
		f[1][1]=1;
		f[1][0]=1;
		for(int a=2;a<=N;a++)
			for(int b=0;b<=(1+a)*a/2;b++)
				if(f[a-1][b]>0)
				{
					f[a][b]+=f[a-1][b];
					f[a][b+a]+=f[a-1][b];
				}
		printf("%d\n",f[N][(1+N)*N/4]/2);
	}
	else
		printf("0\n");
	return 0;
}