发表于 | 分类于 | 0 | 阅读次数 784

题目描述

题目传送门

简意：给定 l,r(0≤l,r≤109)l,r(0 \le l,r \le 10^9)，求：

∑a=lr∑b=lr[a+b=a⊕b]\sum_{a=l}^r \sum_{b=l}^r[a+b = a \oplus b]

思路

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

原式化为：

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

现在可以做了。转化为前缀相减，设 f(l,r)=∑a=0l∑b=0r[a & b=0]f(l,r)=\sum\limits_{a=0}^l \sum\limits_{b=0}^r[a\ \&\ b=0]，就是 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)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;
}