题目描述
JM是强迫症晚期患者，他执着于集合的完美性，他认为，如果一个集合中所有元素之和恰好为(0)，那么这个集合是完美的。
给定一个大小为(n)的可重复集合(A)，判断该集合存在多少个非空子集是完美的。
可重复集合的意思是集合中可能有重复的元素，此时也可能存在多个相同的满足条件的子集，要按照多个来算。
输入格式
第一行一个正整数(n)，表示集合大小。
第二行(n)个整数，表示集合中的元素。
输出格式
一行一个非负整数，表示满足条件的非空子集的个数。
数据范围与提示
(1leq n leq 35)
(-5 imes 10^7 leq A_i leq 5 imes 10^7)
思路
一个简单的想法就是直接dfs，然而(n)范围到(35)，会炸。
那么记忆化搜索呢，不行，数太大，空间不够。
所以我们做这样的处理:我们把原集合分成两半，在第一个集合中，我们遍历所有的取数可能，假设当前取到的sum为(x)，然后，我们再在第二个集合中找————有多少种取数方法使(sum'=-x)
而对于这两个小集合，集合大小都是18以内，计算一下(2^{18}=262144)，不会TLE，完美！
所以我们先操作第二个集合，把所有可能的值扔到一个multiset里面便于查找。
注意！！！我们这么做会多算一种情况，就是什么都不选，这是不合题意的，所以ans要-1
可是毒瘤出题人卡multiset，这种做法只能拿到95分（真是*疼的分数。。。）
不过，趁此机会练习一下数据结构也是不错的呢。
multiset版本（便于理解）
#include <cstdlib>
#include <algorithm>
#include <set>
#define ll long long
using namespace std;
ll a[40];
multiset<ll> s;
int main() {
int i, j, n, m, t;
ll ans = 0;
scanf("%d", &n);
for (i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
}
s.insert(0);
t = 1 << (n >> 1);
for (i = 1; i < t; i++) {
ll sum = 0;
for (j = 1; j <= n >> 1; j++) {
if ((1 << j - 1) & i)
sum += a[j];
}
s.insert(sum);
}
t = 1 << ((n + 1) >> 1);
for (i = 0; i < t; i++) {
ll sum = 0;
for (j = 1; j <= (n + 1) >> 1; j++) {
if ((1 << j - 1) & i)
sum += a[n / 2 + j];
}
ans += s.count(-sum);
}
ans--;
printf("%lld", ans);
return 0;
}
splay版本（可AC）
#include <cstdlib>
#define ll long long
#define maxn 300000
using namespace std;
ll a[40];
struct SplayTree {
struct node {
int lson, rson, father;
ll val, cnt;
} tree[maxn];
int root, size;
private:
void zig(int x) {
int y = tree[x].father;
tree[x].father = tree[y].father;
if (tree[y].father)
if (tree[tree[y].father].lson == y)
tree[tree[y].father].lson = x;
else
tree[tree[y].father].rson = x;
int z = tree[x].rson;
tree[y].lson = z;
if (z)
tree[z].father = y;
tree[y].father = x;
tree[x].rson = y;
}
void zag(int x) {
int y = tree[x].father;
tree[x].father = tree[y].father;
if (tree[y].father)
if (tree[tree[y].father].lson == y)
tree[tree[y].father].lson = x;
else
tree[tree[y].father].rson = x;
int z = tree[x].lson;
tree[y].rson = z;
if (z)
tree[z].father = y;
tree[y].father = x;
tree[x].lson = y;
}
void splay(int x) {
while (tree[x].father) {
int y = tree[x].father, z = tree[y].father;
if (!z) {
if (tree[y].lson == x)
zig(x);
else
zag(x);
} else {
if (tree[z].lson == y && tree[y].lson == x) {
zig(y);
zig(x);
} else if (tree[z].rson == y && tree[y].rson == x) {
zag(y);
zag(x);
} else if (tree[z].lson == y && tree[y].rson == x) {
zag(x);
zig(x);
} else {
zig(x);
zag(x);
}
}
}
root = x;
}
void insert(int pos, int x) {
if (!root) {
root = x;
return;
}
if (tree[pos].val < tree[x].val) {
if (tree[pos].rson)
insert(tree[pos].rson, x);
else {
tree[pos].rson = x;
tree[x].father = pos;
}
} else {
if (tree[pos].lson)
insert(tree[pos].lson, x);
else {
tree[pos].lson = x;
tree[x].father = pos;
}
}
return;
}
int build(ll x) {
tree[++size].val = x;
tree[size].cnt = 1;
return size;
}
ll query(int pos, ll x) {
if (!pos)
return 0;
if (tree[pos].val == x)
return tree[pos].cnt;
if (tree[pos].val < x)
return query(tree[pos].rson, x);
else
return query(tree[pos].lson, x);
}
int find(int pos, ll x) {
if (!pos)
return 0;
if (tree[pos].val == x)
return pos;
if (tree[pos].val < x)
return find(tree[pos].rson, x);
else
return find(tree[pos].lson, x);
}
public:
void push(ll x) {
int f = find(root, x);
if (f)
tree[f].cnt++;
else
insert(root, build(x));
}
ll count(ll x) { return query(root, x); }
void clear() { size = root = 0; }
} s;
int main() {
int n, t;
ll ans = 0;
scanf("%d", &n);
for (register int i = 1; i <= n; ++i) {
scanf("%lld", &a[i]);
}
s.clear();
s.push(0);
t = 1 << (n >> 1);
for (register int i = 1; i < t; ++i) {
ll sum = 0;
for (register int j = 1; j <= n >> 1; ++j) {
if ((1 << j - 1) & i)
sum += a[j];
}
s.push(sum);
}
t = 1 << ((n + 1) >> 1);
for (register int i = 0; i < t; ++i) {
ll sum = 0;
for (register int j = 1; j <= (n + 1) >> 1; ++j) {
if ((1 << j - 1) & i)
sum += a[n / 2 + j];
}
ans += s.count(-sum);
}
ans--;
printf("%lld", ans);
return 0;
}