题目传送门喵

题意分析

给定三个十六进制字符串表示的整数 $l, r, b$，长度均不超过 $50000$ 个字符。求满足 $l \le x \le r$ 且 $x \And b = b$ 的整数 $x$ 的个数，结果对 $10^9+7$ 取模。

按位与的条件等价于：$b$ 的二进制表示中为 $1$ 的位，$x$ 的对应位也必须是 $1$；其余位可以任意取 $0$ 或 $1$。因此问题转化为：在区间 $[l, r]$ 内统计有多少个数，其某些指定位必须为 $1$。

思路

由于 $l, r$ 的二进制位数可达 $4 \times 50000 = 200000$，无法直接枚举，需要使用数位 DP 在二进制位上进行计数。

采用前缀和的思想，令 $f_i$ 表示 $0$ 到 $i$ 之间满足条件的数的个数，则本题答案为 $f_r - f_{l-1}$。于是需要实现数组 $f$。那么思路也呼之欲出了，采用数位 DP 初始化 $f$ 数组，设计如下：

将 $i$ 和 $b$ 均转换为二进制串，并补零到相同长度 $L = \max(\text{len}(i), \text{len}(b))$。从高位向低位逐位决策，记录当前是否已经“小于”$i$（即是否解除上界约束）。

• 状态 $1$：之前所有位都与 $i$ 相等，当前位仍受 $i$ 限制。

• 状态 $2$：之前某位已经小于 $N$，后续位可自由取值。

设计转移：设当前位的 $b$ 值为 $x$（$0$ 或 $1$），$i$ 的当前位为 $y$。

状态 $1$：

当 $x = 1$ 时，只能取 $1$，且必须 $y = 1$，转移后仍为状态 $1$。

当 $x$ = 0 时，可取 $0$ 或 $1$：

取 $0$：若 $y = 0$ 则仍 状态 $1$，否则进入 状态 $2$。

取 $1$：必须 $y = 1$，且仍 状态 $1$。

状态 $2$：

当 $x$ = 1 时，只能取 $1$，仍为状态 $2$。

当 $x$ = 0 时，可取 $0$ 或 $1$，有 $2$ 种选择，仍为状态 $2$。

转移方程式：$f_n = (\text{状态 1} + \text{状态 2}) \bmod M$。

一些细节（边界处理）

$b = 0$ 时，条件恒成立，$f_n = n+1$，数位 DP 仍能正确计算（每位自由）。

$l = 0$ 时，直接取 $f_r$；否则需计算 $f_{l-1}$，为此实现一个十六进制减 $1$ 的函数。

代码思路

读入 $l, r, b$，转换为二进制，计算 $f_r$，若 $l \neq 0$ 则减去 $f_l-1$，输出结果（记得取模喵）。

复杂度分析

时间复杂度：

每个数位 DP 遍历 $O(\text{len})$ 位，总复杂度 $O(\text{len})$，$\text{len} \le 2\times 10^5$， 以你谷评测姬的能力来看可以接受。

空间复杂度（这个真的重要吗喵 qwq）：

存储二进制串需要 $O(\text{len})$ 空间。

写代码时请注意

代码中请使用迭代而非递归，避免栈溢出，且时间复杂度为线性。

减法取模时记得加 $\bmod$（$10^9+7$）保证结果非负喵。