记录编号	606956	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	4179.毛一琛	最终得分	100
用户昵称	二乾五	是否通过	通过
代码语言	C++	运行时间	2.239 s
提交时间	2025-10-04 19:32:12	内存使用	53.23 MiB

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

#define ll long long
#define cpy(a,b) copy(begin(a),end(a),begin(b))
#define ld long double
#define dot(x) fixed<<setprecision(x)
#define foru(a,b,c) for(ll a=b;a<=c;a++)

ll n,n2,a[25],ans[2000005],s,tot;
vector<vector<ll>>p(2000005);
map<ll,ll>b;

void dfs1(ll x,ll sum,ll now){
    if(x>n2){
        if(b[sum]==0)b[sum]=++tot;
        p[b[sum]].push_back(now);
        return;
    }
    dfs1(x+1,sum+a[x],now|(1<<(x-1)));
    dfs1(x+1,sum-a[x],now|(1<<(x-1)));
    dfs1(x+1,sum,now);
}

void dfs2(ll x,ll sum,ll now){
    if(x>n){
        ll t=b[sum];
        if(t!=0)foru(i,0,p[t].size()-1){
            ans[p[t][i]|now]=1;
        }
        return;
    }
    dfs2(x+1,sum+a[x],now|(1<<(x-1)));
    dfs2(x+1,sum-a[x],now|(1<<(x-1)));
    dfs2(x+1,sum,now);
}

int main(){
    cin>>n;
    n2=n/2;
    foru(i,1,n){
        cin>>a[i];
    }
    dfs1(1,0,0);
    dfs2(n2+1,0,0);
    foru(i,1,(1<<n))s+=ans[i];
    cout<<s;
    return 0;
}