問題概要

整数 $l, r$ が与えられる。整数の組 $(x, y)$ であって、

$l \le x, y \le r$
$x$ xor $y$ = $x + y$

を満たすものの個数を求めよ。
(というテストケースが $T$ 個与えられる)

制約

$1 \le T \le 100$
$0 \le l \le r \le 10^{9}$

考えたこと

とりあえず、 $x$ xor $y$ = $x + y$ という条件は

「 $x$ と $y$ を二進法表現したときに、ともに 1 が立っている桁はない」

と同値になる。そして、 $l \le x, y$ という条件が嫌なので、次のように考える。

$f(a, b)$ := $0 \le x \le a$ , $0 \le y \le b$ , $x$ xor $y$ = $x= y$ を満たす $(x, y)$ の個数

とする。このとき、求める値は

$f(r, r) - f(l-1, r) - f(r, l-1) + f(l-1, l-1)$

と求められる。さらに、 $f(a, b)$ の値は桁 DP によって求められる。

桁 DP へ

桁 DP は、「最上位桁からやる」のと「1 の位からやる」のとやり方があるけど、今回は 1 の位からやる方が楽そう。

$(x, y)$ の 1 の位を (0, 0), (1, 0), (0, 1) の 3 パターンのうちのどれにうするかを試した上で、より上位の桁の問題に帰着させていく。

#include <bits/stdc++.h>
#include <sys/time.h>
using namespace std;

using pll = pair<long long, long long>;
map<pll, long long> dp;
long long func(long long a, long long b) {
    if (dp.count(pll(a, b))) return dp[pll(a, b)];
    if (a < 0 || b < 0) return 0;
    if (a == 0) return b+1;
    if (b == 0) return a+1;

    long long res = 0;

    // (0, 0)
    res += func(a/2, b/2);

    // (0, 1)
    if (b % 2 == 0) res += func(a/2, b/2-1);
    else res += func(a/2, b/2);

    // (1, 0)
    if (a % 2 == 0) res += func(a/2-1, b/2);
    else res += func(a/2, b/2);

    return dp[pll(a, b)] = res;
}

int main() {
    int T; cin >> T;
    while (T--) {
        int l, r;
        cin >> l >> r;
        cout << func(r, r) - func(l-1, r) - func(r, l-1) + func(l-1, l-1) << endl;
    }
}