[yukicoder] No.793 うし数列 2

うし数列 2

https://yukicoder.me/problems/no/793

考え方

題意

\( E_i = 13…3 \) となるような数列に対して、\( E_N \) を \( 10^9 + 7 \) で割った余りを求めます。

方針

\( E_1 = 13 \) であり、\( E_2 = 10E_1 + 3 \) となることを考えると、\(E_n = 10E_{n – 1} + 3 \) が成り立つことが分かります。ここで、この漸化式を行列を用いて表現すると、

\[
\begin{bmatrix}
E_n\\
1
\end{bmatrix}
=
\begin{bmatrix}
10 & 3\\
0 & 1
\end{bmatrix}
\begin{bmatrix}
E_{n – 1}\\
1
\end{bmatrix}
\]

となります。上式は、

\[
\begin{bmatrix}
E_n\\
1
\end{bmatrix}
=
\begin{bmatrix}
10 & 3\\
0 & 1
\end{bmatrix}
^{n-1}
\begin{bmatrix}
E_{1}\\
1
\end{bmatrix}
\]

となるので、行列の累乗を効率よく求めることで、解答が導けます。これは、繰り返し二乗法を用いて計算することができます。

\[
A =
\begin{bmatrix}
10 & 3\\
0 & 1
\end{bmatrix}
\]

とすると、\( A^n \) を求めるには、\( n \) を二進数に変換したとき、ビットが立っている箇所の累乗が分かれば良いです。また、\( A^0 = I \) (単位表列)とします。

例えば、\( n = 13 \) では、\( 13 = 2^0 + 2^2 + 2^3 \) なので、

\[ A^{13} = AA^4A^8\]

となります。\( A^2 = AA\)であり、\( A^4 = (A^2)^2 \)、\(A^8 = (A^4)^2\) と計算することができます。

コード

感想

一般項を求めてから逆元を用いて計算する方法もありますが、行列を使うと逆元を考えなくても良くなります。

シェアする

  • このエントリーをはてなブックマークに追加

フォローする