记录编号	606961	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	4179.毛一琛	最终得分	100
用户昵称	会挽弯弓满月	是否通过	通过
代码语言	C++	运行时间	1.786 s
提交时间	2025-10-04 19:44:21	内存使用	4.90 MiB

#include <bits/stdc++.h>
using namespace std;
const int N=30;
int n,ans,cnt;
int m[N];
map<int, vector<int> > mp;
//差值 所有能到达的操作 
bool vis[1<<20];
void dfs1(int x,int ls,int rs,int l,int r){
	if(x==n/2+1){
		int s=l|r,dif=ls-rs;
		mp[dif].push_back(s);
		return;
	}
	dfs1(x+1,ls,rs,l,r);
	dfs1(x+1,ls+m[x],rs,l|(1<<(x-1)),r);
	dfs1(x+1,ls,rs+m[x],l,r|(1<<(x-1)));
	return;
}
void dfs2(int x,int ls,int rs,int l,int r){
	if(x==n+1){
		int dif=rs-ls,len,s;
		if(mp.count(dif)){
			vector<int> now=mp[dif];
			len=now.size();
			for(int i=0;i<len;i++){
				s=now[i]|(l|r);
				if(s!=0) vis[s]=1;
			}
		}
		return;
	}
	dfs2(x+1,ls,rs,l,r);
	dfs2(x+1,ls+m[x],rs,l|(1<<(x-1)),r);
	dfs2(x+1,ls,rs+m[x],l,r|(1<<(x-1)));
	return;
}
int sum;
int main(){
	freopen("subsets.in","r",stdin);
	freopen("subsets.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&m[i]);
	dfs1(1,0,0,0,0);
	dfs2(n/2+1,0,0,0,0);
	sum=1<<n;
	for(int i=1;i<sum;i++){
		if(vis[i]) ans++;
	}
	printf("%d",ans);
	return 0;
}