Functional Graph

定義

すべての頂点の出次数が1の有向グラフ

各連結成分には閉路がちょうど1つ存在する
- ABC357 E - Reachability in Functional Graph の解説
頂点の数がnのとき、任意の頂点からn回進むと、閉路に入る
- ABC311 C - Find it! の解説
閉路を1点に潰すと、その閉路だった部分を根とする根付き木ができる
- SCC をすると根付き木ができる、とも言える。
- 出題例
  - ABC387 F - Count Arrays
  - ABC357 E - Reachability in Functional Graph
$\lvert V \rvert = \lvert E \rvert$
- 連結成分の数に依らない

$X$ を有限集合として、関数 $f\colon X\to X$ を考える。$G = \{(x, f(x)) \mid x\in X\}$ とすると、$(X, G)$ は functional graph である。
- $G$ は関数 $f$ のグラフと呼ばれていて、ややこしい
$f$ の $k$ 回合成を $f^k$ と表すと、$(f^k(x))_{k=0}^\infty$ は途中（または最初）からループする（閉路に入る）
- 周期の長さはたかだか $|X|$。ただし、周期の長さは $x$ に依存する。
  - $x$ に依存しない $(f^k)_{k=0}^\infty$ の周期はたかだか ${\lvert X \rvert}^{\lvert X \rvert}$
    - もう少し小さく見積もると、各連結成分のサイクル部分の長さの LCM となる。
- $X$ が有限集合であることが本質（鳩ノ巣原理）
- 応用例
  - 有限集合上のk項間漸化式は最初または途中からループをする漸化式
  - べき乗 mod N の周期性代数学を使った整数論
  - 取れる石の数の種類が有限個与えられている Nim の grundy 数の周期性不偏ゲーム

$k$ ステップ先 $f^k(x)$ を求める

$k$ が小さい($k\leq 10^{18}$ ) 場合はダブリングをする (累乗・繰り返し二乗法)
$k$ が大きい場合は周期性を使う
- functional graph の性質から数ステップ動かすとサイクルに入る。サイクルに入った後は周期性が使える。
- $|X| = n$、$x$ から行けるサイクルの周期を $l$ とする。$k \geq n$ の場合は、 $k' = n + ((k -n) \bmod l)$ として、 $f^{k'}(x)$ をダブリングで求めれば良い。$k'$ は十分小さい。
  - $k$ がとても大きい場合、$(k -n) \bmod l$ は計算しにくいので、具体的には $k' = n + (k \mathbin{\%}l) + (l - (n \mathbin{\%} l)) \mathbin{\%}l$ と計算することになる。