记录编号	606912	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	4179.毛一琛	最终得分	100
用户昵称	郑霁桓	是否通过	通过
代码语言	C++	运行时间	2.011 s
提交时间	2025-10-04 16:59:00	内存使用	31.81 MiB

#include<bits/stdc++.h>
using namespace std;
long long n,a[25],ss,t,p,as[1050000];
map<long long,long long>mp;
vector<long long>v[1050000];
void dfs(long long x,long long s1,long long s2,long long sx){
    if(x==n/2+1){
        if(!mp[s1-s2]) mp[s1-s2]=++t;
        v[mp[s1-s2]].push_back(sx);
        return;
    }
    dfs(x+1,s1+a[x],s2,sx+(1<<(x-1))),dfs(x+1,s1,s2+a[x],sx+(1<<(x-1))),dfs(x+1,s1,s2,sx);
    return;
}
void dfss(long long x,long long s1,long long s2,long long sx){
    if(x==n+1){
        p=mp[s2-s1];
        for(int i=0;i<v[p].size();i++) as[sx|v[p][i]]=1;
        return;
    }
    dfss(x+1,s1+a[x],s2,sx+(1<<(x-1))),dfss(x+1,s1,s2+a[x],sx+(1<<(x-1))),dfss(x+1,s1,s2,sx);
    return;
}
int main(){
    freopen("subsets.in","r",stdin);
    freopen("subsets.out","w",stdout);
    cin>>n;
    for(long long i=1;i<=n;i++) cin>>a[i];
    dfs(1,0,0,0),dfss(n/2+1,0,0,0);
    for(int i=1;i<=(1<<n);i++) ss+=as[i];
    cout<<ss;
    return 0;
}