以下是 LeetCode 3519「统计逐位非递减的整数」的 TypeScript 实现。

解题思路

这道题的核心难点在于：
1. `l` 和 `r` 是长度可达 100 的十进制字符串（大整数），无法直接转为普通数字类型
2. 需要先将十进制字符串转换为 `b` 进制表示，再用 数位 DP 统计满足条件的数

算法流程：

步骤    说明    
1. 大整数转 `b` 进制    使用「长除法」逐位除 `b`，得到 `b` 进制下的各位数字（MSB 在前）    
2. 数位 DP    `dfs(pos, last, tight)` 表示：当前在第 `pos` 位，上一位是 `last`，是否受上界限制 (`tight`)    
3. 区间计数    答案 = `count(0, r) - count(0, l-1)`    

数位 DP 状态设计：
- `pos`：当前处理到的位数
- `last`：上一位填的数字，当前位必须 `≥ last`（保证非递减）
- `tight`：是否紧贴上界。若为 `true`，当前位最大只能填 `digits[pos]`；否则可填到 `b-1`

---

TypeScript 代码

```typescript
function countNumbers(l: string, r: string, b: number): number {
    const MOD = 1_000_000_007;

    /**
     * 将十进制字符串转为 b 进制数字数组（高位在前）
     * 使用长除法，时间复杂度 O(n²)，n 为字符串长度
     */
    function toBaseB(s: string): number[] {
        const digits: number[] = [];
        let num = s.split('').map(c => parseInt(c));

        while (num.length > 0 && !(num.length === 1 && num[0] === 0)) {
            const next: number[] = [];
            let remainder = 0;

            for (let i = 0; i < num.length; i++) {
                const cur = remainder * 10 + num[i];
                const q = Math.floor(cur / b);
                remainder = cur % b;
                if (q > 0 || next.length > 0) {
                    next.push(q);
                }
            }

            digits.push(remainder);
            num = next;
        }

        digits.reverse();
        return digits.length === 0 ? [0] : digits;
    }

    /**
     * 十进制字符串减 1
     */
    function decr(s: string): string {
        const chars = s.split('');
        let i = chars.length - 1;
        while (i >= 0 && chars[i] === '0') {
            chars[i] = '9';
            i--;
        }
        if (i >= 0) {
            chars[i] = String.fromCharCode(chars[i].charCodeAt(0) - 1);
        }
        let start = 0;
        while (start < chars.length - 1 && chars[start] === '0') {
            start++;
        }
        return chars.slice(start).join('');
    }

    /**
     * 数位 DP：统计 [0, num] 中，b 进制表示下各位非递减的整数个数
     */
    function countUpTo(num: string): number {
        const digits = toBaseB(num);
        const n = digits.length;
        const memo: Map<string, number> = new Map();

        function dfs(pos: number, last: number, tight: boolean): number {
            if (pos === n) {
                return 1; // 所有位都填完了，形成一个合法数字
            }

            const key = `${pos},${last},${tight ? 1 : 0}`;
            if (memo.has(key)) {
                return memo.get(key)!;
            }

            const limit = tight ? digits[pos] : b - 1;
            let res = 0;

            // 枚举当前位：必须 >= last 才能保持非递减
            for (let d = last; d <= limit; d++) {
                const newTight = tight && (d === limit);
                res = (res + dfs(pos + 1, d, newTight)) % MOD;
            }

            memo.set(key, res);
            return res;
        }

        return dfs(0, 0, true);
    }

    // 答案 = count(0, r) - count(0, l-1)
    const countR = countUpTo(r);
    
    if (l === "0") {
        return countR;
    }
    
    const lMinus1 = decr(l);
    const countL = countUpTo(lMinus1);

    return (countR - countL + MOD) % MOD;
}
```

---

复杂度分析

指标    复杂度    说明    
时间    O(\|r\|² + n × b²)    进制转换 O(\|r\|²) + 数位 DP O(n × b²)，n 为 `r` 的 b 进制位数（最多约 332）    
空间    O(n × b)    记忆化搜索的状态数    

关键说明：
- 进制转换用长除法是因为 `l`、`r` 最长 100 位，远超 JS `Number` 安全范围
- `last` 从 `0` 开始，天然处理了前导零的情况（如 `"001"` 等价于 `"1"`）
- 记忆化只在 `!tight` 时生效，但用 `Map` 统一存储也足够高效（状态数很少）

下载文件：[Solution_3519.ts](sandbox:///mnt/agents/output/Solution_3519.ts)