C. 优雅数 详细题解

题目核心理解

称一个正整数为优雅数，当且仅当其十进制表示中非零数字的个数不超过 $3$。

给定 $T$ 个询问，每个询问给出一个区间 $[L,R]$，你需要对每个询问独立计算： 在 $L \le x \le R$ 中有多少个整数是优雅数。

数据范围：

• $1 \le T \le 10^4$
• $1 \le L_i \le R_i \le 10^{18}$

---

核心思路

1. 关键性质

• 能成为优雅数的条件非常宽松：整个数里最多只允许出现 3 个非零数字，其余都必须是 0。
• 在 $10^{18}$ 以内，所有优雅数的总数非常少，大约只有 $700\,000$ 个左右。
• 区间计数问题通用技巧：$$ans(L,R) = count(R) - count(L-1)$$ 即求 $[1,R]$ 的答案减去 $[1,L-1]$ 的答案。

2. 解法选择

本题有两种标准解法：

1. 数位 DP / 组合计数 对给定上界 $X$，直接用数位 DP 或组合公式算出 $\le X$ 的优雅数数量。 复杂度 $O(\log X)$ 每次询问。

2. 预处理全部优雅数 + 二分查询（推荐） 预处理生成所有优雅数，排序后存入数组。 对每个询问 $[L,R]$，直接用二分查找：

   • 找第一个 $\ge L$ 的位置
   • 找最后一个 $\le R$ 的位置 两者之差即为答案。

---

算法流程（预处理 + 二分版）

1. DFS 生成所有优雅数 逐位构造数字，记录已经使用的非零数字个数：

   • 非零个数 $>3$ 时剪枝
   • 长度不超过 $18$ 位（对应 $10^{18}$）

2. 排序并去重

3. 对每个询问

   1. 用 lower_bound(L) 找到第一个 $\ge L$ 的优雅数
   2. 用 upper_bound(R) 找到第一个 $> R$ 的优雅数
   3. 答案为下标之差

---

公式与复杂度分析

优雅数总数量级估算：

$$M = \binom{18}{1}\cdot9 + \binom{18}{2}\cdot9^2 + \binom{18}{3}\cdot9^3 \approx 7\times10^5 $$

复杂度

• 预处理：$O(M)$，可视为常数
• 单次询问：$O(\log M)$
• 总体：$O(T \log M)$

可轻松处理 $T\le 10^4$、$R\le 10^{18}$ 的极限数据。