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

繰り返し二乗法

$a^{11} = a^{8 + 2 + 1}= a^8 a^2 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$ を$２$進数展開して前処理の結果を使って計算する。