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