[题目描述]
给出一个正整数序列 a，长度为 n，cyb 不喜欢完美，他要删掉一些数（也可以不删，即删掉0个），但是他不会乱删，他希望删去以后，能将 a 分成 2 个集合，使得两个非空集合的数的和相同，现在他希望你能帮他算出删数的方案数。
[输入文件]
第一行 n 个正整数
以下有 n行，每行1个
正整数表示整数序列a
[输出文件]
一个整数表示答案
[输入样例]
4
1 2 3 4
[输出样例]
3
[数据范围]
30%:n<=5
100%:n<=20
100%:a 中每个元素<=100000000
题解：
对于前半部分和后半部分dfs枚举
将前半部分得到的值包括状态存进hash(去重)，在把后半部分的所有状态去重在hash中查找
本来是用的三进制数表示存进子集A，存进子集B，删去3种状态，后面发现没有必要
因为是“删数的方案”，也就是除删去的数，AB集合间如何分配并不关心，所以直接二进制就行
注意hash不能只存值，还要保存二进制数以判重，保存二进制数的数组不能太小也不能大
hash的大小70000够了，状态数组zt[70000][700]正好AC，500则90分，100则75分
博客里上传了数据，在管理里的文件
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct Node
{
long long s;
int p;
}f[];
int n,zt[][],len,h[];
long long ans,has[],sp[],inf,a[];
bool cmp(Node a,Node b)
{
return (a.s<b.s||(a.s==b.s&&a.p<b.p));
}
void push_hash(long long x,int i)
{int j;
long long p=(x+)%;
while (has[p]!=inf&&has[p]!=x)
{
p++;
if (p>) p=;
}
if (has[p]==inf)
{
has[p]=x;
sp[p]=;
zt[p][sp[p]]=i;
}
else if (has[p]==x)
{
for (j=;j<=sp[p];j++)
if (i==zt[p][j]) return;
sp[p]++;
zt[p][sp[p]]=i;
}
}
void ask_hash(long long x,int i)
{int j;
long long p=(x+)%;
while (has[p]!=inf&&has[p]!=x)
{
p++;
if (p>) p=;
}
if (has[p]==x)
{
for (j=;j<=sp[p];j++)
h[zt[p][j]|i]=;
}
}
void dfs1(int x,long long s,int p)
{int i;
if (x>n/) push_hash(s,p);
else
for (i=-;i<=;i++)
dfs1(x+,s+i*a[x],p|((i!=)<<(x-)));
}
void dfs2(int x,long long s,int p)
{int i;
if (x>n) f[++len]=(Node){s,p};
else
for (i=-;i<=;i++)
dfs2(x+,s+i*a[x],p|((i!=)<<(x-)));
}
int main()
{int i,j;
long long s;
freopen("regex.in","r",stdin);
freopen("regex.out","w",stdout);
cin>>n;
memset(has,-,sizeof(has));
inf=has[];
for (i=;i<=n;i++)
scanf("%lld",&a[i]);
dfs1(,,);dfs2(n/+,,);
sort(f+,f+len+,cmp);
for (i=;i<len;i++)
if (f[i].s==f[i+].s&&f[i].p==f[i+].p) f[i].s=(<<);
sort(f+,f+len+,cmp);
while (f[len].s==(<<)) len--;
for (i=;i<=len;i++)
ask_hash(-f[i].s,f[i].p);
for (i=;i<=(<<n)-;i++) ans+=h[i];
//cout<<h[i]<<endl;
cout<<ans;
}