抄的题解
2^40爆搜过不了，考虑折半搜索，难点在于合并左右的答案，因为有可能答案同时载左右两边，我们用两个数组记录下来答案，
然后我们再对左边的答案排个序，那么对于右边其中的来说，它可能产生的集合是与左边
的状态相结合。使用二分查找
输入要用%lld
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #define ll long long using namespace std; int n,mid; ll m,w[50],suma[1<<21],sumb[1<<21],cnta,cntb,ans; void dfs(int l,int r,ll sum,ll a[],ll &cnt){ if(sum>m)return; if(l>r){ a[++cnt]=sum;return; } dfs(l+1,r,sum+w[l],a,cnt); dfs(l+1,r,sum,a,cnt); } int main(){ scanf("%d%lld",&n,&m); for(int i=1;i<=n;i++)scanf("%lld",&w[i]); mid=n/2; dfs(1,mid,0,suma,cnta); dfs(mid+1,n,0,sumb,cntb); sort(suma+1,suma+1+cnta); for(int i=1;i<=cntb;i++) ans+=upper_bound(suma+1,suma+1+cnta,m-sumb[i])-suma-1; printf("%lld\n",ans); }
原文：https://www.cnblogs.com/superminivan/p/10859329.html