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