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

#include <bits/stdc++.h>
using namespace std;
const int N=(1<<20)+7;
int ans[N],w,k,a[N];
int n,half,tot; 
vector<int>b[N];
map<int,int>p;
void dfs1(int x,int sum,int now){	
    if(x>half){
        if(p[sum]==0){
        	p[sum]=++tot;
        }
        b[p[sum]].push_back(now);
        return;
    }
	dfs1(x+1,sum,now);
    dfs1(x+1,sum+a[x],now|(1<<(x-1)));	
	dfs1(x+1,sum-a[x],now|(1<<(x-1)));
} 
void dfs2(int x,int sum,int now){
    if(x>n){
        if(p[sum]!=0){
        	for(auto v:b[p[sum]]){
        		ans[v|now]=1;
        	}
        }
        return;
    }
	dfs2(x+1,sum,now);
    dfs2(x+1,sum+a[x],now|(1<<(x-1)));	
	dfs2(x+1,sum-a[x],now|(1<<(x-1)));
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);	
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	} 
	half=(n>>1);
	dfs1(1,0,0);
	dfs2(half+1,0,0);
	int sum=0;
	for(int i=1;i<=(1<<n);i++){
		sum+=ans[i];	
	}
	
	cout<<sum;

	return 0;
}