ループ検出
$ f(x)が与えられて $ f^n(x) を高速に求めたい
fの定義域・値域は共通の有限集合
始点xは単一
定義域のサイズがD、nの最大値をNとするなら前処理O(D)で本処理O(1)にできる
前処理
二つの配列A,Bを用意する
$ A: f^i(x) \to i
$ B: i \to f^i(x)
iをインクリメントしならがらこの配列を埋めていく
Aiが初期値でない場合、ループである
定数オーダーで判定できる
最悪Dまでにループが見つかる
本処理
i, Aiからループに入るまでのパスの長さとループの長さがわかる
loop_start = Ai
loop_length = i - Ai
定数オーダー$ f^n(x) = (n - A_i) \% (i - A_i)