/*ID: lucien23PROG: subsetLANG: C++*/#include 
     
      #include 
      
       using namespace std;int main(){	ifstream infile("subset.in");	ofstream outfile("subset.out");	if(!infile || !outfile)	{		cout << "file operation failure!" << endl;		return -1;	}	int N;	infile >> N;		if (N%4 != 0 && (N+1)%4 != 0)	{		outfile << 0 <
       
        << j;			if ((temp & i) == temp)			{				sum1 += j + 1;			} else {				sum0 += j + 1;			}		}		if (sum0 == sum1)		{			count++;		}	}	outfile << count/2 << endl;*/	/*	 * 动态规划	 * 要求前n个数分成总和相等的两个子集的方案数	 * 实际上就是求前n个数中的数能够组成总和为sum=n(n+1)/4的子集的数量	 * 这就能够用动态规划思想，即从这个子集是否包括n能够分两种情况	 * 即求前n-1个数中总和为sum-n和总和为sum的子集数目	 * 设s[i, j]为从前i个数中选择数字组成总和为j的子集的数量，则有	 * s[i, j] = s[i-1, j] + s[i-1, j-i]    ,    j - i >= 0	 * s[i, j] = s[i-1, j]                     ,    j - i < 0	 */	int sum = N * (N + 1) / 4;	long long **s = new long long*[N+1];	for (int i=0; i<=N; i++)	{		s[i] = new long long[sum+1]();	}	s[1][0] = s[1][1] = 1;	for (int i=2; i<=N; i++)	{		for (int j=0; j<=sum; j++)		{			if (i > j)//不能放i			{				s[i][j] = s[i-1][j];			} else {//能够放i				s[i][j] = s[i-1][j] + s[i-1][j-i];			}		}	}	outfile << s[N][sum] / 2 << endl;	return 0;}