以下是 LeetCode 3519「统计逐位非递减的整数」的 Python3 实现，采用数位 DP（Digit DP） + 大数进制转换解决。

核心思路

1. 大数转 b 进制：`l` 和 `r` 是长度可达 100 的十进制字符串，无法直接用 `int` 处理。通过模拟短除法将其转为 `b` 进制数字列表。
2. 前缀和思想：答案 = `count(≤r) - count(≤l-1)`，即分别统计 `[0, r]` 和 `[0, l-1]` 范围内的合法数字个数，再相减。
3. 数位 DP：设 `count_le(num_digits)` 统计 `b` 进制表示 `≤ num_digits` 的非递减整数个数。
   - 状态：`dfs(pos, prev_digit, tight)` 表示处理到第 `pos` 位，前一位数字为 `prev_digit`，是否仍紧贴 `num_digits` 的上界。
   - 转移：当前位枚举 `d`，需满足 `d >= prev_digit`（非递减）且 `d <= limit`（上界约束）。
   - 记忆化：`lru_cache` 自动处理。

```python
MOD = 10**9 + 7

class Solution:
    def countNumbers(self, l: str, r: str, b: int) -> int:
        """
        统计 [l, r] 范围内，b进制表示下逐位非递减的整数个数
        """
        
        # ========== 1. 大数转 b 进制（模拟短除法）==========
        def to_base(s: str, base: int) -> list:
            """将十进制字符串 s 转为 base 进制的数字列表（从高位到低位）"""
            digits = [int(c) for c in s]
            result = []
            while digits:
                remainder = 0
                new_digits = []
                for d in digits:
                    cur = remainder * 10 + d
                    new_digits.append(cur // base)
                    remainder = cur % base
                result.append(remainder)
                # 去掉前导零
                while new_digits and new_digits[0] == 0:
                    new_digits.pop(0)
                digits = new_digits
            # result 是从低位到高位的，需要反转
            result = result[::-1]
            return result if result else [0]
        
        # ========== 2. 大数减1 ==========
        def decrement(s: str) -> str:
            """将十进制字符串 s 减1"""
            chars = list(s)
            for i in range(len(chars) - 1, -1, -1):
                if chars[i] > '0':
                    chars[i] = chr(ord(chars[i]) - 1)
                    break
                else:
                    chars[i] = '9'
            res = ''.join(chars)
            while len(res) > 1 and res[0] == '0':
                res = res[1:]
            return res
        
        # ========== 3. 数位DP：统计 [0, num] 内合法数字个数 ==========
        from functools import lru_cache
        
        def count_le(num_digits: list) -> int:
            """统计 [0, num] 范围内，b进制表示非递减的整数个数"""
            n = len(num_digits)
            
            @lru_cache(maxsize=None)
            def dfs(pos: int, prev_digit: int, tight: bool) -> int:
                if pos == n:
                    return 1  # 所有位都填完了，找到一个合法数字
                
                limit = num_digits[pos] if tight else b - 1
                res = 0
                
                # 当前位从 prev_digit 开始枚举（保证非递减）
                for d in range(prev_digit, limit + 1):
                    new_tight = tight and (d == limit)
                    res = (res + dfs(pos + 1, d, new_tight)) % MOD
                
                return res
            
            return dfs(0, 0, True)
        
        # ========== 4. 主逻辑 ==========
        r_digits = to_base(r, b)
        
        # 如果 l 是 "0"，直接返回 [0, r] 的结果
        if l == "0":
            return count_le(r_digits) % MOD
        
        # 否则计算 [0, r] - [0, l-1]
        l_minus_1 = decrement(l)
        l_digits = to_base(l_minus_1, b)
        
        # 补零使长度相同（前面补0不影响数值大小）
        while len(l_digits) < len(r_digits):
            l_digits.insert(0, 0)
        
        ans = (count_le(r_digits) - count_le(l_digits)) % MOD
        return ans
```

复杂度分析

- 时间复杂度：O(L \times b \times b)，其中 L 为 `r` 的 `b` 进制位数（最大约 332，因为 10^{100} 转 2 进制约 332 位），b \le 10。实际状态数为 L \times b \times 2，每个状态最多枚举 b 个数字。
- 空间复杂度：O(L \times b \times 2)，用于 `lru_cache` 的记忆化存储。

关键点说明

问题    解决方案    
`l, r` 长达 100 位    用字符串模拟短除法转 `b` 进制    
`l-1` 可能为负数    `l == "0"` 时特殊处理，直接返回 `count_le(r)`    
长度不一致    在 `l_digits` 前面补零，与 `r_digits` 对齐    
非递减约束    DP 中当前位从 `prev_digit` 开始枚举    
上界约束    `tight` 参数控制是否紧贴 `num_digits` 的对应位