数位DP

Posted on Edited on

例题

求$[L,R]$中满足$y\geq x,且y\mod x=x\oplus y$的数对$(x,y)$的个数

分析

  1. 题目涉及位操作，对所有数以二进制看待。x和y的最高位应相同，这是因为$y\mod x<x$，其二进制最高位有限制。
  2. 两数最高位相同，则y不超过x的两倍。$y\mod x = y-x = y\oplus x$。
  3. $y-x$不可能退位。由$y\geq x$找到两者不同的最高位（y一定是1，x一定是0），这一位异或和为1，若低位退位，则差为0，矛盾，故低位不能退位。由低位不能退位，分类讨论$1-0, 1-1, 0-0$三种情况，发现更低位也不能退位，由归纳法可知$y-x$不可能退位。
  4. 综上，以bitset看待，$x\subseteq y$。
  5. 考虑记忆化搜索。$x,y$都受到上下界限制，且$y\geq x$，故分别dp枚举$x,y$的合法取值。另外要记录状态保证$x,y$的最高位相同。

$$
设f[pos][xDown][xUp][yUp][lead]\
表示第pos位之后，x是否压下界，x是否压上界，y是否压上界，xy是否取过最高位时的合法方案数
$$

解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
ULL dfs(int pos, bool xDown, bool xUp, bool yUp, bool lead) {
	if (pos < 0) return 1;
	ULL &res = ans[pos][xDown][xUp][yUp][lead];
	if (res != 0) return res;

	const int xLow = xDown ? L[pos] : 0;
	const int xHigh = xUp ? R[pos] : 1;
	const int yHigh = yUp ? R[pos] : 1;

	for (int i=xLow; i<=xHigh; ++i) {
		for (int j=i; j<=yHigh; ++j) {
			if (lead && i!=j) continue;
			res += dfs(pos-1, xDown&&i==xLow, xUp&&i==xHigh, yUp&&j==yHigh, lead&&i==0);
		}
	}
	return (res %= MOD);
}