[ARC017C] 無駄なものが嫌いな人

有一个背包容量为 X (1≤X≤10^9)，同时有 N 个物品 (1≤n≤32)，第i个物体有体积wi(1≤wi≤5×10^7)。求从 n 个物品中，任取若千个装入箱内，使箱子被装满的方法有几种。

[problemUrl]: https://atcoder.jp/contests/arc017/tasks/arc017_3 私は無駄なものが嫌いなので、無駄なことを言わずに言いたいことだけ言おう。 世の中にはナップサック問題というものがあり、決まった大きさのナップサックにできるだけ価値が高くなるよう品物を詰めることを考えるらしいが、そんなことを考えても無駄である。 価値がいくら高くなったところで、ナップサックに無駄なスペースができてしまうのは許せない。私は無駄なものが嫌いなのだ。 さて、今ここに大きさ $ 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 行に出力せよ。 ``` <pre class="prettyprint linenums"> 5 5 1 1 2 3 4 ``` ``` <pre class="prettyprint linenums"> 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 $ は同じ重さの品物であるが異なる品物として扱うことに注意すること。 ``` <pre class="prettyprint linenums"> 8 21 10 4 2 30 22 20 8 14 ``` ``` <pre class="prettyprint linenums"> 0 ``` どのように品物を選んでも、その大きさの和がぴったり $ 21 $ になるようにはできない。 ``` <pre class="prettyprint linenums"> 20 100000000 35576749 38866484 6624951 39706038 11133516 25490903 14701702 17888322 14423251 32111678 24509097 43375049 35298298 21158709 30489274 37977301 19510726 28841291 10293962 12022699 ``` ``` <pre class="prettyprint linenums"> 45 ``` ``` <pre class="prettyprint linenums"> 16 8 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ``` ``` <pre class="prettyprint linenums"> 12870 ```