记录编号	606914	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	4179.毛一琛	最终得分	100
用户昵称	梦那边的美好ME	是否通过	通过
代码语言	C++	运行时间	1.459 s
提交时间	2025-10-04 17:02:00	内存使用	5.41 MiB

#include<bits/stdc++.h>
using namespace std;
#define ll long long

struct node{
	ll u,val;
}e[210000],edge[11000000];

ll n,m[30];
ll mid,head[11000000],v[11000000],ans,cnt;
ll cct,sta,tot,cot;

bool vis[1919810];

void dfs1(int d,int sum,int o){
	if(d>mid){
		edge[++cnt].u=head[o];
		edge[cnt].val=sum;
		head[o]=cnt;
		return;
	}
	dfs1(d+1,sum,o);
	dfs1(d+1,sum+m[d],o|(1<<(d-1)));
	dfs1(d+1,sum-m[d],o|(1<<(d-1)));
}

void dfs2(int d,int sum,int o){
	if(d>n){
		e[++cct].u=o;
		e[cct].val=sum;
		return;
	}
	dfs2(d+1,sum,o);
	dfs2(d+1,sum+m[d],o|(1<<(d-1)));
	dfs2(d+1,sum-m[d],o|(1<<(d-1)));
}

bool cmp(const node&a,const node&b){
	return a.val<b.val;
}

int main(){
	freopen("subsets.in","r",stdin);
	freopen("subsets.out","w",stdout);
	scanf("%lld",&n);
	mid=(n+1)>>1;sta=(1<<n)-1;
	for(int i=1;i<=n;i++){
		scanf("%lld",&m[i]);
	}
	dfs1(1,0,0);
	dfs2(mid+1,0,0);
	sort(e+1,e+cct+1,cmp);
	for (int i=0;i<=(1<<mid);i++){
		tot=0;
		cot=1;
		for (int j=head[i];j;j=edge[j].u){
			v[++tot]=edge[j].val;
		}
		sort(v+1,v+tot+1);
		if(v[1]>e[cct].val) break;
		for (int j=1;j<=cct;j++){
			while (cot<=tot&&v[cot]<e[j].val) cot++;
			if (cot>tot) break;
			if (v[cot]==e[j].val) vis[i|e[j].u]=1;
		}
	}
	for (int i=1;i<=sta;i++)
		if (vis[i])
			ans++;
	cout<<ans;
	return 0;
}