数位 DP

数位 DP 的本质就是将数字的每位分开考虑，从而降低时间复杂度。其通常的流程如下：

• 递推预处理 DP 数组；
• 逐位考虑，求出原区间的答案。

数位 DP 的问题也分为几种类型

• 求出 \([l,r]\) 区间内，数位满足指定条件的数的个数；
• 求出数位满足指定条件的数中，按大小排名第 \(k\) 的是哪个。

对于第一种问题，先将问题转化为 \([1,r]\) 的答案减去 \([1,l-1]\) 的答案。考虑前面所有数位顶格时，第 \(i\) 位产生的贡献。我们将第 \(i\) 位不顶格，后 \(n-i\) 位产生的贡献也纳入 \(i\) 的贡献，这是 \(dp\) 数组需要预处理的。这样，后面的位只计算 \(i\) 顶格时其的贡献。

对于第二种问题，我们仍然逐位考虑。我们从小到大枚举第 \(i\) 位填的数字 \(a_i\)，统计填 \(a_i\) 时合法的方案数，按 \(a_i\) 递增的顺序累加，当累加和刚好大于等于 \(k\) 时，就说明该位应该填该数字，将 \(k\) 减去该累计和，继续枚举下一位。最后得到答案。