f(x)が与えられて fn(x) を高速に求めたい fの定義域・値域の広さをD、nの最大値をNとするなら前処理O(D log N)で本処理O(log N)にできる 前処理 f2k(x)=fk(fk(x))なのでfkが既知のの時O(D)でf2kが得られる k=1は既知なので、k=2m<NであるようなkについてO(D log N)で得られる 本処理 nの二進展開で1のところだけ前処理結果から選び出して合成すれば良い 二進展開の長さは対数オーダー