SRM 546 div1 easy: KleofasTail

問題

TopCoder Statistics - Problem Statement

数 X から始まる数列を以下のように定義する。

• X が偶数なら, 次の要素は X/2
• X が奇数なら, 次の要素は X-1
• これを無限に繰り返す

最初の要素が [A, B] のもののうち, 数 K が少なくとも一つ含まれるようなものはいくつかるか。

解法

K=0 のときは答えは B-A+1 です。
calc(K, A) = ([0, A) のうち, 数 K が少なくとも一つ含まれているような数列の数) というのが求まれば, calc(K, B+1) - calc(K, A) で答えが求められます。

この問題は, X を決めて X が K を要素に持つかを考えるのではなく, K からスタートして

• K -> K+1(K が偶数の時)
• K -> 2*K (いつでも)

と遷移していき, これが A 以上になるまでにどれだけの要素をたどれるか, みたいに考えると考えやすいです。

これを素直に dfs するのは間に合いません。なのですこし工夫する必要がありますが, 上記のような遷移をするときの性質を観察すると, できる数は

(K の bit)(任意の bit がくっつく) というような構成になっています。例えば K = 3 の時は, K の bit は 11 ですが, そこに
1100, 1101, 1110, 1111 のように下に好きな bit をくっつけることができます。これを利用しましょう。

これを利用すると, K*2^i では, 候補数は min(2^i, A-K*2^i) となっています。これの合計が答えです。

ただし, K が偶数の時は例外で, K+1 の場合も考えないといけません。K の bit が 10 だと, 1000, 1001, 1010, 1011 のような bit がありえますが, 最初に 1 を足すと 11** 系もできるからですね。

ll calc(ll K, ll A) {
	ll x = 1;
	ll ret = 0;
	for (; x*K < A; x *= 2) {
		ret += min(x, A-x*K);
	}
	if (K%2==0) ret += calc(K+1, A);
	return ret;
}

class KleofasTail {
public:
	long long countGoodSequences(long long K, long long A, long long B) {
		if (K==0) return B-A+1;
		return calc(K, B+1) - calc(K, A);
	}
};