yukicoder No.673 カブトムシ

この記事は yukicoder No.673 カブトムシ の解説です。

\(n\) 年目の大晦日のカブトムシの匹数を \(X_n\)（ただし \(X_0=0\)）とすると、$$\begin{eqnarray}X_n&=&(X_{n-1}+B)×C\\&=&C\cdot X_{n-1}+BC\cdot 1\end{eqnarray}$$となる。この遷移を行列で表すと、$$\begin{pmatrix}X_n\\1\end{pmatrix}=\begin{pmatrix}C&BC\\0&1\end{pmatrix}\begin{pmatrix}X_{n-1}\\1\end{pmatrix}$$であるので、\(X_D\) については、$$\begin{pmatrix}X_D\\1\end{pmatrix}=\begin{pmatrix}C&BC\\0&1\end{pmatrix}^D\begin{pmatrix}X_0\\1\end{pmatrix}$$で求まる。

あとは mod をとりながら繰り返し2乗法で行列累乗するだけ。