稍微手玩一下可以发现:
- 若 \(y\ge 2x\),那么 \(y-x\gt y\%x\)
- 若 \(y\lt 2x\),那么 \(y-x=y\%x\)
- \(y\oplus x\ge y-x\)
于是不难发现只有 \(y\lt 2x\) 时才可能有贡献。
即 \(x,y\) 位数相同,最高位都为 \(1\)。
那么问题变成 \(y\oplus x=y-x\) 的对数,那么也不难发现,若某一位 \(y\) 是 \(1\),那么 \(x\) 可能是 \(0\) 或 \(1\),否则 \(y\) 是 \(0\) 的话,\(x\) 也必定是 \(0\)。
枚举最高位是哪一位,然后考虑数位 DP,但是和常规的不太一样,这个是同时给两个数填数,设 \(f_{len,f1,f2}\) 表示当前填到第 \(len\) 位,\(x\) 是否取到下界,\(y\) 是否取到上界。
转移时先枚举 \(y\) 再枚举 \(x\)。
Code:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 65, mod = 1e9 + 7;
ll L, R;
int a[N], len1, b[N], len2;
int f[N][2][2], ans;
void add(int &a, int b) {
a += b;
if (a >= mod) a -= mod;
}
int dfs(int len, bool f1, bool f2) {
if (!len) return 1;
if (~f[len][f1][f2]) return f[len][f1][f2];
int res = 0;
int Down = f1 ? a[len] : 0, Up = f2 ? b[len] : 1;
for (int y = Down; y <= Up; ++y)
for (int x = Down; x <= y; ++x)
add(res, dfs(len - 1, f1 & (x == Down), f2 & (y == Up)));
return f[len][f1][f2] = res;
}
int main() {
scanf("%lld%lld", &L, &R);
while (L) a[++len1] = L & 1, L >>= 1;
while (R) b[++len2] = R & 1, R >>= 1;
memset(f, -1, sizeof f);
for (int i = len1; i <= len2; ++i) add(ans, dfs(i - 1, i == len1, i == len2));
printf("%d", ans);
return 0;
}
标签:f1,f2,int,ABC138F,2x,len,mod
From: https://www.cnblogs.com/Kobe303/p/16909476.html