首页 > 其他分享 >ABC138F

ABC138F

时间:2022-11-20 20:58:01浏览次数:61  
标签:f1 f2 int ABC138F 2x len mod

稍微手玩一下可以发现:

  • 若 \(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

相关文章