和が k の部分列 Scala編（paizaランク B 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
シェア用URL:
ツイートする
問題
下記の問題をプログラミングしてみよう！
長さ n の数列 a = (a_1, a_2, ..., a_n) が与えられます。
a の部分列 a' は 2^n 個存在しますが、それらのうち、その要素の総和が k に等しいもの、
つまり、a'_1 + a'_2 + ... + a'_|a'| = k となるものの個数を求めてください。
x の部分列 x' は x の要素のうちいくつか (0 個以上) を選んで元の順序を保ったまま並べたものと定義されます。
例えば、(1, 2, 3) の部分列は (), (1), (2), (3), (1, 2), (1, 3), (2, 3), (1, 2, 3) の 8 個存在します。
また、空の部分列については、要素の総和は 0 とします。
ただし、取り出された部分列が同じでも、その取り出しかたが異なるものは別のものとして数えてください。
また、答えは非常に大きくなる可能性があるため、10^9 で割った余りを出力してください。
- 入力される値
-
n k
a_1 a_2 ... a_n
・ 1 行目に、数列 a の長さを表す整数 n と和を表す整数 k が半角スペース区切りで与えられます。
・ 2 行目に、数列 a の要素 a_1, a_2, ..., a_n が半角スペース区切りで与えられます。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
1 行で、答えを 10^9 で割った余りを整数で出力してください。
また、末尾に改行を入れ、余計な文字を含んではいけません。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・ 入力はすべて整数
・ 1 ≦ n ≦ 100
・ 1 ≦ k ≦ 10000 = 10^4
・ 1 ≦ a_i ≦ 100 (1 ≦ i ≦ n)
- 入力例1
-
3 3
1 2 3
- 出力例1
-
2
- 入力例2
-
3 4
2 2 2
- 出力例2
-
3
