题意解析 考虑 数位DP\bf{数位DP}数位DP。 将数字 nnn 转化为字符串 sss 定义 f(i,cnt,isLim,isNum)f(i, cnt, isLim, isNum)f(i,cnt,isLim,isNum) 表示构造第 iii 位及其之后数位的合法方案数，其余参数含义为： * cntcntcnt 表示前面选择的非零数字的数量。 * isLimisLimisLim 表示当前是否受到了 nnn 的约束（注意要构造的数字不能超过 nnn）。若为真，则第 iii 位填入的数字至多为 s[i]s[i]s[i]，否则可以是 999。如果在受到约束的情况下填了 s[i]s[i]s[i]，那么后续填入的数字仍会受到 nnn 的约束。例如 n=1234n=1234n=1234，那么 i=0i=0i=0 填的是 111 的话，i=2i=2i=2 的这一位至多填 222。 * isNumisNumisNum 表示 iii 前面的数位是否填了数字。若为假，则当前位可以跳过（不填数字），或者要填入的数字至少为 111；若为真，则要填入的数字可以从 000 开始。例如 n=123n=123n=123，在 i=0i=0i=0 时跳过的话，相当于后面要构造的是一个 999999 以内的数字了，如果 i=1i=1i=1 不跳过，那么相当于构造一个 101010 到 999999 的两位数，如果 i=1i=1i=1 跳过，相当于构造的是一个 999 以内的数字。 AC代码 复杂度分析 对于每个 TestcaseTestcaseTestcase 时间复杂度为：O(mKD)\mathrm{O}(mKD)O(mKD)，其中 mmm 为 sss 的长度，即 O(log⁡N)\mathrm{O}(\log{N})O(logN)；D=10D=10D=10。 由于每个状态只会计算一次，因此动态规划的时间复杂度 = 状态个数 ×\times× 单个状态的计算时间。 本题状态个数为 O(mK)\mathrm{O}(mK)O(mK)，单个状态的计算时间为 O(D)\mathrm{O}(D)O(D)，因此总的时间复杂度为 O(mDK)\mathrm{O}(mDK)O(mDK)。