|
出題しようと準備していた問題が想定TLE解法で出題されてしまって、とても悲しい気分になったので解説を書きました。。。
Xから立ってるビットの数だけ足すというのをK回くりかえすと何になるか？
X,KはT個与えられる。
X,K<10^17, T<10^5
[7ビット目以降でいくつビットが立っているか][7ビット目以降でいくつ立っていないビットが続くか][下6ビット]を状態とする。
それぞれの状態について7ビット目以降で初めて立っているビットが0になるまで足すのに何回かかるか・0になった時の下6ビットを計算する。
これは各状態についてO(1)でできる。
次にXの7ビット目以降で初めて立っているビットが0になるまで足す。
これは前計算の結果を用いればO(1)。
これを足し算がK回以下になるように繰り返す。
足し算がK回以下に収まらなくなったら今度は逆に見るビットを１つずつ下げながら足していく。
これも各ビットについてO(1)。
前の操作と違って、ビットが立っていなくても足すことに注意。
最後に、残った回数だけ愚直に足す。
計算量はO(log^3 (X + K) + T log (X + K))くらい。
