考点：位运算,思维,二进制分块/数位DP。

区间 [0,n] 可以按二进制拆分成若干个二进制高位不变、低位取遍所有值的区间段。如 n=18 有 [0,18]=[0,15]\cup[16,17]\cup[18,18]。设二进制位长为 5，则第一个区间高位不变是 0，低 4 位取遍 0/1，即从 (00000)_2 取到 (01111)_2；第二个区间高位不变是 1000，最低位变化，从 (10000)_2 取到 (10001)_2；第三个区间全部高位不变 10000，没有变化的低位。按照这样的拆法，得到的低位段长一定各不相同，所以最多能拆出 \log n 个区间。在实现时，可以逆序枚举 2^i，若 2^i\le n，代表 2^i 个不同的数 [0,2^i-1] 可以取遍低 i 位，由此确定了一个低位段。那么下一次枚举时就等于删掉了这些数，故新的 n'=n-2^i。可以 O(\log n) 实现枚举全部拆分段。

这样拆分后的每个区间有一个方便的性质，若区间每个数都要异或 x，则可以分成高位异或 x 与低位异或 x 讨论。设区间长为 L，考虑高位段时，可以认为有 L 个相同的数异或 x 的高位，所以将一次异或的结果乘以 L 即可；考虑低位段时，不论位运算结果如何，总和不变，即有 \sum_{i=0}^{2^k-1}i\oplus x(x\le 2^i-1)=\sum_{i=0}^{2^k-1}i。例如，低位是低两位，考虑区间 [24,27] 的数：(11000)_2,(11001)_2,(11010)_2,(11011)_2。假设要同时异或 (01110)_2，得 (10110)_2,(10111)_2,(10100)_2,(10101)_2，可以看到高三位都是 101；而低两位从 00,01,10,11 变成了 10,11,00,01，只是改变了顺序，而总和不变。所以对高低段分别都可以 O(1) 计算出结果(低位用等差数列求和求出 0+1+\cdots+2^i-1)。

故总复杂度为 O(\log n)。注意取模公式。

#include <bits/stdc++.h>
using namespace std;
#define sc(x) scanf("%lld", &x)
using ll = long long;
ll n, x, mod = 1e9 + 7, inv2 = (mod + 1) / 2;
signed main()
{
    sc(n), sc(x);
    ll ans = 0;
    for (ll i = 62, pw = 1LL << i, rem = n + 1, cnt = 0; i >= 0; --i, pw >>= 1)
    {
        if (pw <= rem)
        {
            ll lf = cnt, rf = cnt + pw - 1, num = rf - lf + 1;
            ll base = ((x ^ cnt) & (~(pw - 1)));
            ll sum = (pw % mod) * ((pw - 1 + mod) % mod) % mod * inv2 % mod;
            sum += (base % mod) * (num % mod) % mod;
            ans = (ans + sum) % mod;
            cnt += pw, rem -= pw;
        }
    }
    printf("%lld", ans);
    return 0;
}

本题也可以数位 DP，可自行尝试。