题目链接

SP11469 SUBSET - Balanced Cow Subsets

题目翻译

给出 N 1 N 20 N(1≤N≤20) N1N20个数 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);
}