数位DP

[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$ 位进行统计时，可以分两类讨论：

1. 前导零合法时，$0\sim 9$ 的数量相同，可以由 $dp_{i-1}$ 递推得到。
2. 前导零不合法时，需要单独处理最高位为 $0$ 的情况。

这类题的核心是把 $[1,n]$ 的统计函数写出来，再用答案 $calc(b)-calc(a-1)$ 得到区间结果。