数位统计DP
数位统计DP是一种模板性较强的DP套路题，主要用于对数字数位上的统计。在完成一些对数位上数字有明确要求的统计操作时，对区间内数字的暴力逐个枚举会产生大量无效工作，严重超时。
[ZJOI2010] 数字计数
题目描述
给定两个正整数 aaa 和 bbb，求在 [a,b][a,b][a,b] 中的所有整数中，每个数码(digit)各出现了多少次。
输入格式
仅包含一行两个整数 a,ba,ba,b，含义如上所述。
输出格式
包含一行十个整数，分别表示 0∼90\\sim 90∼9 在 [a,b][a,b][a,b] 中出现了多少次。
样例 #1
样例输入 #1
1 99
样例输出 #1
9 20 20 20 20 20 20 20 20 20
提示
数据规模与约定
- 对于 30%30\\%30% 的数据，保证 a≤b≤106a\\le b\\le10^6a≤b≤106；
- 对于 100%100\\%100% 的数据，保证 1≤a≤b≤10121\\le a\\le b\\le 10^{12}1≤a≤b≤1012。
从取值范围就可以看出，暴力绝对不可能完成。
先考虑一个较为简单的问题，如果区间为 [0,9…9⏟i](1≤i≤11)[0,\\underbrace{9\\dots 9}_i](1\\le i\\le 11)[0,i9…9](1≤i≤11)，我们如何计算其中 333 出现的次数？
- 0∼90\\sim 90∼9 中，只有 333 出现 111 次；
- 0∼990\\sim 990∼99 中，个位出现 101010 次，分别是 3,13,23,33,43,53,63,73,83,933,13,23,33,43,53,63,73,83,933,13,23,33,43,53,63,73,83,93，十位出现也是 101010 次，为 30∼3930\\sim 3930∼39，共 202020 次；
- 0∼9990\\sim 9990∼999 中，个位出现 100100100 次，十位出现 100100100 次，百位出现 100100100 次，共 300300300 次；
- 0∼9…9⏟i0\\sim \\underbrace{9\\dots 9}_i0∼i9…9 中，枚举每一位为 333 时，其余位均可从 0∼90\\sim 90∼9 取值，共 10i−110^{i-1}10i−1 种取法，因此共出现 i⋅10i−1i\\cdot 10^{i-1}i⋅10i−1 次。
如果就是按位统计，直接通过组合数学的方法即可计算得出结果。
那么，如果最高位只是普通值应该怎么办呢？
以 0∼5120\\sim 5120∼512 中 333 的出现次数为例，可以先对百位的 0∼40\\sim 40∼4 进行枚举。
整百的数里，不算百位，333 均出现 202020 次；百位的 333 出现 100100100 次；这样就统计完了 0∼4990\\sim 4990∼499，问题变为 500∼512500\\sim 512500∼512 的子问题……
