题目解析 考虑 数位DP\bf{数位DP}数位DP。 将数字 nnn 转化为字符串 sss 并 反转\bf{反转}反转，定义 f(i,r,one,isLim)f(i, r, one, isLim)f(i,r,one,isLim) 表示构造低位第 iii 位及其之前数位的合法方案数，其余参数含义为： * rrr 表示前面选择的数字除以 333 的余数。 * oneoneone 表示前面选择的数字是否存在 111。若 one=1one = 1one=1 表示存在 111，否则表示不存在 111。 * isLimisLimisLim 表示当前是否受到了 nnn 的约束（注意要构造的数字不能超过 nnn）。若为真，则第 iii 位填入的数字至多为 s[i]s[i]s[i]，否则可以是 999。如果在受到约束的情况下填了 s[i]s[i]s[i]，那么后续填入的数字仍会受到 nnn 的约束。例如 n=1234n=1234n=1234 那么 i=3(s[3]=4)i=3(s[3] = 4)i=3(s[3]=4) 填的是 444 的话，i=2(s[2]=3)i=2(s[2] = 3)i=2(s[2]=3) 的这一位至多填 333。 AC代码 复杂度分析 采用记忆化搜索实现数位DP。 数位DP的时间复杂度=状态的个数×单个状态的计算时间\bf{数位DP的时间复杂度} = \bf{状态的个数} \times \bf{单个状态的计算时间}数位DP的时间复杂度=状态的个数×单个状态的计算时间。 本题状态的个数为 O(N×3×2)O(N \times 3 \times 2)O(N×3×2)，令 D=10D = 10D=10，计算单个状态的时间为 O(D)O(D)O(D)，所以本题数位DP的时间复杂度为 O(6×N×D)O(6 \times N \times D)O(6×N×D)。 本题 DP数组\bf{DP数组}DP数组 可以 复用\bf{复用}复用 与查询次数无关，总的时间复杂度为 O(6ND+T)O(6ND + T)O(6ND+T)。 若 DP数组\bf{DP数组}DP数组 无法复用，则时间复杂度为 O(6NDT)O(6NDT)O(6NDT)。