记录编号	606853	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	4179.毛一琛	最终得分	100
用户昵称	zhyn	是否通过	通过
代码语言	C++	运行时间	2.550 s
提交时间	2025-10-04 15:31:53	内存使用	74.71 MiB

#include<bits/stdc++.h>
using namespace std;
 
#define ll long long
#define maxn 3000005
ll n,cnt=0;
ll num[50];
int nx[maxn];
vector<int>e[maxn];
map<int,int>vis;

void dfs1(int s,ll sum,int to,int k){
	if(s>k){
		if(!vis[sum]){
			cnt++; 
			vis[sum]=cnt;
		}
		e[vis[sum]].push_back(to);
		return; 
	}
	dfs1(s+1,sum+num[s],to|(1<<(s-1)),k);
	dfs1(s+1,sum-num[s],to|(1<<(s-1)),k);
	dfs1(s+1,sum,to,k);
}

void dfs2(int s,ll sum,int to,int k){
	if(s>k){
		int x=vis[sum];
		if(x){
			for(int u:e[x]){
				nx[to|u]=1;
			}
		}
		return; 
	}
	dfs2(s+1,sum+num[s],to|(1<<(s-1)),k);
	dfs2(s+1,sum-num[s],to|(1<<(s-1)),k);
	dfs2(s+1,sum,to,k);
}
 
int main(){
    
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    freopen("subsets.in","r",stdin);
    freopen("subsets.out","w",stdout);
    
    cin>>n;
    
    for(int i=1;i<=n;i++){
        cin>>num[i];
    }
    
    
    dfs1(1,0,0,n/2);
    dfs2(n/2+1,0,0,n); 
    
    ll ans=0;
    for(int i=1;i<=1<<n;i++){
    	ans+=nx[i];
	}
    cout<<ans;
    
    return 0;
}