問題一覧 > 通常問題

No.3226 2×2行列累乗

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 68
作問者 : ジュ・ビオレ・グレイス / テスター : 👑 p-adic
ProblemId : 12524 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-07-20 00:42:25

問題文

入力から整数 $A, B, C, D, S, T, N, K$ が与えられます。$2\times 2$ 行列 $M$ を

$M = \begin{pmatrix} A & B \\ C & D \end{pmatrix}$

と定めます。また、

$M^N \begin{pmatrix} S \\ T \end{pmatrix} = \begin{pmatrix} R \\ U\end{pmatrix}$

とします。$R, U$ を $K$ で割った余り ($0$ 以上 $K$ 未満の整数です) $R', U'$ をそれぞれ求めてください。

行列の積について $2 \times 2$ 行列の積は

$\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}$

と定義されます。累乗は

$M^0 = \begin{pmatrix}1 & 0 \\ 0 & 1\end{pmatrix}, \ M^{n+1} = M^n M$ と定義されます。また、

$\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}$

と定義されます。

入力

$A \ B \\ C \ D \\ S \ T \\ N \ K$

$A, B, C, D, S, T$ は $-10^8$ 以上 $10^8$ 以下、$N$ は $0$ 以上 $10^{18}$ 以下、$K$ は $2$ 以上 $10^8$ 以下の整数です。

出力

問題文で定義された $R', U'$ を

$R' \ U'$
と出力してください。 最後に改行してください。

サンプル

サンプル1
入力
1 0
0 1
-9 12
7 5
出力
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},$
$-9, 12$ を $5$ で割った余りはそれぞれ $1, 2$ です。

サンプル2
入力
1 -2
3 4
-5 -6
7 8
出力
3 3

サンプル3
入力
10000 9797
1234 9876
9898 8989
1717 7777
出力
2020 1616

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。