3519.统计逐位递减的整数

数位DP，https://leetcode.cn/problems/count-numbers-with-non-decreasing-digits/

给你两个以字符串形式表示的整数 l 和 r，以及一个整数 b。返回在区间 [l, r] （闭区间）内，以 b 进制表示时，其每一位数字为 非递减 顺序的整数个数。

整数逐位 非递减 需要满足：当按从左到右（从最高有效位到最低有效位）读取时，每一位数字都大于或等于前一位数字。

由于答案可能非常大，请返回对 10^9 + 7 取余后的结果。

示例 1：

输入： l = "23", r = "28", b = 8

输出： 3

解释：

从 23 到 28 的数字在 8 进制下为：27、30、31、32、33 和 34。
其中，27、33 和 34 的数字是非递减的。因此，输出为 3。

示例 2：

输入： l = "2", r = "7", b = 2

输出： 2

解释：

从 2 到 7 的数字在 2 进制下为：10、11、100、101、110 和 111。
其中，11 和 111 的数字是非递减的。因此，输出为 2。

提示：

1 <= l.length <= r.length <= 100
2 <= b <= 10
l 和 r 仅由数字（0-9）组成。
l 表示的值小于或等于 r 表示的值。
l 和 r 不包含前导零。

下面给出完整的 Python 实现，思路如下：

将十进制字符串转换为 b 进制的数字列表
由于输入的上下界 l、r 都是十进制的字符串，我们先编写一个函数 to_base_digits(s, b)，将十进制字符串 s 转换成基数为 b 的数字列表（最高位在前）。
“十进制字符串减一”操作
为了计算区间 [l, r] 内满足条件的数目，我们可以先算出 [0, r] 内满足条件的数，再减去 [0, l-1] 内满足条件的数。这里需要一个函数 dec_str_minus_one(s)，对十进制字符串做 “减一” 操作（假定 s ≥ "1"）。
数位 DP
定义 dp[pos][last][tight] 表示：当前在第 pos 位（从 0 开始，最高位），前一位的数字是 last，tight 表示是否还受到上界限制（1=是，0=否），从这一状态出发能构造的满足“各位非递减”条件的合法后缀的个数。
- 如果 tight==1，那么当前位置的数字上限是 digits[pos]，否则上限是 b-1。
- 下一位的 last 要取不小于当前位的值，保证非递减。
组合起来
- 先计算 count_up_to(r)，再计算 count_up_to(l-1)，两者相减并加上 MOD 即为答案。

python

MOD = 10**9 + 7

class Solution:
    def countNumbers(self, l: str, r: str, b: int) -> int:
        # 1. 十进制字符串减一
        def dec_str_minus_one(s: str) -> str:
            # 假设 s >= "1"
            arr = list(s)
            i = len(arr) - 1
            while i >= 0:
                if arr[i] == '0':
                    arr[i] = '9'
                    i -= 1
                else:
                    arr[i] = str(int(arr[i]) - 1)
                    break
            # 去掉可能出现的最高位 '0'
            if arr[0] == '0':
                arr.pop(0)
            return ''.join(arr) if arr else '0'

        # 2. 将十进制字符串转为 b 进制数字列表（最高位在前）
        def to_base_digits(s: str, base: int) -> list[int]:
            # 用“短除法”模拟十进制字符串除 base
            digits = []
            num = list(map(int, s))
            while num and not (len(num) == 1 and num[0] == 0):
                carry = 0
                new_num = []
                for d in num:
                    carry = carry * 10 + d
                    q = carry // base
                    r = carry % base
                    if new_num or q != 0:
                        new_num.append(q)
                    carry = r
                digits.append(carry)
                num = new_num if new_num else [0]
            return digits[::-1]  # 目前是低位到高位，翻转为高位到低位

        # 3. 计算 [0, S] 范围内满足条件的个数
        from functools import lru_cache

        def count_up_to(S: str) -> int:
            # 转为 base b 数字列表
            digs = to_base_digits(S, b)
            n = len(digs)

            @lru_cache(None)
            def dp(pos: int, last: int, tight: int) -> int:
                if pos == n:
                    return 1  # 构造完毕
                res = 0
                up = digs[pos] if tight else b - 1
                # 枚举当前位置的数字 x，要求 x >= last，且 x <= up
                for x in range(last, up + 1):
                    res = (res + dp(pos + 1, x, tight and (x == up))) % MOD
                return res

            # 起始时，last = 0（因为可以从 0 开始），tight = 1
            return dp(0, 0, 1)

        # 4. 主逻辑：count(r) - count(l-1)
        l_minus_1 = dec_str_minus_one(l)
        ans = (count_up_to(r) - count_up_to(l_minus_1)) % MOD
        return ans

if __name__ == "__main__":
    sol = Solution()
    print(sol.countNumbers("23", "28", 8))  # 3
    print(sol.countNumbers("2", "7", 2))    # 2

复杂度分析

将长度为 (D) 的十进制字符串转换为 (b) 进制，最坏情况下每次除法要 $O (D)$ ，共做 $O (D \log_{b} (10^{D})) = O (D^{2})$ 步；
DP 状态数为 $O (n \times b \times 2)$ ，其中 (n) 是基 (b) 表示后的位数，最坏 $n = O (D \log_{b} 10)$ ；转移枚举最多 $b $次，因此整体 DP 复杂度为 $O (n \times b^{2})$ 。
综合来看，对于 $D \leq 100$ 、 $b \leq 10$ 的限制，完全在可接受范围内。

3519.统计逐位递减的整数 ​

3519.统计逐位递减的整数