C - 無駄なものが嫌いな人 Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

私は無駄なものが嫌いなので、無駄なことを言わずに言いたいことだけ言おう。
世の中にはナップサック問題というものがあり、決まった大きさのナップサックにできるだけ価値が高くなるよう品物を詰めることを考えるらしいが、そんなことを考えても無駄である。
価値がいくら高くなったところで、ナップサックに無駄なスペースができてしまうのは許せない。私は無駄なものが嫌いなのだ。
さて、今ここに大きさ X のナップサックと N 個の品物がある。
i 番目の品物の大きさは w_i である。品物の価値については、考えても無駄なので無視する。
ナップサックに無駄なスペースができないよう品物を詰める方法は何通りあるだろうか？
つまり、N 個の品物から、大きさの総和が無駄なくぴったり X となる選び方が何通りあるか、ということだ。
私ははじめ手でこの問題を解こうとしたが、無駄が多い手段であると分かったので君に頼むことにした。
無駄な計算時間のないプログラムを書いてこの問題を解き、私の無駄な時間を省くのを手伝ってもらいたい。

入力

入力は以下の形式で標準入力から与えられる。

N X
w_1
w_2
:
w_N
  • 1 行目には、品物の個数を表す整数 N (1 \leq N \leq 32) とナップサックの大きさを表す整数 X (1 \leq X \leq 10^9) が半角空白区切りで与えられる。
  • 2 行目から N 行では、品物の大きさが与えられる。このうち i (1 \leq i \leq N) 行目には、i 番目の品物の大きさを表す整数 w_i (1 \leq w_i \leq 5 \times 10^7) が書かれている。

出力

N 個の品物のうちいくつかを選び、その大きさの和がぴったり X になるような方法が何通りあるかを表す整数を 1 行に出力せよ。

入力例１

5 5
1
1
2
3
4

出力例１

4
無駄のない品物の選び方は次の 4 通りである。
  • 品物 1, 品物 2, 品物 4 を選ぶ: 1 + 1 + 3 = 5
  • 品物 1, 品物 5 を選ぶ: 1 + 4 = 5
  • 品物 2, 品物 5 を選ぶ: 1 + 4 = 5
  • 品物 3, 品物 4 を選ぶ: 2 + 3 = 5
品物 1 と品物 2 は同じ重さの品物であるが異なる品物として扱うことに注意すること。

入力例２

8 21
10
4
2
30
22
20
8
14

出力例２

0
どのように品物を選んでも、その大きさの和がぴったり 21 になるようにはできない。

入力例３

20 100000000
35576749
38866484
6624951
39706038
11133516
25490903
14701702
17888322
14423251
32111678
24509097
43375049
35298298
21158709
30489274
37977301
19510726
28841291
10293962
12022699

出力例３

45

入力例４

16 8
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1

出力例４

12870