链接：https://ac.nowcoder.com/acm/contest/9925/C
来源：牛客网
Given two non-negative integers XX and YY, determine the value of
(Sigma_{i = 0}^XSigma_{j = [i = 0]}^Y[i & j = 0]⌊log_2^{i + j}+1⌋)
modulo 10^9+7where & denotes bitwise AND;[A] equals 1 if A is true, otherwise 00;⌊x⌋ equals the maximum integer whose value is no more than x.
输入描述:
The first line contains one integer T (1≤T≤10^5) denoting the number of test cases.
Each of the following T lines contains two integers X,Y (0≤X,Y≤10^9) indicating a test case.
输出描述:
For each test case, print one line containing one integer, the answer to the test case.
示例1
输入
复制
3
3 3
19 26
8 17
输出
复制
14
814
278
详情见注释TAT
#include <bits/stdc++.h>
#define N 66
#define ll long long
using namespace std;
int x, y;
ll ans, dp[N][2][2][2];
int len1 = 0, len2 = 0, num1[N], num2[N];
const int mod = 1e9 + 7;
//dfs的作用主要是找状态数 状态数就是满足和这个数长度相等的（i的这部分） & （j的这部分） == 0 的数 把计算答案包含在里面（遇到对答案有贡献时就更新答案）
//思想就是
ll dfs(int len, bool flag, bool limit1, bool limit2) {//长度为len的状态数 flag表示之前是否有1 limit1，2标志之前部分是否卡Y或者Y上界
if(len == 0) return 1;
if(dp[len][flag][limit1][limit2] != -1) return dp[len][flag][limit1][limit2];
//这里不是枚举0到9了，而是枚举二进制位
ll cnt = 0;
for(int i = 0; i <= 1; i++) {
for(int j = 0; j <= 1; j++) {
if(limit1 && num1[len] < i || limit2 && num2[len] < j) continue;
if(i & j) continue;//都为1
if(i == j) {//都为0
cnt = (cnt + dfs(len - 1, flag, limit1 && i == num1[len], limit2 && j == num2[len])) % mod;
} else {//一个为1 一个为0
ll tmp = dfs(len - 1, 1, limit1 && i == num1[len], limit2 && j == num2[len]);
if(!flag) ans = (ans + 1ll * len * tmp % mod) % mod;//之前都为0，这时候遇到了第一个最高位
//设p + q = 31 = 1 + 2 + 4 + 8 + 16 则log(p + q) = 4，且一共有5位，4再加上公式中的1就等于5（即长度）了，因此这里直接用len乘即可
//只要这种状态计算过一次对答案的贡献就不用再计算了 因此可以保证记忆化的正确性
cnt = (cnt + tmp) % mod;
}
}
}
return dp[len][flag][limit1][limit2] = cnt;
}
void solve(int x, int y) {
memset(dp, -1, sizeof(dp));
ans = 0;
len1 = len2 = 0;
memset(num1, 0, sizeof(num1));
memset(num2, 0, sizeof(num2));
while(x) {
num1[++len1] = x & 1;
x >>= 1;
}
while(y) {
num2[++len2] = y & 1;
y >>= 1;
}
dfs(max(len1, len2), 0, 1, 1);
}
int main() {
int t;
cin >> t;
while(t--) {
cin >> x >> y;
solve(x, y);
cout << ans << endl;
}
return 0;
}