yukicoder No.673 カブトムシ

No.673 カブトムシ - yukicoder
とりあえずS年目の元旦のときのカブトムシの数S_nを漸化式で表してみると,
\begin{equation} S_1 = B \\ S_{n+1} = CS_n + B \end{equation}
が成り立ちます. これを解くと,
\begin{equation} S_n = nB (C = 1)\\ S_n = (B + \frac{B}{C-1})C^{n-1} - \frac{B}{C-1} (otherwise) \end{equation}
となります. これをあるB,C,nについて, MOD = 10^9 + 7 で割った余りを求めたい訳ですが, 上の漸化式(特に下の式)を計算してから余りを取るには, とても大きな数になり, 整数型におさまらないことが予想できます. なのでmod 10^9+7上の演算を考えます.
フェルマーの小定理から(C-1)^{-1} mod 10^9+7を繰り返し自乗法で求め, (a^{p-2} \equiv a^{-1} \space mod \space p (pは素数)を利用) , 上の漸化式をMODを取りながら慎重に積を取ります. 上の漸化式は元旦のカブトムシの数なので, それを求めた後でCと積をとると答えです.
#278116 No.673 カブトムシ - yukicoder