[AtCoder] トリボナッチ数列 - ヤマカサのプログラミング勉強日記

AtCoder Beginner Contest 006

AtCoderの問題でトリボナッチ数列に関する問題がありました。ABC006のB問題でトリボナッチ数列の値を10007で割った余りを出力せよという問題です。

トリボナッチ数列とはフィボナッチ数列の拡張であり、
${ \displaystyle a_1 = 0 }$ $a_2 = 0$ , $a_3 = 1$
$\displaystyle a_n = a_{n-1} + a_{n-2} + a_{n-3}$
を満たす数列のことです。問題ではnが与えられて、 $a_{n}$ を10007で割った余りを出力するんですが、 $a_{n}$ を求めた後に余りを求めると数値が大きくなりすぎて正しい答えを得ることができません。
したがって、次のようにする必要があります。 $\displaystyle a_n\mod 10007 = (a_{n-1} + a_{n-2} + a_{n-3} )\mod 10007$
合同式の性質から、先に $a_{n}$ を10007で割っても問題ありません。