[来源不详]删数方案数

Description

给出一个正整数序列 a，长度为 n，cyb 不喜欢完美，他要删掉一些数（也可以不删，即删掉0个），但是他不会乱删，他希望删去以后，能将 a 分成 2 个集合，使得两个非空集合的数的和相同，现在他希望你能帮他算出删数的方案数。

Input

第一行 n 个正整数

以下有 n行，每行1个

正整数表示整数序列a

Output

一个整数表示答案

Sample Input

4

1 2 3 4

Sample Output

3

Hint

30%:n<=5

100%:n<=20

100%:a 中每个元素<=100000000

题解

涉及到了hash，状压，双向搜索
首先可以想出一个3N的搜索．
枚举每个是不选还是在A集合，还是在B集合
这样显然通不过20的数据
那么我们发现这个搜索是独立的
如果在A集合，我们令其为−1∗a
在B集合，令其为1∗a
那么实际上我们在找一个方程有多少组解．
这样，我们先搜前面一半，将和用hash存起来
将选的情况，用一个2进制数也存入hash
这样可以通过全部数据

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define mod (100005)
using namespace std;
int n,a[21],lim,t[21];
bool vis[1<<21];
int head[100005],size,ans=0;
struct hash
{
    int tot,st,next;
}edge[100005];
void add_hash(int tot,int st)
{
    int key=(tot%mod+mod)%mod;
    size++;
    edge[size].tot=tot;
    edge[size].st=st;
    edge[size].next=head[key];
    head[key]=size;
}
void find_hash(int tot,int st)
{
    int key=(tot%mod+mod)%mod;
    for(int i=head[key];i!=-1;i=edge[i].next)if(edge[i].tot==tot)vis[edge[i].st+st]=1;
}
void dfs1(int k,int tot,int st)
{
    if(k>lim)
    {
        add_hash(tot,st);
        return;
    }
    dfs1(k+1,tot,st);
    dfs1(k+1,tot+a[k],st+t[k]);
    dfs1(k+1,tot-a[k],st+t[k]);
}
void dfs2(int k,int tot,int st)
{
    if(k==lim)
    {
        find_hash(tot,st);
        return;
    }
    dfs2(k-1,tot,st);
    dfs2(k-1,tot+a[k],st+t[k]);
    dfs2(k-1,tot-a[k],st+t[k]);
}
int main()
{
    freopen("regex.in","r",stdin);
    freopen("regex.out","w",stdout);
    memset(head,-1,sizeof(head));
    int i,j;
    scanf("%d",&n);lim=n/2;
    for(i=1;i<=n;i++)scanf("%d",&a[i]),t[i]=1<<(i-1);
    dfs1(1,0,0);
    dfs2(n,0,0);
    int cnt=(1<<21)-1;
    for(i=1;i<=cnt;i++)
        ans+=vis[i];
    printf("%d
",ans);
    return 0;
}