题目理解

我们需要统计 $[L, R]$ 区间内满足以下两个条件的 $11$ 位手机号码数量：

1. 至少包含 $3$ 个相邻的相同数字（如 $111$, $222$ 等）
2. 不能同时包含数字 $8$ 和 $4$

手机号码是 $11$ 位，没有前导 $0$。

---

数据范围分析

• $L, R$ 都是 $11$ 位数，范围 $10^{10} \leq L \leq R < 10^{11}$
• 直接枚举不可行：区间大小可能达到 $10^{11} - 10^{10} = 9 \times 10^{10}$

---

数位DP方法

这是典型的数位统计问题，可以使用数位DP解决。

状态设计

我们需要记录以下信息：

• 位置 $pos$：当前处理到第几位（从高位到低位，0-based）
• 边界限制 $limit$：之前是否紧贴上界
• 前导零 $lead$：之前是否都是前导零（本题号码固定11位，可简化）
• 是否有三个连续相同数字 $triple$：0/1 表示是否已满足条件1
• 数字8和4的出现状态 $state$：
  • 0：既没有8也没有4
  • 1：有8没有4
  • 2：有4没有8
  • 3：同时有8和4（非法状态）
• 前两个数字 $prev1, prev2$：记录前两位的数字（用于判断连续三个相同）

状态转移

设 $dp[pos][limit][triple][state][prev1][prev2]$ 表示状态下的方案数。

对于当前位置，枚举数字 $d$ 从 $0$ 到 $9$：

• 如果 $limit = 1$ 且 $d$ 等于上界的当前位，则下一位仍受限制
• 更新 $triple$：如果 $prev1 = prev2 = d$，则出现三个连续相同
• 更新 $state$：
  • 如果 $d = 8$：$state | 1$
  • 如果 $d = 4$：$state | 2$
• 更新 $prev1, prev2$：$prev2 = prev1$, $prev1 = d$

---

特殊处理

前导零问题

由于手机号码是固定11位，没有前导零，所以：

• 第一位只能从 $1$ 到 $9$
• 其他位可以从 $0$ 到 $9$

非法状态剪枝

如果 $state = 3$（同时有8和4），直接返回 $0$

最终有效状态

只有当 $triple = 1$ 且 $state \neq 3$ 时，才计数为有效方案

---

算法流程

1. 将 $L-1$ 和 $R$ 转换为数字数组
2. 定义数位DP函数 $solve(num)$：计算 $[10^{10}, num]$ 中满足条件的号码数
3. 答案 = $solve(R) - solve(L-1)$
4. DP记忆化搜索：
   • 边界：$pos = 11$ 时，检查 $triple$ 和 $state$
   • 转移：枚举当前位数字，更新状态

---

样例验证

输入：

12121284000 12121285550

计算过程：

• $solve(12121285550)$：统计到该数的满足条件号码数
• $solve(12121283999)$：统计到 $L-1$ 的满足条件号码数
• 差值即为 $[L, R]$ 区间内的数量

满足条件的号码：

• $12121285000$：有 $000$，只有 $8$ 没有 $4$
• $12121285111$：有 $111$，只有 $8$ 没有 $4$
• $12121285222$：有 $222$，只有 $8$ 没有 $4$
• $12121285333$：有 $333$，只有 $8$ 没有 $4$
• $12121285550$：有 $555$，只有 $8$ 没有 $4$

输出：5 ✓

---

复杂度分析

• 状态数：$11 \times 2 \times 2 \times 4 \times 10 \times 10 = 17600$
• 每次转移：最多 $10$ 种选择
• 总复杂度：$O(17600 \times 10) \approx 1.76 \times 10^5$，非常高效

---

总结

本题的关键在于：

1. 识别出这是数位统计问题，使用数位DP
2. 设计合适的状态记录必要信息（连续数字、8/4出现情况）
3. 处理边界条件和状态转移
4. 使用记忆化搜索避免重复计算

这是一个典型的数位DP问题，考察了对状态设计和记忆化搜索的掌握程度。