ループ検出
- $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)$