No.2443 特殊線形群の標準表現
タグ : / 解いたユーザー数 44
作問者 : 👑
p-adic
/ テスター :
MasKoaTS
注意
この問題の実行時間制限は3000[ms]です。
問題文
入力の最初に $3$ 個の正整数 $N, B, Q$ と、$N$ 個の $2$ 次正方行列が与えられます。
$N$ 以下の各正整数 $n$ に対し、$n$ 個目に与えられる $2$ 次正方行列を $A_n$ と置くと、$A_n$ は以下の $2$ 条件を全て満たします：
- $A_n$ の各成分は整数である。
- $A_n$ の行列式 $\det(A_n)$ は $1$ である。
以下で説明される $Q$ 個のクエリを与えられた順に処理してください。
各クエリは $0 \leq L \leq R \leq N$ を満たす $4$ 個の整数 $L, R, x, y$ の組 $(L,R,x,y)$ です。
クエリ $(L,R,x,y)$ は次のように処理します。
- $L \leq n \leq R$ を満たす各整数 $n$ に対し、整数 $z_n, w_n$ を以下のように再帰的に（$n$ の小さい順に）定める：
- $n = L$ ならば、 $\displaystyle \left( \begin{array}{c} z_n \\ w_n \end{array} \right) = \left( \begin{array}{c} x \\ y \end{array} \right) $ である。
- $n > L$ ならば、 $\displaystyle \left( \begin{array}{c} z_n \\ w_n \end{array} \right) = A_n \left( \begin{array}{c} z_{n-1} \\ w_{n-1} \end{array} \right) $ である。
- $z_R, w_R$ をそれぞれ $B$ で割った余りを求める。（以下これらをそのクエリに対する回答と呼ぶ）
ただし整数 $n$ に対し、$n$ を $B$ で割った余りとは $2$ 条件
- $0 \leq r < B$ である。
- $n = qB + r$ を満たす整数 $q$ が存在する。
を全て満たす一意な整数 $r$ を指します。
背景
整数全体の集合 $\mathbb{Z}$ や実数全体の集合 $\mathbb{R}$ は通常の四則演算に関して可換環という代数構造をなします。一般の可換環 $R$ に対し、行列式が $1$ である $R$ 係数 $2$ 次正方行列全体は特殊線形群 $\textrm{SL}_2(R)$ と呼ばれ、行列の通常の積に関して群という代数構造をなすことが知られています。特殊線形群は整数論や表現論を始めとした様々な分野で現れる非常に重要な対象です。
入力
$N$ 以下の各正整数 $n$ と $2$ 以下の各正整数 $i,j$ に対し、$A_n$ の $(i,j)$ 成分を $A_{n,i,j}$ と置きます。
$Q$ 以下の各正整数 $q$ に対し、$q$ 個目のクエリを $(L_q,R_q,x_q,y_q)$ と置きます。
この時、入力は以下の形式で標準入力から $1 + 2N + Q$ 行で与えられます：
- $1$ 行目に $N, B, Q$ が半角空白区切りで与えられます。
- $N$ 以下の各正整数 $n$ に対し、
- $2n$ 行目に $A_n$ の第 $1$ 行の各成分 $A_{n,1,1}, A_{n,1,2}$ が半角空白区切りで与えられます。
- $2n+1$ 行目に $A_n$ の第 $2$ 行の各成分 $A_{n,2,1}, A_{n,2,2}$ が半角空白区切りで与えられます。
- $Q$ 以下の各正整数 $q$ に対し、$2N + 1 + q$ 行目に $q$ 個目のクエリの各成分 $L_q,R_q,x_q,y_q$ が半角空白区切りで与えられます。
$N$ $B$ $Q$
$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}$
$L_1$ $R_1$ $x_1$ $y_1$
$\vdots$
$L_Q$ $R_Q$ $x_Q$ $y_Q$
制約
入力は以下の制約を満たします：
- $N$ は $1 \leq N \leq 10^5$ を満たす整数である。
- $B$ は $1 \leq B \leq 10^9$ を満たす整数である。
- $Q$ は $1 \leq Q \leq 10^5$ を満たす整数である。
- $N$ 以下の任意の正整数 $n$ に対し、
- $2$ 以下の任意の正整数 $i,j$ に対し、$A_{n,i,j}$ は $-10^9 \leq A_{n,i,j} \leq 10^9$ を満たす整数である。
- $\det(A_n) = 1$ すなわち $A_{n,1,1} A_{n,2,2} - A_{n,1,2} A_{n,2,1} = 1$ である。
- $Q$ 以下の任意の正整数 $q$ に対し、
- $L_q,R_q$ は $0 \leq L_q \leq R_q \leq N$ を満たす整数である。
- $x_q$ は $-10^9 \leq x_q \leq 10^9$ を満たす整数である。
- $y_q$ は $-10^9 \leq y_q \leq 10^9$ を満たす整数である。
出力
$Q$ 以下の各正整数 $q$ に対し、$q$ 行目に $q$ 個目のクエリに対する回答（クエリの最後に得た $z_R, w_R$ をそれぞれ $B$ で割った余り）を半角空白区切りで出力してください。
最後に改行してください。
サンプル
サンプル1
入力
1 1 1 1 0 0 1 0 1 1 2
出力
0 0
与えられる $2$ 次正方行列は
$\displaystyle A_1 = \left( \begin{array}{cc} 1 & 0 \\ 0 & 1 \end{array} \right) $
の $1$ 個だけです。$\det(A_1) = 1 \times 1 - 0 \times 0 = 1$ です。
与えられるクエリは $(L_1,R_1,x_1,y_1) = (0,1,1,2)$ です。$L_1 \leq n \leq R_1$ を満たす整数 $n$ は $0,1$ があり、このクエリに対して定義に従って $(z_n,w_n)$ を計算すると
$\displaystyle \begin{array}{ccccccc} \displaystyle \left( \begin{array}{cc} z_0 \\ w_0 \end{array} \right) &\displaystyle = &\displaystyle \left( \begin{array}{cc} z_{L_1} \\ w_{L_1} \end{array} \right) &\displaystyle = &\displaystyle \left( \begin{array}{cc} x_1 \\ y_1 \end{array} \right) &\displaystyle = &\displaystyle \left( \begin{array}{cc} 1 \\ 2 \end{array} \right) \\ \displaystyle \left( \begin{array}{cc} z_1 \\ w_1 \end{array} \right) &\displaystyle = &\displaystyle A_1 \left( \begin{array}{cc} z_0 \\ w_0 \end{array} \right) &\displaystyle = &\displaystyle \left( \begin{array}{cc} 1 & 0 \\ 0 & 1 \end{array} \right) \left( \begin{array}{cc} 1 \\ 2 \end{array} \right) &\displaystyle = &\displaystyle \left( \begin{array}{cc} 1 \\ 2 \end{array} \right) \end{array} $
となります。従って $(z_{R_1},w_{R_1}) = (z_1,w_1) = (1,2)$ であるので、$1,2$ をそれぞれ $B = 1$ で割った余り $0,0$ を半角空白区切りで出力してください。
今回は $Q = 1$ であるので、これにて全てのクエリが処理できました。
サンプル2
入力
1 2 2 1 -2 1 -1 0 0 1 0 1 1 0 1
出力
1 0 0 1
与えられる $2$ 次正方行列は
$\displaystyle A_1 = \left( \begin{array}{cc} 1 & -2 \\ 1 & -1 \end{array} \right) $
の $1$ 個だけです。$\det(A_1) = 1 \times (-1) - (-2) \times 1 = 1$ です。
$1$ 個目のクエリは $(L_1,R_1,x_1,y_1) = (0,0,1,0)$ です。$L_1 \leq n \leq R_1$ を満たす整数 $n$ は $0$ に限られ、このクエリに対して定義に従って $(z_n,w_n)$ を計算すると
$\displaystyle \left( \begin{array}{cc} z_0 \\ w_0 \end{array} \right) = \left( \begin{array}{cc} z_{L_1} \\ w_{L_1} \end{array} \right) = \left( \begin{array}{cc} x_1 \\ y_1 \end{array} \right) = \left( \begin{array}{cc} 1 \\ 0 \end{array} \right) $
となります。従って $(z_{R_1},w_{R_1}) = (z_0,w_0) = (1,0)$ であるので、$1,0$ をそれぞれ $B = 2$ で割った余り $1,0$ を半角空白区切りで出力してください。
$2$ 個目のクエリは $(L_2,R_2,x_2,y_2) = (1,1,0,1)$ です。$L_2 \leq n \leq R_2$ を満たす整数 $n$ は $1$ に限られ、このクエリに対して定義に従って $(z_n,w_n)$ を計算すると
$\displaystyle \left( \begin{array}{cc} z_1 \\ w_1 \end{array} \right) = \left( \begin{array}{cc} z_{L_2} \\ w_{L_2} \end{array} \right) = \left( \begin{array}{cc} x_2 \\ y_2 \end{array} \right) = \left( \begin{array}{cc} 0 \\ 1 \end{array} \right) $
となります。従って $(z_{R_2},w_{R_2}) = (z_1,w_1) = (0,1)$ であるので、$0,1$ をそれぞれ $B = 2$ で割った余り $0,1$ を半角空白区切りで出力してください。
今回は $Q = 2$ であるので、これにて全てのクエリが処理できました。
サンプル3
入力
2 3 2 2 1 1 1 -1 -1 -1 -2 0 1 0 1 0 2 0 1
出力
1 1 1 0
与えられる $2$ 次正方行列は
$\displaystyle \begin{array}{rcl} \displaystyle A_1 &\displaystyle = &\displaystyle \left( \begin{array}{cc} 2 & 1 \\ 1 & 1 \end{array} \right) \\ \displaystyle A_2 &\displaystyle = &\displaystyle \left( \begin{array}{cc} -1 & -1 \\ -1 & -2 \end{array} \right) \end{array} $
の $2$ 個です。$\det(A_1) = 2 \times 1 - 1 \times 1 = 1$ かつ $\det(A_2) = (-1) \times (-2) - (-1) \times (-1) = 1$ です。
$1$ 個目のクエリは $(L_1,R_1,x_1,y_1) = (0,1,0,1)$ です。$L_1 \leq n \leq R_1$ を満たす整数 $n$ は $0,1$ があり、このクエリに対して定義に従って $(z_n,w_n)$ を計算すると
$\displaystyle \begin{array}{ccccccc} \displaystyle \left( \begin{array}{cc} z_0 \\ w_0 \end{array} \right) &\displaystyle = &\displaystyle \left( \begin{array}{cc} z_{L_1} \\ w_{L_1} \end{array} \right) &\displaystyle = &\displaystyle \left( \begin{array}{cc} x_1 \\ y_1 \end{array} \right) &\displaystyle = &\displaystyle \left( \begin{array}{cc} 0 \\ 1 \end{array} \right) \\ \displaystyle \left( \begin{array}{cc} z_1 \\ w_1 \end{array} \right) &\displaystyle = &\displaystyle A_1 \left( \begin{array}{cc} z_0 \\ w_0 \end{array} \right) &\displaystyle = &\displaystyle \left( \begin{array}{cc} 2 & 1 \\ 1 & 1 \end{array} \right) \left( \begin{array}{cc} 0 \\ 1 \end{array} \right) &\displaystyle = &\displaystyle \left( \begin{array}{cc} 1 \\ 1 \end{array} \right) \end{array} $
となります。従って $(z_{R_1},w_{R_1}) = (z_1,w_1) = (1,1)$ であるので、$1,1$ をそれぞれ $B = 3$ で割った余り $1,1$ を半角空白区切りで出力してください。
$2$ 個目のクエリは $(L_2,R_2,x_2,y_2) = (0,2,0,1)$ です。$L_2 \leq n \leq R_2$ を満たす整数 $n$ は $0,1,2$ があり、このクエリに対して定義に従って $(z_n,w_n)$ を計算すると $(L_2,x_2,y_2) = (L_1,x_1,y_1)$ より $(z_0,w_0), (z_1,w_1)$ の値は $1$ 個目のクエリに対する値と同じであり、
$\displaystyle \left( \begin{array}{cc} z_2 \\ w_2 \end{array} \right) = A_2 \left( \begin{array}{cc} z_1 \\ w_1 \end{array} \right) = \left( \begin{array}{cc} -1 & -1 \\ -1 & -2 \end{array} \right) \left( \begin{array}{cc} 1 \\ 1 \end{array} \right) = \left( \begin{array}{cc} -2 \\ -3 \end{array} \right) $
となります。従って $(z_{R_2},w_{R_2}) = (z_2,w_2) = (-2,-3)$ であるので、$-2,-3$ をそれぞれ $B = 3$ で割った余り $1,0$ を半角空白区切りで出力してください。
今回は $Q = 2$ であるので、これにて全てのクエリが処理できました。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。