这个题就是一个dp问题
我们用data[i][j]表示前i个数字构成j的方案数
这样的话可以得到状态转移方程
data[i][j]=data[i-1][j-i]+data[i-1][j];
边界条件就是当j等于0的时候data[i][j]=1;
当i等于0的时候j不等于0data[i][j]=0;
然后提交的时候忘记测39这个数据了造成wa了一次
因为求出来的是需要除2的
而39这个数据的答案乘以2以后超过了int
在计算过程中用int64或是unsigned int都是可以的。
我选用了unsigned int这个
因为对g++的int64用哪个一直比较混乱
记得以前写是用long long最近又听说用__int64
1
/**//*
2
ID: bnugong1
3
PROG: subset
4
LANG: C++
5
*/
6
#include<stdio.h>
7
#include<string.h>
8
unsigned int data[40][800];
9
void di(int i,int j)
10

{
11
unsigned int ans;
12
if(j==0)
{
13
data[i][j]=1;
14
return;
15
}
16
if(i==0)
{
17
data[i][j]=0;
18
return;
19
}
20
if(data[i-1][j]==(unsigned int)-1)di(i-1,j);
21
ans=data[i-1][j];
22
if(j-i>=0)
{
23
if(data[i-1][j-i]==(unsigned int)-1)di(i-1,j-i);
24
ans+=data[i-1][j-i];
25
}
26
data[i][j]=ans;
27
// printf("%d\n",ans);
28
return;
29
}
30
int main()
31

{
32
int n,sum;
33
freopen("subset.in","r",stdin);
34
freopen("subset.out","w",stdout);
35
scanf("%d",&n);
36
sum=((n+1)*n)/2;
37
if(sum%2==1)printf("0\n");
38
else
39
{
40
memset(data,-1,sizeof(data));
41
sum=sum/2;
42
di(n,sum);
43
printf("%u\n",data[n][sum]/2);
44
}
45
return 0;
46
}
47