問題
IOI数列は、1,101,10101,1010101,...とa_1=1, a_i=100*a_{i-1}+1であるような数列である。
第N項について、1000000007で割ったあまりと101010101010101010101で割ったあまりを求めよ。
解説
第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}」のように書ける。
今回の漸化式は定数項があるので、
から
という式になる。行列の累乗は繰り返し二乗法を使ってO(m^3 log n)または高速にO(m^2 log n)の計算量で求められる。
