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

#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;

#define int long long
int m[25];
int SA[2005];
int SB[2005];
int n;
unordered_map<int, vector<int> > mp;

signed main(){
    freopen("subsets.in", "r", stdin);
    freopen("subsets.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for(int i = 0;i < n;i ++) cin >> m[i];
	int k = n / 2;
	int l1 = 1 << k;
	int l2 = 1 << (n - k);
	for(int p = 0;p < l1;p ++){
		int s = 0;
		for(int i = 0;i < k;i ++){
//		    cout << (p & (1 << j)) << '\n';
			if(p & (1 << i)) s += m[i];
		}
//		cout << s << '\n';
		SA[p] = s;
	}
	for(int p = 0;p < l2;p ++){
		int s = 0;
		for(int j = 0;j < (n - k);j ++){
			if(p & (1 << j)) s += m[k + j];
		}
		SB[p] = s;
//		cout << s << '\n';
		mp[s].push_back(p);
	}

	int ans = 0;
	int len = 1 << n;
	for(int p = 1;p < len;p ++){
		int pA = p >> (n - k);
		int pB = p & (l2 - 1);
//		cout << pA << ' ' << pB << '\n';
		int sum = SA[pA] + SB[pB];
		if(sum % 2 != 0) continue;
		int tag = sum / 2;
		bool flag = false;
		int s1 = 0;
		do{
			int sa = SA[s1];
			int res = tag - sa;
//			cout << sa << ' ' << res << '\n';
			auto it = mp.find(res);
			if(it != mp.end()){
				for(int x : it -> second){
//				    cout << x << '\n';
					if((x & pB) == x){
						if(s1 == 0 && x == 0) continue;
						flag = true;
						break;
					}
				}
				if(flag) break;
			}
			s1 = (s1 - 1) & pA;
		}while(s1 != 0);
		if(flag) ans ++;
	}
	cout << ans << '\n';
	return 0;
}