数位统计动态规划

计数问题

求 $a$ 和 $b$ 之间的所有数字中 $0\sim 9$ 的出现次数。

1024 1025 1026 1027 1028 1029 1030 1031 1032
0: 10
1: 10
2: 7
...

如果是暴力做法，每个测试点都需要 $10\times {10}^8$ 时间复杂度。

我们先实现一个函数 count(n, x)，它表示算出 $1n$ 中数字 $x$ 出现的次数。而类似前缀和的思想，答案就是 count(b, x) - count(a - 1, x)。

对于 $1\sim n$ 中的七位数字 $abcdefg$，分别求出 1 在每一位上出现的次数。选择 $1\le uvw1opq\le abcdefg$，其中：

考虑 1 出现在第四位的情形，分两种情况：

• uvw < abc
  • uvw = 000 ~ abc - 1
  • opq = 000 ~ 999
  • 一共 abc * 1000
• uvw = abc
  • 如果 d < 1，那么 uvw1opq = abc1opq > abcdefg，舍去这种情况
  • 如果 d = 1，那么 opq = 000 ~ efg，一共 efg + 1 种可取结果
  • 如果 d > 1，那么 opq = 000 ~ 999，一共 1000 种可取结果
  • 一共 efg + 1001
• 所有的情况加在一起就是 abc * 1000 + efg + 1001

边界情况：

• 当 1 出现在最高位时，上述第一种情况不存在
• 当我们枚举数字 0 的时候，由于不能有前导 0，因此 uvw = 001 ~ abc - 1
• 这是因为并不是要 7 位，而是说要至少 4 位

AC338. 计数问题