読者です 読者をやめる 読者になる 読者になる

phyllo’s algorithm note

レッドコーダーへの道のりは遠い。休んでる場合じゃない!

yukicoder No.492 IOI数列

問題

IOI数列は、1,101,10101,1010101,...とa_1=1, a_i=100*a_{i-1}+1であるような数列である。
第N項について、1000000007で割ったあまりと101010101010101010101で割ったあまりを求めよ。

制約

1 <= N <= 10^18

解説

第N項を計算したい。
後者の10101...で割ったあまりは、64bit整数に収まらないが、パターンの繰り返しなので、それで答えればよい。
前者の1000000007で割ったあまりを考える。

特性方程式

「a_n = b*a_n + c」の形をしているので、特性方程式x=bx+cを解いてあげれば等比数列として考えられる。

x=100x+1 <=> x = -1/99

よって、「(a_{n+1}-x)=100*(a_{n}-x)」となるので、一般項は、「a_{n+1} = 100^n * (a_1 - x) + x」となる。
展開すると、a_{n+1}=(100^{n+1} - 1)/99なので、「a_n=(100^n - 1)/99」になる。

この計算を、MODでの累乗(繰り返し二乗法)や逆元(拡張ユークリッド互除法を使う方法)を使ってあげれば高速に求められる。

行列累乗

より一般に、m項間漸化式について、一つ次の項を求めるような行列計算を立てると、第N項を行列累乗で求められる。

v_{n+m} = (a_{n+m}, a_{n+m-1}, ..., a_{n+1})^Tとして、「v_{n+m} = X * v_{n+m-1}」となるような行列Xを作れれば、第n項は「v_{n+m-1} = X^n * v_{m}」のように書ける。

今回の漸化式は定数項があるので、
\begin{pmatrix} a_{n+1} \\ 1 \end{pmatrix} = \begin{pmatrix} 100&1 \\ 0&1 \end{pmatrix} * \begin{pmatrix} a_{n} \\ 1 \end{pmatrix}
から
\begin{pmatrix} a_{n+1} \\ 1 \end{pmatrix} = \begin{pmatrix} 100&1 \\ 0&1 \end{pmatrix}^n * \begin{pmatrix} a_{1} \\ 1 \end{pmatrix}
という式になる。行列の累乗は繰り返し二乗法を使ってO(m^3 log n)または高速にO(m^2 log n)の計算量で求められる。

反省

  • 漸化式は行列累乗を検討