# Untitled

By: a guest on Apr 15th, 2012  |  syntax: C++  |  size: 0.85 KB  |  hits: 15  |  expires: Never
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
1. #include <iostream>
2.
3. #include <map>
4.
5. #define MOD 1000000000
6.
7. using namespace std;
8.
9. int mass[40], pw[(1<<19)+1], totmass[1<<20];
10.
11. map<int,int> cnt;
12.
13. int main() {
14.
15.   int N,M,ans = 0;
16.
17.   scanf("%d%d",&N,&M);
18.
19.   for(int i=0;i<M;++i) scanf("%d",&mass[i]);
20.
21.   for(int i=0;i<20;++i) pw[1<<i] = i;
22.
23.   int M2 = M>>1;
24.
25.   totmass[0] = 0;
26.
27.   cnt[0] = 1;
28.
29.   for(int i=1;i<(1<<M2);++i) {
30.
31.     int lb = i&(-i);
32.
33.     if(totmass[i-lb] >= N) totmass[i] = N+1;
34.
35.     else totmass[i] = totmass[i-lb] + mass[pw[lb]];
36.
37.     cnt[totmass[i]]++;
38.
39.   }
40.
41.   for(int i=0;i<(1<<(M-M2));++i) {
42.
43.     if(i) {
44.
45.       int lb = i&(-i);
46.
47.       if(totmass[i-lb] >= N) totmass[i] = N+1;
48.
49.       else totmass[i] = totmass[i-lb] + mass[M2+pw[lb]];
50.
51.     }
52.
53.     ans += cnt[N-totmass[i]];
54.
55.     if(ans >= MOD) ans -= MOD;
56.
57.   }
58.
59.   printf("%d\n",ans);
60.
61. }