数位 dp 是个让人头疼的问题，特别是对于前导零的处理方法
还是得多多练习，本文的例题出自以下链接：https://oi-wiki.org/dp/number/
数字计数
【问题描述】
给定两个正整数 a 和 b，求在 [a, b] 中的所有整数中，每个数码各出现了多少次
【输入格式】
仅包含一行两个整数 a, b，含义如上所述
【输出格式】
包含一行十个整数，分别表示 0 ~ 9 在 [a,b] 中出现了多少次。
【样例】
【评测用例规模与约定】
【解析及代码】
给定区间 [a, b] 求其中各个数出现的次数，可以等价于 [1, b] 中各个数出现的次数 - 区间 [1, a-1] 中各个数出现的次数
例如给定 b = 465，那么各个数出现的次数可以这样拆分来计算 (先不考虑前导零)：
- 百位 4：当百位为 0~3 时，000~399 的贡献
- 十位 6：固定百位为 4，当十位为 0~5 时，400~459 的贡献
- 个位 5：固定十位为 6，当个位为 0~5 时，460~465 的贡献
以百位 4 为例，将数值的贡献拆分为三种类型的贡献：
- 本位 ∈ [0, 4) 时，下位的贡献：百位以下的数位的贡献，即 000~399 中 4 个 00~99 的贡献
- 本位 ∈ [0, 4) 时，本位的贡献：百位不为最大值时的贡献，即 000~399 中的百位，0~3 这三个数字分别出现了 100 次
- 本位 = 4 时，本位的贡献：百位为最大值时的贡献，即 400 ~ 465 中的百位，4 出现了 65 次 (这个很关键)
所以，在对百位的贡献进行上述的拆分、计算后，可以忽略百位对十位、个位的影响
此外，在这个计算的过程中，又需要使用 0~9、00~99、000~999 …… 中各个数字出现的次数。因为先不考虑前导零 (所有数字一视同仁)，所以用一个一维列表即可完成动态规划
使用 dp[i] 表示 中数字 9 的出现次数，则 dp[3] 的贡献也分为两种类型 (dp[2] 表示 00~99 中数字 9 的出现次数)：
- 下位的贡献：由 00~99 新增加一位到 000~999，则新增加了 10 个 00~99 的贡献
- 本位的贡献：新增加的一位是 0~9，则 0~9 各出现了 100 次
可以得出以下状态转移方程：
最后就是删除前导零，比如 001 中的两个 0，029 中的一个 0。不难得出，百位贡献了 100 个前导零 (000~099)，十位贡献了 10 个前导零 (00~09)，个位贡献了 1 个前导零 (0)
a, b = input().split()
dp = [0] * len(b)
# dp[i] 表示 0 ~ 10^i-1 中 9 出现的次数
for i in range(len(dp) - 1):
dp[i + 1] = dp[i] * 10 + 10 ** i
def solve(n):
tmp = int(n) + 1
cnt = [0] * 10
if tmp > 1:
# 从高位开始枚举: i 为本位的位置
for i, digit in zip(range(len(n) - 1, -1, -1), map(int, n)):
gain = 10 ** i
# 下位的贡献: 当本位 ∈ [0, digit)
for j in range(10): cnt[j] += dp[i] * digit
# 本位的贡献: 当本位 ∈ [0, digit)
for j in range(digit): cnt[j] += gain
# 本位的贡献: 当本位 = digit
tmp -= digit * gain
cnt[digit] += tmp
# 删除前导零
cnt[0] -= gain
return cnt
print(*[j - i for i, j in zip(solve(str(int(a) - 1)), solve(b))])