异或 [异或相关]

感谢 Morning_Glory 赞助

$异或$异或

$Description$Description

给定 $L,R$L,R, 求
$\sum _{i=L}^R\sum _{j=L}^{R}i\oplus j$i=L∑R​j=L∑R​ i⊕j
$L,R\&lt;=10^9$L,R<=109 .

$Solution$Solution

假设 $L=1,R=4$L=1,R=4, 则将所有涉及到的数字转换为 二进制 如下 $\downarrow$↓,
$\left[\begin{array}{c}1\mid 001\\ 2\mid 010\\ 3\mid 011\\ 4\mid 100\end{array}\right]$ ⎣⎢⎢⎡​1 ∣ 0 0 12 ∣ 0 1 03 ∣ 0 1 14 ∣ 1 0 0​⎦⎥⎥⎤​
$按位处理:$按位处理:

以 $2^0$20位 为例,

$\left[\begin{array}{c}1\\ 0\\ 1\\ 0\end{array}\right]$ ⎣⎢⎢⎡​1010​⎦⎥⎥⎤​
每个数字都要与每个数字 异或 并且对答案造成贡献,

$设0的数量为nu{m}_0,1的数量的为nu{m}_1$设 0 的数量为 num0​,1 的数量的为 num1​

1. 当前位置为 $1$1, 对答案贡献为 $nu{m}_0$num0​ .
2. 当前位置为 $0$0, 对答案贡献为 $nu{m}_1$num1​ .

综上该位答案为 $2\ast nu{m}_1\ast nu{m}_0\ast 2^0$2∗num1​∗num0​∗20 .

$求nu{m}_1,nu{m}_0:$求num1​,num0​:

$\left[\begin{array}{c}000\\ 001\\ 010\\ 011\\ 100\\ 101\\ 110\\ 111\end{array}\right]$⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎡​0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1​⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎤​
观察以上序列, 发现若当前位置为 $2^i$2i位, 则 $\mathrm{000..111...}$000..111...循环节长度为 $2^{i+1}$2i+1.
先来求 $[0,N]$[0,N] 中 $2^i$2i 位置的答案,
则
$nu{m}_0=\lfloor \frac{N+1}{2^{i+1}}\rfloor \ast 2^i+min\left\{\right(N+1)\%2^{i+1},2^i\}nu{m}_1=N-nu{m}_0+1$num0​=⌊2i+1N+1​⌋∗2i+min{(N+1)%2i+1,2i} num1​=N−num0​+1

然后 容斥 即可求出 $[L,R]$[L,R] 的 $nu{m}_0,nu{m}_1$num0​,num1​ .

$复杂度O\left(logN\right)$复杂度O(logN).

$Code$Code

#include<bits/stdc++.h>
#define reg register

int read(){
        char c;
        int s = 0, flag = 1;
        while((c=getchar()) && !isdigit(c))
                if(c == '-'){ c = getchar(), flag = -1; break ; }
        while(isdigit(c)) s = s*10 + c-'0', c = getchar();
        return s * flag;
}

const int mod = 1e9 + 7;

int L;
int R;
int Ans;
int pw[50];

int Calc(int x, int b){ 
        return ((x+1)/pw[b+1]) * pw[b] + std::min((x+1)%pw[b+1], pw[b]); 
}

void Work(){
        L = read(), R = read();
        Ans = 0;
        for(reg int b = 0; pw[b] <= R; b ++){ 
                int num_0 = Calc(R, b) - Calc(L-1, b), num_1 = R-L+1 - num_0;
                int pluss = (2ll*num_0*num_1 % mod) * pw[b] % mod;
                Ans = (1ll*pluss + Ans) % mod;
        }
        printf("%d\n", Ans);
}

int main(){
        pw[0] = 1;
        for(reg int i = 1; pw[i] <= mod; i ++) pw[i] = pw[i-1] << 1;
        int T = read();
        while(T --) Work();
        return 0;
}