记录编号	606855	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	4179.毛一琛	最终得分	100
用户昵称	对立猫猫对立	是否通过	通过
代码语言	C++	运行时间	2.398 s
提交时间	2025-10-04 15:40:45	内存使用	53.78 MiB

#include <bits/stdc++.h>
using namespace std;
int n, vis[1 << 21];
int a[1001], ans, idx;
map<int, int> m;
vector<int> g[1 << 21];
void dfs(int step, int sum, int state) {
	if (step >= n / 2) {
		if (!m.count(sum))m[sum] = ++idx;
		g[m[sum]].push_back(state);
	} else {
		dfs(step + 1, sum, state);
		dfs(step + 1, sum + a[step], state | (1 << step));
		dfs(step + 1, sum - a[step], state | (1 << step));
	}
}
void dfs2(int step, int sum, int state) {
	if (step >= n) {
		if (m.count(sum)) {
			int t = m[sum];
			for (int i = 0; i < g[t].size(); i++) {
				vis[g[t][i] | state] = 1;
			}
		}
	} else {
		dfs2(step + 1, sum, state);
		dfs2(step + 1, sum - a[step], state | (1 << step));
		dfs2(step + 1, sum + a[step], state | (1 << step));
	}
}
int main() {
	freopen("subsets.in", "r", stdin);
	freopen("subsets.out", "w", stdout);
	cin >> n;
	for (int i = 0; i < n; i ++)cin >> a[i];
	dfs(0, 0, 0);
	dfs2(n / 2, 0, 0);
	for (int i = 1; i < (1 << n); i ++) {
		if (vis[i]) {
			ans++;
		}
	}
	cout << ans << '\n';
	return 0;
}