1到N范围不含指定数字P的计数问题相关理论主题咨询

这类问题属于**数位动态规划（数位DP）**的典型基础题型，部分资料中也会将这类特定的数位排除计数问题归类到「排列组合数位计数」分支下，本质是动态规划在数位统计场景的专项应用。

• 核心逻辑是把数字按位拆分，从最高位到最低位逐位枚举取值，通过状态标记记录当前枚举的前缀是否已经小于N的对应前缀（即是否处于「紧约束」状态），同时标记是否已经出现过禁止数位P，最终统计所有合法状态的总数。
• 针对不含特定数位的简单场景，甚至可以不用写通用数位DP，直接用排列组合公式简化计算：
  1. 先统计所有位数小于N的位数的合法数：比如N是3位数，先算1位数、2位数里不含P的数的个数，第一位不能为0和P，其余位不能为P
  2. 再统计位数和N相同，且小于等于N的合法数，逐位比对计算即可
• 该算法时间复杂度仅和N的数位长度有关，最多18位的前提下计算量不到100次，完全可以处理10^18量级的输入。

function countWithoutP(N, P):
    digits = 将N转为字符串后逐位转数字得到的列表
    n = len(digits)
    res = 0
    // 统计位数小于n的合法数
    for i in 1 to n-1:
        if P != 0:
            res += 9 * (9 ** (i-1))
        else:
            res += 8 * (9 ** (i-1))
    // 统计位数等于n的合法数
    tight = True
    valid_prefix = True
    for i in 0 to n-1:
        if not tight:
            upper = 9
        else:
            upper = digits[i]
        for d in 0 to upper:
            if d == P:
                continue
            if i == 0 and d == 0:
                continue
            if d < upper:
                res += 9 ** (n - i - 1)
        if digits[i] == P:
            valid_prefix = False
            break
        tight = tight and (digits[i] == upper)
    // 单独判断N本身是否合法
    if valid_prefix and P not in digits:
        res += 1
    return res

内容的提问来源于stack exchange，提问作者user15431285