SRM 622 Hard

Hardを頑張ってちょいちょい解いていきたい。メモ。

k

o

r

e

h

a

k

u

u

h

a

k

u

[0, A)のフィボナッチ表現のi桁目の立っているbitの個数の偶奇がわかれば良い(いつもの)

桁を固定して考えると、直感的にフラクタル的な感じになりそう…と決めうちして考えると、フィボナッチ文字列みたいになっていることがわかる

あとは適当に計算すればOK。計算量はO(log²)かlog³か