题目描述

题目传送门

简意:给定 l,r(0l,r109)l,r(0 \le l,r \le 10^9),求:

a=lrb=lr[a+b=ab]\sum_{a=l}^r \sum_{b=l}^r[a+b = a \oplus b]

思路

直接做没法做,考虑一下这个式子的意义,也就是什么时候 a+b=aba+b = a \oplus b 会成立。异或运算表示二进制下不进位加法,他们相等时就说明两个数二进制相加无进位,也就是 a+b=aba & b=0a+b = a \oplus b \Leftrightarrow a\ \&\ b=0

原式化为:

a=lrb=lr[a & b=0]\sum_{a=l}^r \sum_{b=l}^r[a\ \&\ b=0]

现在可以做了。转化为前缀相减,设 f(l,r)=a=0lb=0r[a & b=0]f(l,r)=\sum\limits_{a=0}^l \sum\limits_{b=0}^r[a\ \&\ b=0],就是 f(r,r)f(l1,r)f(l,r1)+f(r,r)=f(r,r)2f(l1,r)+f(l1,l1)f(r,r)-f(l - 1, r) - f(l, r - 1) + f(r, r)=f(r,r) - 2f(l - 1, r) + f(l - 1, l - 1)。然后对于每一个,考虑按位枚举,设 dpi,l1,l2dp_{i,l_1,l_2} 表示从高往低第 ii 位,前面对于两个数对于已填的位是否已经是最大(即对于后面做到的上界为 00 的位,我们能不能自己添上 11),然后分三种情况对于这一位填就可以了:(0,0)(0,1)(1,0)(0,0)(0,1)(1,0)

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll T, L, R, Dp[31][2][2];
ll Bit1[31], Bit2[31];

ll DFS(ll pos, bool limit1, bool limit2) {
    if (!pos) return 1ll;
    if (~Dp[pos][limit1][limit2]) return Dp[pos][limit1][limit2];

    ll tmp = DFS(pos - 1, limit1 && (Bit1[pos] == 0), limit2 && (Bit2[pos] == 0));
    if ((!limit1) || Bit1[pos]) tmp += DFS(pos - 1, limit1, limit2 && (Bit2[pos] == 0));
    if ((!limit2) || Bit2[pos]) tmp += DFS(pos - 1, limit1 && (Bit1[pos] == 0), limit2);
    Dp[pos][limit1][limit2] = tmp;
    return tmp;
}

ll Solve(ll x1, ll x2) {
    if (x1 < 0 || x2 < 0) return 0;
    memset(Dp, -1, sizeof Dp);
    memset(Bit1, 0, sizeof Bit1);
    memset(Bit2, 0, sizeof Bit2);
    ll Len1 = 0, Len2 = 0;
    while (x1) {
        Bit1[++Len1] = x1 & 1;
        x1 >>= 1;
    }
    while (x2) {
        Bit2[++Len2] = x2 & 1;
        x2 >>= 1;
    }
    return DFS(max(Len1, Len2), true, true);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> T;
    while (T--) {
        cin >> L >> R;
        ll Ans1 = Solve(R, R), Ans2 = Solve(L - 1, R), Ans3 = Solve(L - 1, L - 1);
        cout << Ans1 - 2ll * Ans2 + Ans3 << endl;
    }
    return 0;
}