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

#include <bitset>
#include <iostream>
#include <map>
using namespace std;
int n, m[25];
long long ans = 0;
bitset<1050> vis[1050];
map<int, bitset<1050>> mp;
void dfs(int t, int sum, int u) {
    if (t == n / 2 + 1) {
        mp[sum].set(u);
        return;
    }
    dfs(t + 1, sum, u);
    dfs(t + 1, sum + m[t], u | (1 << (t - 1)));
    dfs(t + 1, sum - m[t], u | (1 << (t - 1)));
    return;
}
void dfs2(int t, int sum, int u) {
    if (t == n + 1) {
        if (mp.count(sum)) {
            bitset<1050> s(mp[sum]);
            s &= ~vis[u];
            ans += s.count();
            vis[u] |= s;
        }
        return;
    }
    dfs2(t + 1, sum, u);
    dfs2(t + 1, sum + m[t], u | (1 << (t - 1 - n / 2)));
    dfs2(t + 1, sum - m[t], u | (1 << (t - 1 - n / 2)));
    return;
}
int main() {
    freopen("subsets.in", "r", stdin);
    freopen("subsets.out", "w", stdout);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> m[i];
    }
    dfs(1, 0, 0);
    dfs2(n / 2 + 1, 0, 0);
    cout << ans - 1;
    return 0;
}