No.3227 Matrix Query
タグ : / 解いたユーザー数 58
作問者 :
ジュ・ビオレ・グレイス
/ テスター :
👑 
p-adic
時間制限
本問題の時間制限は 8000ms です。問題文
入力から正整数 $K, N$ が与えられます。はじめに $2 \times 2$ 行列の列 $X^{(1)}, \dots, X^{(N)}$ が入力から $2\times 2$ 行列 $A^{(1)}, \dots, A^{(N)}$ と与えられます。
以下の $Q$ 個のクエリを順番に処理し、結果を出力してください。
各クエリは $1 \leq i \leq N$ となる整数 $i$, $2\times 2$ 行列 $Y$ 及び $1 \leq L \leq R \leq N$ を満たす整数 $L, R$ からなる4つ組 $(i, Y, L, R)$ です。
このクエリを次のように処理します:
- 行列 $X^{(i)}$ に $Y$ を代入する
- 行列の積 $Z = X^{(L)} \cdots X^{(R)} = \begin{pmatrix}a & b \\ c & d\end{pmatrix}$ を計算し、$a, b, c, d$ を $K$ で割った余り $a', b', c', d'$（以降クエリの結果と呼ぶ）を求める
ただし、整数を $K$ で割った余りは常に $0$ 以上 $K$ 未満です。
入力
$K \ N$
$A^{(1)}_{1, 1} \ A^{(1)}_{1, 2}$
$A^{(1)}_{2, 1} \ A^{(1)}_{2, 2}$
$\vdots$
$A^{(N)}_{1, 1} \ A^{(N)}_{1, 2}$
$A^{(N)}_{2, 1} \ A^{(N)}_{2, 2}$
$Q$
$i_1 \ L_1 \ R_1$
$Y^{(1)}_{1, 1}, Y^{(1)}_{1, 2}$
$Y^{(1)}_{2, 1}, Y^{(1)}_{2, 2}$
$\vdots$
$i_Q \ L_Q \ R_Q$
$Y^{(Q)}_{1, 1}, Y^{(Q)}_{1, 2}$
$Y^{(Q)}_{2, 1}, Y^{(Q)}_{2, 2}$
$2 \leq K < 2^{31},$
$1 \leq N \leq 10^5,$
$1 \leq Q \leq 10^5,$
$1 \leq i_q \leq N,$
$1 \leq L_q \leq R_q \leq N$
$-10^8 \leq A^{(n)}_{i, j}, \, Y^{(n)}_{i, j} \leq 10^8$ は整数です。
$A^{(n)} = \begin{pmatrix} A^{(n)}_{1, 1} & A^{(n)}_{1, 2} \\ A^{(n)}_{2, 1} & A^{(n)}_{2, 2}\end{pmatrix}, \ Y^{(q)} = \begin{pmatrix} Y^{(q)}_{1, 1} & Y^{(q)}_{1, 2} \\ Y^{(q)}_{2, 1} & Y^{(q)}_{2, 2}\end{pmatrix}$ とし、
$q$ 番目のクエリは $(i_q, Y^{(q)}, L_q, R_q)$ です。
出力
$q$ 番目までのクエリを順に処理した際のクエリの結果 $a', b', c', d'$ を
$a' \ b' \\ c' \ d'$と各 $q$ について順番に出力してください。
つまり、$2q-1, \, 2q$ 行目に $q$ 番目までのクエリを順に処理した際の「クエリの結果」を出力してください。
最後に改行してください。
サンプル
サンプル1
入力
100 3 1 2 3 4 1 3 5 7 2 4 1 3 2 2 2 3 3 1 -18 5 1 1 2 9 2 8 3
出力
7 15 69 43 91 19 70 23
はじめ、$X^{(1)} = \begin{pmatrix}1 & 2 \\ 3 & 4\end{pmatrix}, \ X^{(2)} = \begin{pmatrix}1 & 3 \\ 5 & 7\end{pmatrix}, \ X^{(3)} = \begin{pmatrix}2 & 4 \\ 1 & 3\end{pmatrix}$ です。
また、$Y^{(1)} = \begin{pmatrix}3 & 1 \\ -18 & 5\end{pmatrix}, \ Y^{(2)} = \begin{pmatrix}9 & 2 \\ 8 & 3\end{pmatrix}$ です。
$1$ 番目のクエリ $(2, Y^{(1)}, 2, 3)$ を処理すると $X^{(2)}$ に $Y^{(1)}$ が代入され、
$X^{(1)} = \begin{pmatrix}1 & 2 \\ 3 & 4\end{pmatrix}, \ X^{(2)} = \begin{pmatrix}3 & 1 \\ -18 & 5\end{pmatrix}, \ X^{(3)} = \begin{pmatrix}2 & 4 \\ 1 & 3\end{pmatrix}$
となります。
$X^{(2)} X^{(3)} = \begin{pmatrix}3 & 1 \\ -18 & 5\end{pmatrix} \begin{pmatrix}2 & 4 \\ 1 & 3\end{pmatrix} = \begin{pmatrix}7 & 15 \\ -31 & -57\end{pmatrix}$ なので、$1$ 番目のクエリを処理した際の「クエリの結果」は $7, 15, 69, 43$ です。
したがって、まず
7 15 69 43が出力されます。
次に、$2$ 番目のクエリ $(1, Y^{(2)}, 1, 2)$ を処理すると $X^{(1)}$ に $Y^{(2)}$ が代入され、
$X^{(1)} = \begin{pmatrix}9 & 2 \\ 8 & 3\end{pmatrix}, \ X^{(2)} = \begin{pmatrix}3 & 1 \\ -18 & 5\end{pmatrix}, \ X^{(3)} = \begin{pmatrix}2 & 4 \\ 1 & 3\end{pmatrix}$
となります。
$X^{(1)} X^{(2)} = \begin{pmatrix}9 & 2 \\ 8 & 3\end{pmatrix} \begin{pmatrix}3 & 1 \\ -18 & 5\end{pmatrix} = \begin{pmatrix}-9 & 19 \\ -30 & 23\end{pmatrix}$ なので、$2$ 番目までのクエリを順に処理した際の「クエリの結果」は $91, 19, 70, 23$ です。
したがって、次に
91 19 70 23が出力されます。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。