题目链接

SP11469 SUBSET - Balanced Cow Subsets

题目翻译

给出 N （ 1 ≤ N ≤ 20 ） N（1≤N≤20） N（1≤N≤20）个数 M ( i ) ( 1 < = M ( i ) < = 100 , 000 , 000 ) M(i) (1 <= M(i) <= 100,000,000) M(i)(1<=M(i)<=100,000,000)，在其中选若干个数，如果这几个数可以分成两个和相等的集合，那么方案数加1。问总方案数。

思路：
如果折半搜出的两个序列数字都相等的话是会被卡爆的，这是我们就需要更稳更好打的方法。

我们换个角度考虑，N只有区区20，所有选或不选的方案数只有 2 N <mtext>   </mtext> = <mtext>   </mtext> 1 e 6 2^N\ = \ 1e6 2N = 1e6，如果在两次搜索就把每种选的情况可行性做出来，就可以解决问题。

第一次搜索时，我们记录每一种结果可以被哪些组合拼出来（ N = = 20 N == 20 N==20，组合状态是可以压缩的）。当然一种结果可能被多个组合拼出来，所以要用vector记录，而一个结果也可能很大，需要用map离散化（编个号就行，不用排序）。

那么第二次搜索时，每当我们得到一个结果S，我们是需要前一半产生-S的总和来得到方案的，显然-S的方案就是S的方案反过来而已，是完全等效的，那么我们遍历第一次搜到的所有能使前一半算出S的方案，他们的组合与后一半的组合并在一起就是一个可能的答案。
思路来源%%%

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=2000000+7;//范围2^20
ll v,n,m,ans,a[100],use[N],mx,mc;
vector<ll>d[N];
map<ll,ll>mp;
inline void dfs1(ll i,ll sum,ll now)//now为压缩状态（状压），sum为当前的总和
{
    if(i>mx)
    {
        if(!mp.count(sum))mp[sum]=++mc;//（伪）离散化
        d[mp[sum]].push_back(now);//当前now可以拼出sum的和
        return;
    }
    dfs1(i+1,sum,now);//选择当前
    dfs1(i+1,sum+a[i],now|(1<<(i-1)));//选左边第1组
    dfs1(i+1,sum-a[i],now|(1<<(i-1)));//选右边第2组
}
inline void dfs2(ll i,ll sum,ll now)
{
    if(i>n)
    {
        if(mp.count(sum)){
            ll x=mp[sum];//寻找前一半（左边）能拼出-sum的组合（利用map映射）
            for(int i=0;i<d[x].size();++i)
                use[d[x][i]|now]=1;//两边一组合就是一个可能的结果个
        }
        return;
    }
    dfs2(i+1,sum,now);
    dfs2(i+1,sum+a[i],now|(1<<(i-1)));
    dfs2(i+1,sum-a[i],now|(1<<(i-1)));
}
int main()
{
    scanf("%lld",&n);
    mx=n>>1;//n/2
    for(int i=1;i<=n;++i)
        scanf("%lld",&a[i]);
    dfs1(1,0,0),dfs2(mx+1,0,0);//先dfs左边一半，再dfs右边一半，(n/2+1)
    for(int i=1;i<=1<<n;++i)//遍历每一种情况
        ans+=use[i];
    printf("%lld\n",ans);
}