かんプリンの学習記録

勉強したことについてメモしています. 主に競技プログラミングの問題の解説やってます.

yukicoder No.1105 Many Triplets

yukicoder 典型 式変形 競技プログラミング 解説

問題はこちら

問題概要

{A_1,B_1,C_1}が与えられる. 以下の連立漸化式で表される数列{A,B,C}の第{N}項を求めよ.

{\left \{ \begin{array}{l} A_{n+1}=A_n-B_n \\ B_{n+1}=B_n-C_n \\ C_{n+1}=C_n-A_n \\ \end{array} \right.}

思考の流れ

蟻本とか見てるとわかるように線形の連立漸化式は行列累乗で高速に解くことができる.
{\begin{pmatrix} A_N\\ B_N\\ C_N \end{pmatrix} = \begin{pmatrix} 1 & -1 & 0\\ 0 & 1 & -1\\ -1 & 0 & 1 \end{pmatrix}^{N-1} \begin{pmatrix} A_1\\ B_1\\ C_1 \end{pmatrix}}

{-1≡10^9+6(mod10^9+7)}に注意


提出プログラム

https://yukicoder.me/submissions/506432


感想

知ってたらすぐ解けそうな問題