满足区间减法,于是我们只需要分别计算 [0,a−1]以及 [0,b]的结果,相减既是答案。我们考虑从一个数 x的低位往高位开始枚举,对于第 k位我们分情况进行讨论。
假设 x=12345,k指向数字 3的位置,则此时pre=12,after=45,tmp=100
我们枚举 i从 0−9:
当前数字小于 i,即 i∈[4,9],此时高位的变化范围可以是 [0,11],共 pre×tmp种方案
当前数字大于 i,即 i∈[0,2],此时高位的变化范围可以是 [0,12],共 (pre+1)×tmp种方案
当前数字等于 i,即 i=3,此时高位的变化范围可以是 [0,12],当且仅当高位等于 12时低位最多取到45,因此共有 pre×tmp+after+1种方案
特殊的当 i=0时且高位为 0时,显然这种情况是不允许的,因此我们需要减去一个 tmp 。
ps:
数位dp的做法