No.3226 2×2 Matrix Exponentiation
タグ : / 解いたユーザー数 75
作問者 :
ジュ・ビオレ・グレイス
/ テスター :
👑 Problem Statement
You are given integers $A, B, C, D, S, T, N, K$ from the input. Define the $2\times 2$ matrix $M$ as
$M = \begin{pmatrix} A & B \\ C & D \end{pmatrix}$
. Also, let
$M^N \begin{pmatrix} S \\ T \end{pmatrix} = \begin{pmatrix} R \\ U\end{pmatrix}$
. Find $R', U'$, the remainders (integers at least $0$ and less than $K$) when $R, U$ are divided by $K$, respectively.
About matrix multiplication
The product of $2 \times 2$ matrices is defined as$\begin{pmatrix} a_{1, 1} & a_{1, 2} \\ a_{2, 1} & a_{2, 2} \end{pmatrix} \begin{pmatrix} b_{1, 1} & b_{1, 2} \\ b_{2, 1} & b_{2, 2} \end{pmatrix} = \begin{pmatrix} a_{1, 1} b_{1, 1} + a_{1, 2}b_{2, 1} & a_{1, 1}b_{1, 2} + a_{1, 2}b_{2, 2} \\ a_{2, 1}b_{1, 1} + a_{2, 2}b_{2, 1} & a_{2, 1}b_{1, 2} + a_{2, 2}b_{2, 2} \end{pmatrix}$
. Powers are defined as
$M^0 = \begin{pmatrix}1 & 0 \\ 0 & 1\end{pmatrix}, \ M^{n+1} = M^n M$ . Also, the following is defined:
$\begin{pmatrix} a_{1, 1} & a_{1, 2} \\ a_{2, 1} & a_{2, 2} \end{pmatrix} \begin{pmatrix} b_1 \\ b_2 \end{pmatrix} = \begin{pmatrix} a_{1, 1} b_1 + a_{1, 2}b_2 \\ a_{2, 1}b_1 + a_{2, 2}b_2\end{pmatrix}$
.
Input
$A \ B \\ C \ D \\ S \ T \\ N \ K$
$A, B, C, D, S, T$ are integers between $-10^8$ and $10^8$, inclusive; $N$ is an integer between $0$ and $10^{18}$, inclusive; and $K$ is an integer between $2$ and $10^8$, inclusive.
Output
Output $R', U'$, as defined in the problem statement, in the following format:
$R' \ U'$Print a newline at the end.
Sample
Sample 1
Input
1 0 0 1 -9 12 7 5
Output
1 2
$\begin{pmatrix} 1 & 0 \\ 0 & 1\end{pmatrix} ^ 7 = \begin{pmatrix} 1 & 0 \\ 0 & 1\end{pmatrix},$
$\begin{pmatrix} 1 & 0 \\ 0 & 1\end{pmatrix}$ $\begin{pmatrix} -9 \\ 12\end{pmatrix} = \begin{pmatrix}-9 \\ 12\end{pmatrix},$
The remainders when $-9, 12$ are divided by $5$ are $1, 2$, respectively.
Sample 2
Input
1 -2 3 4 -5 -6 7 8
Output
3 3
Sample 3
Input
10000 9797 1234 9876 9898 8989 1717 7777
Output
2020 1616
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。