No.3492 区間冪乗加算一点取得
p-adic注意
この問題の実行時間制限は4000[ms]です。実行時間が厳しいので高速な言語・処理系の仕様を推奨します。
参考までにwriter解の実行時間はc++で577[ms]、PyPy3で1596[ms]、Python3で10000[ms]超すなわち TLE となります。
問題文
入力の最初に $3$ 個の正整数 $N, B, Q$ が与えられます。
長さ $N$ の非負整数列 $A$ が、最初は $0$ のみを成分に持つ数列として与えられています。
以下で説明する $Q$ 個のクエリを与えられた順に処理することで $A$ を更新してください。
各クエリは $1 \leq L \leq M \leq R \leq N$ を満たす $3$ 個の整数 $L, M, R$ と $2$ 個の非負整数 $C, D$ の組 $(L,M,R,C,D)$です。
クエリ $(L,M,R,C,D)$ は以下のように処理します：
- まず $L \leq i \leq R$ を満たす各正整数 $i$ に対し、$A$ の $i$ 個目の成分を $A_i + (i+C)^D$ に置き換えることで $A$ を更新する。
- 次に更新後の $A$ に対する $A_M$ を $B$ で割った余りを求める。（以下、この値をこのクエリに対する回答と呼ぶ）
ただし $N$ 以下の各正整数 $i$ に対し、$A_i$ で $A$ の $i$ 個目の成分を表します。
入力
$Q$ 以下の各正整数 $q$ に対し、$q$ 個目のクエリを $(L_q,M_q,R_q,C_q,D_q)$ と置きます。
この時、入力は以下の形式で標準入力から $1 + Q$ 行で与えられます：
- $1$ 行目に $N, B, Q$ が半角空白区切りで与えられます。
- $Q$ 以下の各正整数 $q$ に対し、$1+q$ 行目に $L_q,M_q,R_q,C_q,D_q$ の各成分が半角空白区切りで与えられます。
$N$ $B$ $Q$ $L_1$ $M_1$ $R_1$ $C_1$ $D_1$ $\vdots$ $L_Q$ $M_Q$ $R_Q$ $C_Q$ $D_Q$
制約
入力は以下の制約を満たします：
- $N$ は $1 \leq N \leq 10^4$ を満たす整数
- $B$ は $1 \leq B \leq 10^9$ を満たす整数
- $Q$ は $1 \leq Q \leq 10^4$ を満たす整数
- $Q$ 以下の任意の正整数 $q$ に対し、
- $L_q,M_q,R_q$ は $1 \leq L_q \leq M_q \leq R_q \leq N$ を満たす整数
- $C_q$ は $0 \leq C_q \leq 10^{18}$ を満たす整数
- $D_q$ は $0 \leq D_q \leq 10^2$ を満たす整数
出力
$Q$ 以下の各正整数 $q$ に対し、$q$ 行目に $q$ 個目のクエリに対する回答を出力してください。
最後に改行してください。
サンプル
サンプル1
入力
1 2 1 1 1 1 2 0
出力
1
最初に長さ $N = 1$ の非負整数列 $A$ が $(0)$ として与えられています。
$1$ 個目のクエリ $(L_1,M_1,R_1,C_1,D_1) = (1,1,1,2,0)$ により、まず $A$ が
$\displaystyle (A_1 + (1 + C_1)^{D_1}) = (0 + (1 + 2)^0) = (1) $
に置き換わります。従って更新後の $A$ に対する $A_{M_1} = A_1$ は $1$ であり、$1$ を $B = 2$ で割った余りは $1$ です。
今回は $Q = 1$ なのでこれで全ての処理が終わります。
サンプル2
入力
2 3 1 1 2 2 1 1
出力
0
最初に長さ $N = 2$ の非負整数列 $A$ が $(0,0)$ として与えられています。
$1$ 個目のクエリ $(L_1,M_1,R_1,C_1,D_1) = (1,2,2,1,1)$ により、まず $A$ が
$\displaystyle (A_1 + (1 + C_1)^{D_1},A_2 + (2 + C_1)^{D_1}) = (0 + (1 + 1)^1,0 + (2 + 1)^1) = (2,3) $
に置き換わります。従って更新後の $A$ に対する $A_{M_1} = A_2$ は $3$ であり、$3$ を $B = 3$ で割った余りは $0$ です。
今回は $Q = 1$ なのでこれで全ての処理が終わります。
サンプル3
入力
3 4 2 1 1 2 0 2 2 2 3 2 1
出力
1 0
最初に長さ $N = 3$ の非負整数列 $A$ が $(0,0,0)$ として与えられています。
$1$ 個目のクエリ $(L_1,M_1,R_1,C_1,D_1) = (1,1,2,0,2)$ により、まず $A$ が
$\displaystyle (A_1 + (1 + C_1)^{D_1},A_2 + (2 + C_1)^{D_1},A_3) = (0 + (1 + 0)^2,0 + (2 + 0)^2,0) = (1,4,0) $
に置き換わります。従って更新後の $A$ に対する $A_{M_1} = A_1$ は $1$ であり、$1$ を $B = 4$ で割った余りは $1$ です。
$2$ 個目のクエリ $(L_2,M_2,R_2,C_2,D_2) = (2,2,3,2,1)$ により、まず $A$ が
$\displaystyle (A_1,A_2 + (2 + C_2)^{D_2},A_3 + (3 + C_2)^{D_2}) = (1,4 + (2 + 2)^1,0 + (3 + 2)^1) = (1,8,5) $
に置き換わります。従って更新後の $A$ に対する $A_{M_2} = A_2$ は $8$ であり、$8$ を $B = 4$ で割った余りは $0$ です。
今回は $Q = 2$ なのでこれで全ての処理が終わります。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。