记录编号	274020	评测结果	AAAAAAAAAAAAAAAAAAAAA
题目名称	[USACO Open12] 平衡奶牛子集	最终得分	100
用户昵称	神利·代目	是否通过	通过
代码语言	C++	运行时间	0.626 s
提交时间	2016-06-26 09:36:24	内存使用	77.64 MiB

#include<stdio.h>
#define HASH 5000010
bool flag[1100000];
int ans,n,n1,n2,m1[15],m2[15];
int shu,first[HASH];
struct edge{int val,stat,nx;}o[HASH];
inline void add(int x,int y){
	int ha=(x%HASH+HASH)%HASH;
	for(int i=first[ha];i;i=o[i].nx)
	    if(o[i].val==x&&o[i].stat==y)
	        return;
	o[++shu].val=x,o[shu].stat=y,o[shu].nx=first[ha],first[ha]=shu;
}
inline void dfs1(int x,int now,int stat){
	if(x==n1){
		add(-now,stat);
		return;
	}
	dfs1(x+1,now-m1[x+1],stat|1<<x);
	dfs1(x+1,now,stat);
	dfs1(x+1,now+m1[x+1],stat|1<<x);
}
inline void dfs2(int x,int now,int stat){
	if(x==n2){
		int ha=(now%HASH+HASH)%HASH;
		for(int i=first[ha];i;i=o[i].nx)
		    if(o[i].val==now){
				if(!flag[stat<<n1|o[i].stat])
				    ++ans,flag[stat<<n1|o[i].stat]=1;
		    }
		return;
	}
	dfs2(x+1,now-m2[x+1],stat|1<<x);
	dfs2(x+1,now,stat);
	dfs2(x+1,now+m2[x+1],stat|1<<x);
}
int main(){
	freopen("subsets.in","r",stdin);
	freopen("subsets.out","w",stdout);
	scanf("%d",&n);
	n1=n>>1,n2=(n-1>>1)+1;
	for(int i=1;i<=n1;++i)scanf("%d",&m1[i]);
	for(int i=1;i<=n2;++i)scanf("%d",&m2[i]);
	dfs1(0,0,0);
	dfs2(0,0,0);
	printf("%d",ans-1);
	//while(1);
}