問題一覧 > 通常問題

No.3226 2×2 Matrix Exponentiation

レベル : / AI推定難易度 : 700 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 75
作問者 : ジュ・ビオレ・グレイス / テスター : 👑 p-adic
お気に入りにしたユーザー ProblemId : 12524 / 自分の提出
問題文最終更新日: 2025-07-20 00:42:25
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 477 線形代数コンテスト (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。