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