SRM546 Div1 Easy - KleofasTail
問題
「xのkleofas tail」とは、1個目の要素がxで、i(>2)個目の要素が
i-1個目の要素=yが偶数のとき) y/2
yが奇数のとき) y-1
であるような長さ無限の数列である
a <= x <= b で↑の数列に1回以上kが登場するようなxの個数を求めよ
0 <= k <= 10^18
0 <= a <= b <= 10^18
解法
kからスタートして逆操作をしていく
kが偶数のときはk*2かk+1へ、奇数のときはk*2へ遷移できる
これを繰り返すと、2進数表記でprefixがkまたはk|1になっているような数は全て作れる
あとはある数x以下で↑のようなものの個数を数えられればいい
これはkを左に1ビットずつシフトしていき、そのシフトした数(=sとする)とxの上位kビットが同じときはx-s+1個、そうでないときは2^(シフト数)個だけ存在する
実装
k=0のときはprefixがどうとかいう話は通じないからb-a+1を返す
class KleofasTail { public: ll cnt(ll k, ll x) { ll res = 0; rep(i,60) { ll s = k<<i; if (x<s) break; res += min(1ll<<i, x-s+1); } return res; } ll countGoodSequences(ll k, ll a, ll b) { if (k==0) return b-a+1; ll res = cnt(k,b) - cnt(k,a-1); if (k%2==0) res += cnt(k+1,b) - cnt(k+1,a-1); return res; } };