ループ検出

• $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)$