累乗はモノイドに対して定義できる。

繰り返し二乗法

• $a^{11} = a^{8 + 2 + 1}= a^8 a^4 a^1$ と考えて計算をする（指数の部分の２進展開をする）

  • $a$ の 2べき乗の部分は

    • $a^2 = a\cdot a$
    • $a^4 = a^2\cdot a^2$
    • $a^8 = a^4 \cdot a^4$

    と計算していく。

• モノイドに一般化できる

• $a^k$ の計算量は $O(\log k)$

  • 積が $O(1)$ で計算できるとする。

ダブリング

• $f: [N] \to [N]$ に対して前処理をすると、$k \leq K$ に対して $f^k (x)$ が高速に計算できる。ただし、$f^k$ は $f$ の $k$ 回合成とする。

  • 前処理
    • 計算量: $O(N \log K)$
    • 前処理内容: $f^{2^i}$ を繰り返し二乗法のノリで計算する
      • $i$ は $0$ から $2^i \geq K$ となる $i$ まで計算をする
  • クエリ ($f^k (x)$ の計算)
    • 計算量: $O(\log K)$
    • $k$ を$２$進数展開して前処理の結果を使って計算する。

• 競プロでの使い方

  • $f\colon [n] \to [n]$ は「Functional Graph の隣の頂点」や「木における親の頂点」としてよく出てくる
  • 頂点を $k$ 回動かした先を $f^k$ として表せることがよくある
  • LCA の計算でこの考え方を使う (‣)

• 愚直との比較

  • 前処理なしで愚直に繰り返し二乗法をやると $f^k(x)$ の計算に $O(n \log k)$ かかるが、$x$ だけでよいのであれば前処理をすることで $O(\log k)$ で計算できる。

• ダブリングのクエリはキャッシュがうまく使えず定数倍が遅い

  • 例えば、$N=2\times 10^5, K=10^{18}$ の場合、ダブリングテーブルがキャッシュに乗り切らない。
    • $N\times \lfloor\log_2 K\rfloor = 1.18\times 10^7$
    • L3キャッシュが54MB (64bit $7.1\times 10^6$ 個分)
      • 参考: CPU
    • (u32 にするとキャッシュに乗り切って速くなる説がある）
  • ダブリングのクエリはダブリングテーブルを縦にアクセスしていくため、速いキャッシュがうまく使えない。

• 前処理のコードについて（ダブリングテーブルの作成）

  dp[i][v] = dp[i - 1][dp[i - 1][v]]
  // ↓こう書くほうが見通しが良い (合成をしていることがわかりやすい)
  let f = &dp[i - 1];
  dp[i][v] = f[f[v]]
  

• メモ

  • 余談: functional graph の場合は周期性を使って解くこともできる？

典型的な累乗の問題の例

• 群
  • 置換 $\sigma$ に対して $\sigma^K$
  • $a \in (\mathbb{Z}/p\mathbb{Z})^\times$ に対して $a^K$
• モノイド
  • 変換 $f$ に対して $f^K$
  • $a \in \mathbb{Z}/N\mathbb{Z}$ に対して $a^K$
  • 正方行列 $A$ に対して、$A^K$

ある種の漸化式が出てくると、累乗の話になりがち。(参考: 漸化式)