No.492

漸化式を変形すると,

$$a_{i+1} + \frac{1}{99} = 100 \left( a_i + \frac{1}{99} \right)$$

となるので,

$$\begin{align} a_i &= 100^{i-1} \left( a_1 + \frac{1}{99} \right) - \frac{1}{99} \\ &= 100^{i-1} a_1 + \frac{100^{i-1} - 1}{99} \\ &= \frac{100^i-1}{99} \end{align}$$

となる. $a_i$ を $10^9+7$ で割った余りは, 上式を $10^9+7$ を法とする剰余環上で計算すればいい. 累乗は繰り返し2乗法で, 割り算は法が素数なので逆元が使える.

$a_{11}$ で割ったときの余りであるが, $i \leq 10$ ならばそのまま出せばいい. $i = 11$ ならば 0 である.

それ以上のときは, 上の式を変形して,

$$a_i = 100^{i-11} a_{11} + \frac{100^{i-11}-1}{99}$$

となり, 右辺第1項は $0$ となる. 右辺第2項はよく見ればこれは $a_{i-11}$ であり, これを再帰的に適用すると余りは $a_{i\ mod \ 11}$ となる.