No.3226 2×2行列累乗
タグ : / 解いたユーザー数 71
作問者 :
ジュ・ビオレ・グレイス
/ テスター :
👑 
p-adic
問題文
入力から整数 $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もしくは右上の雲マークをクリックしてアカウントを作成してください。