No.2443 Standard Representation of the Special Linear Group
p-adic
MasKoaTSNote
The execution time limit for this problem is 3000[ms].
Problem Statement
At the beginning of the input, you are given $3$ positive integers $N, B, Q$ and $N$ square matrices of order $2$.
For each positive integer $n$ not exceeding $N$, let $A_n$ be the $n$-th given square matrix of order $2$. Then $A_n$ satisfies both of the following $2$ conditions:
- Each entry of $A_n$ is an integer.
- The determinant $\det(A_n)$ of $A_n$ is $1$.
Process the $Q$ queries described below in the given order.
Each query is a tuple $(L,R,x,y)$ of $4$ integers $L, R, x, y$ satisfying $0 \leq L \leq R \leq N$.
A query $(L,R,x,y)$ is processed as follows.
- For each integer $n$ satisfying $L \leq n \leq R$, define integers $z_n, w_n$ recursively (in increasing order of $n$) as follows:
- If $n = L$, then $\displaystyle \left( \begin{array}{c} z_n \\ w_n \end{array} \right) = \left( \begin{array}{c} x \\ y \end{array} \right) $ .
- If $n > L$, then $\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) $ .
- Find the remainders when $z_R, w_R$ are each divided by $B$. (Hereafter, these are called the answer to the query.)
Here, for an integer $n$, the remainder when $n$ is divided by $B$ refers to the unique integer $r$ satisfying both of the $2$ conditions
- $0 \leq r < B$.
- There exists an integer $q$ satisfying $n = qB + r$.
.
Background
The set of all integers $\mathbb{Z}$ and the set of all real numbers $\mathbb{R}$ form an algebraic structure called a commutative ring under the usual arithmetic operations. For a general commutative ring $R$, the set of all square matrices of order $2$ with coefficients in $R$ whose determinant is $1$ is called the special linear group $\textrm{SL}_2(R)$, and it is known to form an algebraic structure called a group under the usual matrix product. The special linear group is a very important object that appears in various fields, including number theory and representation theory.
Input
For each positive integer $n$ not exceeding $N$ and each pair of positive integers $i,j$ not exceeding $2$, let $A_{n,i,j}$ be the $(i,j)$ entry of $A_n$.
For each positive integer $q$ not exceeding $Q$, let $(L_q,R_q,x_q,y_q)$ be the $q$-th query.
Then, the input is given from standard input in $1 + 2N + Q$ lines in the following format:
- Line $1$ contains $N, B, Q$, separated by half-width spaces.
- For each positive integer $n$ not exceeding $N$,
- Line $2n$ contains the entries $A_{n,1,1}, A_{n,1,2}$ of row $1$ of $A_n$, separated by half-width spaces.
- Line $2n+1$ contains the entries $A_{n,2,1}, A_{n,2,2}$ of row $2$ of $A_n$, separated by half-width spaces.
- For each positive integer $q$ not exceeding $Q$, line $2N + 1 + q$ contains the components $L_q,R_q,x_q,y_q$ of the $q$-th query, separated by half-width spaces.
$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$
Constraints
The input satisfies the following constraints:
- $N$ is an integer satisfying $1 \leq N \leq 10^5$.
- $B$ is an integer satisfying $1 \leq B \leq 10^9$.
- $Q$ is an integer satisfying $1 \leq Q \leq 10^5$.
- For any positive integer $n$ not exceeding $N$,
- for any positive integers $i,j$ not exceeding $2$, $A_{n,i,j}$ is an integer satisfying $-10^9 \leq A_{n,i,j} \leq 10^9$.
- $\det(A_n) = 1$, that is, $A_{n,1,1} A_{n,2,2} - A_{n,1,2} A_{n,2,1} = 1$.
- For any positive integer $q$ not exceeding $Q$,
- $L_q,R_q$ are integers satisfying $0 \leq L_q \leq R_q \leq N$.
- $x_q$ is an integer satisfying $-10^9 \leq x_q \leq 10^9$.
- $y_q$ is an integer satisfying $-10^9 \leq y_q \leq 10^9$.
Output
For each positive integer $q$ not exceeding $Q$, output on line $q$ the answer to the $q$-th query (the remainders when $z_R, w_R$ obtained at the end of the query are each divided by $B$), separated by a half-width space.
Print a newline at the end.
Sample
Sample 1
Input
1 1 1 1 0 0 1 0 1 1 2
Output
0 0
The given square matrix of order $2$ is
$\displaystyle A_1 = \left( \begin{array}{cc} 1 & 0 \\ 0 & 1 \end{array} \right) $
only, so there is just $1$ matrix. We have $\det(A_1) = 1 \times 1 - 0 \times 0 = 1$.
The given query is $(L_1,R_1,x_1,y_1) = (0,1,1,2)$. The integers $n$ satisfying $L_1 \leq n \leq R_1$ are $0,1$, and computing $(z_n,w_n)$ for this query according to the definition gives
$\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} $
. Therefore, $(z_{R_1},w_{R_1}) = (z_1,w_1) = (1,2)$, so output $0,0$, the remainders when $1,2$ are each divided by $B = 1$, separated by a half-width space.
Since $Q = 1$ in this case, all queries have now been processed.
Sample 2
Input
1 2 2 1 -2 1 -1 0 0 1 0 1 1 0 1
Output
1 0 0 1
The given square matrix of order $2$ is
$\displaystyle A_1 = \left( \begin{array}{cc} 1 & -2 \\ 1 & -1 \end{array} \right) $
only, so there is just $1$ matrix. We have $\det(A_1) = 1 \times (-1) - (-2) \times 1 = 1$.
The $1$-st query is $(L_1,R_1,x_1,y_1) = (0,0,1,0)$. The only integer $n$ satisfying $L_1 \leq n \leq R_1$ is $0$, and computing $(z_n,w_n)$ for this query according to the definition gives
$\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) $
. Therefore, $(z_{R_1},w_{R_1}) = (z_0,w_0) = (1,0)$, so output $1,0$, the remainders when $1,0$ are each divided by $B = 2$, separated by a half-width space.
The $2$-nd query is $(L_2,R_2,x_2,y_2) = (1,1,0,1)$. The only integer $n$ satisfying $L_2 \leq n \leq R_2$ is $1$, and computing $(z_n,w_n)$ for this query according to the definition gives
$\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) $
. Therefore, $(z_{R_2},w_{R_2}) = (z_1,w_1) = (0,1)$, so output $0,1$, the remainders when $0,1$ are each divided by $B = 2$, separated by a half-width space.
Since $Q = 2$ in this case, all queries have now been processed.
Sample 3
Input
2 3 2 2 1 1 1 -1 -1 -1 -2 0 1 0 1 0 2 0 1
Output
1 1 1 0
The given square matrices of order $2$ are
$\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} $
, so there are $2$ matrices. We have $\det(A_1) = 2 \times 1 - 1 \times 1 = 1$ and $\det(A_2) = (-1) \times (-2) - (-1) \times (-1) = 1$.
The $1$-st query is $(L_1,R_1,x_1,y_1) = (0,1,0,1)$. The integers $n$ satisfying $L_1 \leq n \leq R_1$ are $0,1$, and computing $(z_n,w_n)$ for this query according to the definition gives
$\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} $
. Therefore, $(z_{R_1},w_{R_1}) = (z_1,w_1) = (1,1)$, so output $1,1$, the remainders when $1,1$ are each divided by $B = 3$, separated by a half-width space.
The $2$-nd query is $(L_2,R_2,x_2,y_2) = (0,2,0,1)$. The integers $n$ satisfying $L_2 \leq n \leq R_2$ are $0,1,2$. Computing $(z_n,w_n)$ for this query according to the definition, since $(L_2,x_2,y_2) = (L_1,x_1,y_1)$, the values of $(z_0,w_0), (z_1,w_1)$ are the same as those for the $1$-st query, and
$\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) $
. Therefore, $(z_{R_2},w_{R_2}) = (z_2,w_2) = (-2,-3)$, so output $1,0$, the remainders when $-2,-3$ are each divided by $B = 3$, separated by a half-width space.
Since $Q = 2$ in this case, all queries have now been processed.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。