No testdata at current.

好的，我将这道题整理为清晰的题面格式，并补充样例解释、数据范围与时空限制：

---

题目描述

原题来自：ZJOI 2010

给定两个正整数 $a$ 和 $b$，求在 $[a,b]$ 中的所有整数中，每个数码（digit）各出现了多少次。

---

输入格式

仅包含一行两个整数 $a, b$，含义如上所述。

---

输出格式

包含一行 $10$ 个整数，分别表示数码 $0\sim 9$ 在 $[a,b]$ 中出现了多少次。

---

样例

样例输入

1 99

样例输出

9 20 20 20 20 20 20 20 20 20

样例解释

在 $[1,99]$ 中：

• 数码 $0$ 出现次数：$10,20,30,\dots,90$ 共 $9$ 次（$0$ 在个位出现 $9$ 次）；
• 数码 $1$ 出现次数：
  • 个位：$1,11,21,\dots,91$ 共 $10$ 次
  • 十位：$10,11,12,\dots,19$ 共 $10$ 次 合计 $20$ 次；
• 数码 $2\sim 9$ 同理，各出现 $20$ 次。

---

数据范围

• 对于 $30\%$ 的数据，$1 \le a \le b \le 10^6$；
• 对于 $100\%$ 的数据，$1 \le a \le b \le 10^{12}$。

---

时空限制

• 时间：$1000 \text{ ms}$
• 内存：$524288 \text{ KB}$

---

提示
此题为经典的 数位 DP 问题，需要分别统计 $0\sim 9$ 每个数码的出现次数。

方法： 我们可以分别对每个数码 $d$（$0\sim 9$）计算它在 $[1,n]$ 中出现的次数 $count(d,n)$，然后答案即为 $count(d,b) - count(d,a-1)$。

对于固定的 $d$，设计状态：$dp[pos][sum][lead][limit]$ 表示：

• $pos$：当前处理到的位（从高到低）；
• $sum$：当前数码 $d$ 已经出现的次数；
• $lead$：是否前面全是前导零；
• $limit$：是否受到 $n$ 的上限限制。

转移时，枚举当前位数字 $cur$ 从 $0$ 到 $9$（若有限制则到 $digit[pos]$），更新：

• 新的 $sum' = sum + (cur == d)$，但要注意如果 $lead$ 为真且 $cur=0$，则 $d=0$ 时不计入（因为前导零不算作数字 $0$）。
• 新的 $lead' = lead$ 且 $cur==0$。

最终当 $pos$ 到达末尾时，返回 $sum$。

记忆化：$dp[pos][sum][lead]$，其中 $limit$ 不记忆（但 $limit=0$ 时才记忆化）。

复杂度：每个数码 $O(\text{位数} \times \text{位数} \times 2)$，总 $O(10 \times (\log_{10} b)^3)$，可以接受。

优化：可以一次 DP 同时统计所有数码，状态为 $dp[pos][cnt_0,\dots,cnt_9]$，但状态数太大，不可行。因此分别计算每个数码是合理的。

注意：数码 $0$ 需要特殊处理前导零。

另一种思路：利用组合数学直接计算每个数码在每个数位上的贡献，可以做到 $O(\log_{10} b)$ 计算一个数码。
设当前处理第 $k$ 位（从低位到高位，权重 $10^{k-1}$），将数字分为三部分：高位 $high$、当前位 $cur$、低位 $low$。

• 如果 $cur > d$，则该位出现 $d$ 的次数为 $(high+1) \times 10^{k-1}$；
• 如果 $cur = d$，则该位出现 $d$ 的次数为 $high \times 10^{k-1} + low + 1$；
• 如果 $cur < d$，则该位出现 $d$ 的次数为 $high \times 10^{k-1}$。

对于 $d=0$ 的情况需要特殊处理，因为不能有前导零：当 $high=0$ 时，当前位不能算作 $0$ 的出现，需要减去 $10^{k-1}$。

这种方法更快，且不需要 DP。