题目描述

定义圆形数字如下：

把一个十进制数转换为一个无符号二进制数，若该二进制数中 0 的个数大于或等于 1 的个数，则它就是一个圆形数字。

现在给定两个正整数 $a$ 和 $b$，请问在区间 $[a, b]$ 内有多少个圆形数字。

输入格式

输入占一行，包含两个整数 $a$ 和 $b$。

输出格式

输出一个整数，表示圆形数字的个数。

样例

2 12

6

样例解释

输入

$a = 2$, $b = 12$

需要检查的数字

区间 $[2, 12]$ 内的整数：2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12

转换为二进制并判断

• 2: 二进制 10，0 的个数 1，1 的个数 1，0≥1，是圆形数字。
• 3: 二进制 11，0 的个数 0，1 的个数 2，0<2，不是。
• 4: 二进制 100，0 的个数 2，1 的个数 1，2≥1，是。
• 5: 二进制 101，0 的个数 1，1 的个数 2，1<2，不是。
• 6: 二进制 110，0 的个数 1，1 的个数 2，1<2，不是。
• 7: 二进制 111，0 的个数 0，1 的个数 3，0<3，不是。
• 8: 二进制 1000，0 的个数 3，1 的个数 1，3≥1，是。
• 9: 二进制 1001，0 的个数 2，1 的个数 2，2≥2，是。
• 10: 二进制 1010，0 的个数 2，1 的个数 2，2≥2，是。
• 11: 二进制 1011，0 的个数 1，1 的个数 3，1<3，不是。
• 12: 二进制 1100，0 的个数 2，1 的个数 2，2≥2，是。

圆形数字有：2, 4, 8, 9, 10, 12，共 6 个。

数据范围

• $1 \le a < b \le 2\times 10^9$

算法分析

这是一个数位统计 DP问题，需要统计区间 $[a, b]$ 内满足二进制表示中 0 的个数 ≥ 1 的个数的数的个数。

由于 $b$ 最大 $2\times 10^9$，二进制位最多 31 位（因为 $2^{31} \approx 2.1\times 10^9$）。

问题转化

设 $f(n)$ 表示 $[1, n]$ 中圆形数字的个数，则答案 = $f(b) - f(a-1)$。

因此，我们需要实现函数 $f(n)$。

数位 DP

通常数位 DP 针对十进制，这里二进制类似。但注意“无符号二进制数”不包含前导零，但统计 0 的个数时，前导零不计入（因为无符号二进制表示没有前导零）。例如，数字 2 的二进制是 10，不是 0010。

所以我们需要统计的是有效二进制位中 0 和 1 的个数。

设 $dp[pos][cnt0][cnt1][limit]$ 表示当前处理到第 $pos$ 位（从高位到低位），已经填的 0 的个数为 $cnt0$，1 的个数为 $cnt1$，$limit$ 表示是否受到 $n$ 的限制（即之前填的位是否与 $n$ 的对应位相同）。

但这样状态数：$pos$ 最多 31，$cnt0$ 和 $cnt1$ 最多 31，状态数 $31 \times 32 \times 32 \times 2 \approx 64000$，可接受。

转移时，枚举当前位填 0 或 1（注意不能有前导零，所以最高位必须填 1）。如果当前位填 0，则 $cnt0+1$；填 1，则 $cnt1+1$。

最终，当所有位填完后，如果 $cnt0 \ge cnt1$，则该数合法。

注意

• 数字 0 需要特殊处理：二进制表示 0，0 的个数 1（只有一位 0），1 的个数 0，$1 \ge 0$，所以 0 是圆形数字。但题目给定 $a \ge 1$，所以可以不考虑 0。
• 最高位必须为 1，所以从最高位开始填 1。

优化

由于 $cnt0$ 和 $cnt1$ 的和等于已填位数，所以可以只记录 $cnt0$ 和 $cnt1$ 的差值 $diff = cnt0 - cnt1$，这样状态减少一维。但 $diff$ 范围 $[-31, 31]$，需要加偏移量。

设 $dp[pos][diff][limit]$，其中 $diff = cnt0 - cnt1$，偏移量 $offset = 31$（因为最多 31 位）。状态数 $31 \times 63 \times 2 \approx 3906$，更小。

转移：填 0 则 $diff+1$，填 1 则 $diff-1$。

最终，如果 $diff \ge 0$，则合法。

实现步骤

1. 将 $n$ 转换为二进制字符串（不含前导零）。
2. 记忆化搜索 $dfs(pos, diff, limit)$：
   • $pos$：当前处理到第几位（从 0 开始）。
   • $diff$：当前 0 的个数减去 1 的个数。
   • $limit$：是否受到 $n$ 的限制（即前面填的位是否与 $n$ 相同）。
3. 如果 $pos$ 达到二进制长度 $len$，则返回 $diff \ge 0$。
4. 枚举当前位填的数字 $bit$（0 或 1）：
   • 如果 $limit$ 为真，则 $bit$ 不能超过 $n$ 的第 $pos$ 位。
   • 如果 $pos=0$（即最高位），必须填 1。
5. 递归计算，累加结果。
6. 使用记忆化数组存储结果，注意 $diff$ 可能为负，需要加偏移量。

边界情况

• 数字 0 需要单独判断（如果 $n=0$，则返回 1）。但题目 $a\ge1$，所以不需要。
• 注意 $diff$ 初始值：开始填之前，没有 0 和 1，所以 $diff=0$。

样例验证

对于 $n=12$，计算 $f(12)$：

二进制：1100，长度 4。

搜索过程：

• 最高位必须填 1，$diff = -1$。
• 第二位可以填 0 或 1（受限制？$n$ 的第二位是 1，所以如果前面填的与 $n$ 相同，则不能超过 1；否则可以填任意）。 最终统计所有合法路径。

结果 $f(12) = 6$（1,2,4,8,9,10,12 中圆形数字有 2,4,8,9,10,12，共 6 个）。

$f(1) = 0$（数字 1 的二进制 1，0 个 0，1 个 1，不是圆形数字）。

所以 $[2,12]$ 的圆形数字个数 = $f(12) - f(1) = 6 - 0 = 6$。

复杂度

状态数 $O(位数 \times 差值范围)$，位数最多 31，差值范围 $[-31,31]$，共约 $31 \times 63 \times 2 \approx 3906$，每次转移 $O(1)$，总计算量很小。

总结

本题是二进制数位 DP，关键点：

1. 无前导零，最高位必须为 1。
2. 用差值 $diff$ 代替 $cnt0$ 和 $cnt1$ 减少状态。
3. 记忆化搜索实现。