本番では解けなかった。
2進数表現にすると分かりやすい。
奇数なら n-1, 偶数なら n/2 という列に登場するという事は、
最上位が K で始まるということ。
なぜ気が付かなかった・・・。
lli f(lli K, lli m) { if (K == 0LL) return m + 1; if (m < 0) return 0; lli ret = 0; bool even = (K % 2 == 0); for (lli i = 0; ; ++i) { lli mn = K << i; lli mx = (K << i) + (1LL << (i + even)) - 1; if (m < mn) break; ret += min(m, mx) - mn + 1; } return ret; } class KleofasTail { public: long long countGoodSequences(long long K, long long A, long long B) { lli a = f(K, A - 1); lli b = f(K, B); return b - a; } };