题解：AT_abc138_f [ABC138F] Coincidence
hhhqx
·
·
题解
对于 x \le y：
- 若 2x \le y，则 y - x > y \bmod x。
- 若 2x > y，则 y - x = y \bmod x。
- 有 x \oplus y \ge y - x。
当 2x \le y 时，不可能存在 y \bmod x = x \oplus y 了。
现在只需要考虑满足 x \le y < 2x 且 y - x = y \oplus x 的 (x,y)。
很多题解说只用统计二进制位数相同的 (x,y)，为什么？
首先 x 要么和 y 位数相同，要么 x 比 y 的位数少一。
---
问题转化为统计多少对 $(x,y)$ 满足：
- $L \le x \le y \le R$ 且 $x$ 和 $y$ 的二进制位数相同。
- $y - x = x \oplus y$。
第二个限制等价于：对于每个二进制位，$y=1$ 则 $x=0/1$，$y=0$ 则 $x=0$。
然后就是一个比较明显的数位 dp 了。
为什么要写递推？世界属于记忆化搜索！！！
实现参考了 https://www.luogu.com.cn/article/xrraivbn 。
```cpp
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const LL mod = 1e9 + 7;
LL L, R;
LL f[100][2][2][2];
LL Solve(int d, int o1, int o2, int o3){
if(d == -1) return 1;
if(f[d][o1][o2][o3] != -1) return f[d][o1][o2][o3];
LL ret = 0;
int O1 = (L >> d) & 1, O2 = (R >> d) & 1;
for(int i = (o1 ? 0 : O1); i < 2; i++){
for(int j = i; j <= (o2 ? 1 : O2); j++){
if(!o3 && i != j) continue;
ret += Solve(d - 1, o1 | (i != O1), o2 | (j != O2), o3 | (j != 0));
ret %= mod;
}
}
return f[d][o1][o2][o3] = ret;
}
int main(){
ios::sync_with_stdio(0), cin.tie(0);
memset(f, -1, sizeof(f));
cin >> L >> R;
cout << Solve(60, 0, 0, 0);
return 0;
}
```