[ZJOI2010] 数字计数
题目描述
给定两个正整数 $a$ 和 $b$，求在 $[a,b]$ 中的所有整数里，每个数码 $0\sim 9$ 分别出现了多少次。
输入格式
一行两个整数 $a,b$。
输出格式
一行十个整数，分别表示 $0\sim 9$ 在 $[a,b]$ 中出现了多少次。
样例输入
1 99
样例输出
9 20 20 20 20 20 20 20 20 20
数据范围
- 对于 $30\%$ 的数据，保证 $a \le b \le 10^6$。
- 对于 $100\%$ 的数据，保证 $1 \le a \le b \le 10^{12}$。
分析
设 $dp_i$ 表示在不考虑前导零时，满 $i$ 位范围内某一种数码出现的次数。
对前 $i$ 位进行统计时，可以分两类讨论：
- 前导零合法时，$0\sim 9$ 的数量相同，可以由 $dp_{i-1}$ 递推得到。
- 前导零不合法时，需要单独处理最高位为 $0$ 的情况。
这类题的核心是把 $[1,n]$ 的统计函数写出来，再用答案 $calc(b)-calc(a-1)$ 得到区间结果。