Eva

Time Limit: 10 Sec  Memory Limit: 256 MB
Submit: 68  Solved: 30
Description

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

第一行两个数n，m代表物品数量及钱数

第二行n个数，代表每个物品的价格

n<=40，m<=10^18

一行一个数表示购买的方案数

（想怎么买就怎么买，当然不买也算一种）

5 1000
100 1500 500 500 1000

8

/**************************************************************

    Problem: 4800

    User: ictsing

    Language: C++

    Result: Accepted

    Time:6376 ms

    Memory:34060 kb

****************************************************************/

 

#include <iostream>

#include <cstdio>

#include <algorithm>

using namespace std;

typedef long long ll;

ll a[40];

ll sums1[(1<<21)],sums2[(1<<21)];

void get_sums(ll a[],int n,ll sums[]) 

{

  for(int i=0;i<(1<<n);i++)

  {

    ll sum=0;

    for(int j=0;j<n;j++)

      if(i&(1<<j)) sum+=a[j];

    sums[i]=sum;

  }

  sort(sums,sums+(1<<n));

}

int main()

{

  int n;ll m;

  scanf("%d%lld",&n,&m);

  for(int i=0;i<n;i++) scanf("%lld",&a[i]);

  int n1=n/2,n2=n-n1;

  get_sums(a,n1,sums1);

  get_sums(a+n1,n2, sums2);

  ll ans = 0;

  int pos2=(1<<n2);

  for (int pos1=0;pos1<(1<<n1);pos1++)

  {

    while(pos2>=1&&sums1[pos1]+sums2[pos2-1]>m) 

      pos2--;

    ans+=pos2;

  }

  printf("%lld\n",ans);

  return 0;

}