数位dp的基本思路

数位dp

此类问题一般是求某个区间内满足某个数的个数。统计这种问题用到的数学思想是按数位分类讨论。

对于一个数 $n$ ，假设其在十进制表示下为 $a_{k - 1}a_{k - 2}...a_1a_0$，考虑数字 $val$ 在 $0$ 到 $n$ 中出现的次数：

从高位向低位遍历 $n$ ：

• 假设当前到了第 $i$ 位 （$i$ 从 $k - 1$ 到 $0$），该位的数字是 $t$

  • 若 $i$ 是最高位
    • 若 $val > t$， 由于是最高位，所以不能有贡献
    • 若 $val = t$
      • 如果只有一位，则res++
      • 否则，由于是最高位，所以不可能出现 $val = 0$ 的情况，这个时候后面的 $k - 1$ 位不能超过 $a_{k - 2}..a_1a_0$ ，所以方案数就是 get_value(num, i - 1, 0) + 1
    • 若 $val < t$
      • 若 $val = 0$
        • 如果只有一位，则 res++
        • 否则，不应该被计数
      • 若 $val \ne 0$ ，则这一位填 $val$ ，其他剩余的 $i$ 位可以随便填，所以方案数量是 get_power10(i)
  • 若 $i$ 是中间位（如果是按照顺序if-else的话，此处保证了位数不为1）
    • 若 $val > t$，则高位的枚举不能大于等于 $a_{k - 1}a_{k - 2}...a_{i + 1}$ ，低位可以随便选，所以方案数为 (get_value(num, k - 1, i + 1)) * get_power10(i)，这里的 +1是因为还要算上高位全是 0 的情况
    • 若 $val = t$
      • 若 $val = 0$，为了保证大小关系以及这一位 $0$ 确实有贡献，所以高位不能全是 $0$ ，低位还是那样，所以方案数为 (get_value(num, k - 1, i + 1) - 1) * get_power10(i) + get_value(num, i - 1, 0) + 1 （$val \ne 0$ 的时候的结果减去高位全为 $0$ 的特殊情况）
      • 若 $val \ne 0$ ，则为了保证大小关系，第 $k - 1$ 到第 $i + 1$ 位和第 $i - 1$ 到第 $0$ 位需要按照 $n$ 的大小来填，所以方案数为 get_value(num, k - 1, i + 1) * get_power10(i) + get_value(num, i - 1, 0) + 1 （相当于把第 $i$ 位抠掉之后得到的数就是方案数）。
    • 若 $val < t$
      • 若 $val = 0$ ，则为了让这一位贡献 $0$ ，前面的高位们不能都是 $0$ ，后面照样是随便填，所以方案数为 get_value(num, k - 1, i + 1) * get_power10(i)
      • 若 $val \ne 0$ ，则从第 $k - 1$ 位到第 $i + 1$ 位只要在合理的范围内随便填就好了（$0$ 也无所谓），后面的第 $i - 1$ 到第 $0$ 位没有任何限制，所以方案数为 (get_value(num, k - 1, i + 1) + 1) * get_power10(i)
  • 若 $i$ 是最低位（如果是按照顺序if-else的话，此处保证了位数不为1）
    • 若 $val > t$，则处理方式和中间位相同，为(get_value(num, k - 1, i + 1)) * get_power10(i)
    • 若 $val = t$
      • 若 $val = 0$ ，则相比较中间位来说，其没有更低位了，所以方案数是 get_value(num, k - 1, i + 1) * get_power10(i)
      • 若 $val \ne 0$，则相比较中间位来说，其没有更低位了，所以方案数是get_value(num, k - 1, i + 1) * get_power10(i)
    • 若 $val < t$
      • 若 $val = 0$ ，则和中间位一样的处理，为 get_value(num, k - 1, i + 1) * get_power10(i) + 1
      • 若 $val \ne 0$ ，则和中间位一样的处理，为 (get_value(num, k - 1, i + 1) + 1) * get_power10(i)