yukicoder No.1136 Four Points Tour - かんプリンの学習記録

あんまり見てなかったけど本当はここらしい

問題概要
思考の流れ
提出プログラム
感想

問題概要

4点 ${A,B,C,D}$ があり, 最初 ${A}$ にいる. 今いる点から別の点に移動することを ${N}$ 回繰り返す. ${N}$ 回の移動の後に ${A}$ にいる移動方法が何通りあるか求めよ.

思考の流れ

${n}$ 回の移動後に ${A,B,C,D}$ にいる移動方法の数をそれぞれ ${A_n,B_n,C_n,D_n}$ とすると漸化式は以下のようになる.

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

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

提出プログラム

https://yukicoder.me/submissions/520003

感想

いろんな解き方がある問題