No.2394 部分和乗総和
タグ : / 解いたユーザー数 106
作問者 : 👑
p-adic
/ テスター :
hotman78
hiro1729
問題文
入力に３つの正整数 $N, M, B$ と、長さ $N$ の正整数列 $A$ が与えられます。
まずは記法の導入です。$A$ の（連続部分列とは限らない）部分列全体の集合を $S(A)$ と置きます。
ただしここでは部分列と言った時、$A$ の何番目の成分を取り出したものかのデータも含めます。
例えば $A = (1,1,2)$ である時、$A$ には数列として $(1,2)$ となる部分列が $2$ つあり互いに区別されます。
$A$ の各部分列 $A'$ に対し、その成分の総和を $s(A')$ と置きます。
$\sum_{A' \in S(A)} M^{s(A')}$ を $B$ で割った余りを求めてください。
入力
入力は次の形式で標準入力から $2$ 行で与えられます：
$N$ $M$ $B$ $A$
- $1$ 行目に $N, M, B$ が半角空白区切りで与えられます。
- $2$ 行目に $A$ の各成分が半角空白区切りで与えられます。
制約
入力は以下の制約を満たします：
- $N$ は $1 \leq N \leq 10^5$ を満たす整数
- $M$ は $1 \leq M \leq 10^{18}$ を満たす整数
- $B$ は $1 \leq B \leq 10^9$ を満たす整数
- $A$ の各成分 $a$ は $1 \leq a \leq 10^{18}$ を満たす整数
出力
$\sum_{A' \in S(A)} M^{s(A')}$ を $B$ で割った余りを $1$ 行に出力してください。
最後に改行してください。
サンプル
サンプル1
入力
1 1 2 1
出力
0
$A = (1)$ の部分列には数列として空列 $()$ である部分列 $A'_0$ と $(1)$ である部分列 $A'_1$ の $2$ つがあります。
$\displaystyle \sum_{A' \in S(A)} M^{s(A')} = M^{s(A'_0)} + M^{s(A'_1)} = 1^0 + 1^1 = 1 + 1 = 2 $
であり、$2$ を $B = 2$ で割った余りは $0$ です。
サンプル2
入力
1 2 2 1
出力
1
$A$ はサンプル1と同じです。サンプル1と同じ記法を用いると
$\displaystyle \sum_{A' \in S(A)} M^{s(A')} = M^{s(A'_0)} + M^{s(A'_1)} = 2^0 + 2^1 = 1 + 2 = 3 $
であり、$3$ を $B = 2$ で割った余りは $1$ です。
サンプル3
入力
2 1 2 1 3
出力
0
$A = (1,3)$ の部分列には数列として空列 $()$ である部分列 $A'_0$ と $(1)$ である部分列 $A'_1$ と $(3)$ である部分列 $A'_2$ と $(1,3)$ である部分列 $A'_3$ の $4$ つがあります。
$\displaystyle \sum_{A' \in S(A)} M^{s(A')} = M^{s(A'_0)} + M^{s(A'_1)} + M^{s(A'_2)} + M^{s(A'_3)} = 1^0 + 1^1 + 1^3 + 1^4 = 1 + 1 + 1 + 1 = 4 $
であり、$4$ を $B = 2$ で割った余りは $0$ です。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。