f(x)が与えられて f^n(x) を高速に求めたい

fの定義域・値域の広さをD、nの最大値をNとするなら前処理O(D log N)で本処理O(log N)にできる

前処理

f^{2k}(x) = f^k(f^k(x))なのでf^kが既知のの時O(D)でf^{2k}が得られる

k=1は既知なので、k=2^m < NであるようなkについてO(D log N)で得られる

本処理

nの二進展開で1のところだけ前処理結果から選び出して合成すれば良い

二進展開の長さは対数オーダー