题面：SP11469 SUBSET - Balanced Cow Subsets
题解：
对于任意一个数，它要么属于集合A，要么属于集合B，要么不选它。对应以上三种情况设置三个系数1、-1、0，于是将题目转化
为找出两个集合和为0，将这两个集合合并不重复的为一种答案。考虑折半搜索。搜出前一半和后一半，用哈希表和状态压缩记录
和去重，然后统计答案即可。
时间复杂度为O(6^(N/2))。
代码：
#include<cstdio>
using namespace std;
const int maxn=,MOD=,max_num=6e4;
int N,M[maxn],num=,ans=,nx[max_num],hd[MOD+];
int Tmp[max_num],Sum[max_num],hf,ps;
bool vis[][];
inline void Insert(int tmp,int sum){
ps=(sum%MOD+MOD)%MOD;
for(int i=hd[ps];i;i=nx[i])
if(Tmp[i]==tmp && Sum[i]==sum) return;//
nx[++num]=hd[ps];
Tmp[num]=tmp;
Sum[num]=sum;
hd[ps]=num;
return;
}
inline int Find(int tmp,int sum){
ps=(sum%MOD+MOD)%MOD;
int ans=;
for(int i=hd[ps];i;i=nx[i])
if(Sum[i]==sum && vis[Tmp[i]][tmp]==){
vis[Tmp[i]][tmp]=;
ans++;
}
return ans;
}
inline void Dfs1(int tp,int sum,int tmp){
if(tp>hf){
Insert(tmp,sum);
return;
}
Dfs1(tp+,sum+M[tp],tmp<<|);
Dfs1(tp+,sum-M[tp],tmp<<|);
Dfs1(tp+,sum,tmp<<);
return;
}
inline void Dfs2(int tp,int sum,int tmp){
if(tp>N){
ans+=Find(tmp,-sum);
return;
}
Dfs2(tp+,sum+M[tp],tmp<<|);
Dfs2(tp+,sum-M[tp],tmp<<|);
Dfs2(tp+,sum,tmp<<);
return;
}
int main(){
scanf("%d",&N);
hf=N>>;
for(int i=;i<=N;i++) scanf("%d",&M[i]);
Dfs1(,,);
Dfs2(hf+,,);
printf("%d\n",ans-);
return ;
}
By:AlenaNuna