部分和問題 2 F#(Beta)編（paizaランク B 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
シェア用URL:
ツイートする
問題
下記の問題をプログラミングしてみよう！
1 ~ n の番号がついた n 個のおもりがあり、おもり i の重さは a_i です。
おもりを何個か選んで重さの和が x となるようにする方法が何通りあるか求めてください。なお、同じおもりを2個以上選ぶことはできません。
重さが同じおもりが複数存在する場合、それらは区別して別のものとして扱うことにします。
答えは非常に大きくなる可能性があるので、答えを 1,000,000,007 で割った余りで出力してください。
- 入力される値
-
n x
a_1
a_2
...
a_n・ 1行目に、おもりの個数 n と目標とする重さの和 x が半角スペース区切りで与えられます。
・ 続く n 行のうち i 行目では、おもり i の重さ a_i が与えられます。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
重さの和が x となるようにおもりを選ぶ方法が何通りあるか求めてください。
ただし、答えは非常に大きくなる可能性があるので、1,000,000,007 で割った余りで出力してください。
また、末尾に改行を入れ、余計な文字、空行を含んではいけません。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・ 1 ≦ n ≦ 100
・ 1 ≦ x ≦ 1,000
・ 1 ≦ a_i ≦ 100
- 入力例1
-
5 10
7
3
4
3
2
- 出力例1
-
3
