来自FallDream的博客，未经允许，请勿转载，谢谢。

---

 

有n个物品，m块钱，给定每个物品的价格，求买物品的方案数

n<=40 m<=10^18

 

考虑双向宽搜，然后得到两个大小为2^20的数组，排序之后两个指针推一推计算答案即可。

排序最好用基数排序

#include
     
      #include
      
       #include
       
        #define MN 40#define MM 1050000#define N 32767#define ll unsigned long longusing namespace std;inline ll read(){    ll x = 0 , f = 1; char ch = getchar();    while(ch < '0' || ch > '9'){ if(ch == '-') f = -1;  ch = getchar();}    while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}    return x * f;}int n,lim,tot1=0,tot2=0,v[4][N+5];ll a[MN+5],s[MM+5],s2[MM+5],m,sa[MM+5],ans=0;void Dfs2(int x,ll y){    if(x==lim){s2[++tot2]=y;return;}    if(y+a[x]<=m) Dfs2(x-1,y+a[x]);    Dfs2(x-1,y);    }void Dfs1(int x,ll y){    if(x>lim){s[++tot1]=y;return;}    if(y+a[x]<=m)Dfs1(x+1,y+a[x]);    Dfs1(x+1,y);}void Sort(ll*s,int n){    memset(v,0,sizeof(v));//    for(int i=1;i<=n;++i) cout<
        
         <<" ";puts("");    for(int i=1;i<=n;++i)         for(ll j=s[i],i=0;i<4;j>>=15,++i) ++v[i][j&N];    for(int r=0;r<4;++r) for(int i=1;i<=N;++i) v[r][i]+=v[r][i-1];    for(ll r=0,j=N;r<4;++r,j<<=15)    {        for(register int i=n;i;--i) sa[v[r][(s[i]&j)>>(r*15)]--]=s[i];         for(register int i=1;i<=n;++i) s[i]=sa[i];    }    }int main(){    n=read();lim=n>>1;m=read();    for(int i=1;i<=n;++i) a[i]=read();    Dfs1(1,0);Dfs2(n,0);    Sort(s,tot1);Sort(s2,tot2);    for(int i=tot1,j=1;i;--i)    {        while(j
         
          <=m) ++j;        if(s2[j]+s[i]<=m) ans+=j;    }    printf("%lld\n",ans);    return 0;}