2025-10-08：统计逐位非递减的整数。用go语言，给定两个用字符串表示的整数 l 和 r，以及一个进制数 b。要求统计在闭区间 [l, r] 内，满足下列条件的整数个数：

• 把整数用 b 进制写出（不计前导零，0 的表示为单个 0），从最高位到最低位读取时，每一位的数值都不会小于前一位（即位序列从高位到低位是非递减的）。

• 数字范围和进制都可能很大，因此答案取模 1,000,000,007 输出。

注意 l 和 r 用字符串给出是为了支持超出标准整数范围的情况。

1 <= l.length <= r.length <= 100。

2 <= b <= 10。

l 和 r 仅由数字（0-9）组成。

l 表示的值小于或等于 r 表示的值。

l 和 r 不包含前导零。

输入： l = “23”, r = “28”, b = 8。

输出： 3。

解释：

从 23 到 28 的数字在 8 进制下为：27、30、31、32、33 和 34。

其中，27、33 和 34 的数字是非递减的。因此，输出为 3。

题目来自力扣3519。

大体过程描述

1. 预处理组合数

• 创建一个组合数表 comb，用于后续计算。
• 组合数 comb[n][k] 表示从 n 个元素中取 k 个的组合数。
• 由于题目中 b ≤ 10，我们只需要计算 k < 10 的组合数。
• 使用递推公式计算：comb[i][j] = comb[i-1][j-1] + comb[i-1][j]。
• 这些组合数将在后面用于计算"不受约束"的方案数。

2. 进制转换函数 trans

• 将字符串表示的大整数转换为指定进制的字符串表示。
• 如果 inc 参数为 true，会先将原数加 1 再转换。
• 使用 Go 的 big.Int 处理大数，确保能处理超长数字字符串。

3. 核心计算函数 calc

• 计算小于给定数字 s 的合法数字个数。
• 首先将 s 转换为 b 进制字符串。
• 使用数位 DP 的思想，逐位处理：
  • 从最高位开始，依次考虑每一位可以填的数字。
  • 维护变量 pre 记录上一位的数字，确保当前位不小于前一位。
  • 对于当前位，如果当前数字 hi 小于 pre，说明后续所有情况都不合法，直接退出。
  • 使用组合数计算"不受约束"的方案数：
    • comb[m+b-pre][b-1-pre] 表示从当前位开始，剩余 m 位，且第一位至少为 pre 的方案数。
    • comb[m+b-hi][b-1-hi] 用于调整计算范围。
  • 将当前位固定为实际值 hi，继续处理下一位。

4. 主函数 countNumbers

• 计算小于 r+1 的合法数字个数：calc(r, b, true)
• 计算小于 l 的合法数字个数：calc(l, b, false)
• 两者相减得到区间 [l, r] 内的合法数字个数。
• 对结果取模 1,000,000,007。

5. 示例处理过程

对于输入 l = “23”, r = “28”, b = 8：

• 将 23-28 转换为 8 进制：27, 30, 31, 32, 33, 34
• 检查各位是否非递减：
  • 27₈ → 2 ≤ 7 ✓
  • 30₈ → 3 > 0 ✗
  • 31₈ → 3 > 1 ✗
  • 32₈ → 3 > 2 ✗
  • 33₈ → 3 ≤ 3 ✓
  • 34₈ → 3 ≤ 4 ✓
• 最终找到 3 个合法数字。

复杂度分析

时间复杂度

• 预处理组合数：O(maxN × maxB) = O(343 × 10) ≈ O(3430)
• 每次 calc 调用：O(len(s))，其中 len(s) 是转换后的 b 进制字符串长度
• 总体：O(maxN + len(s))，在题目约束下非常高效

额外空间复杂度

• 组合数表：O(maxN × maxB) = O(343 × 10) ≈ O(3430)
• 临时变量：O(len(s)) 用于存储转换后的字符串
• 总体：O(maxN × maxB + len(s)) ≈ O(3500)

由于题目中数字长度最多 100，b ≤ 10，该算法能够高效处理所有测试用例。

Go完整代码如下：

package main

import (
	"fmt"
	"math/big"
	"strings"
)

const maxN = 333 // 进制转换后的最大长度
const maxB = 10

var comb [maxN + maxB][maxB]int

func init() {
	// 预处理组合数
	for i := 0; i < len(comb); i++ {
		comb[i][0] = 1
		for j := 1; j < min(i+1, maxB); j++ {
			// 注意本题组合数较小，无需取模
			comb[i][j] = comb[i-1][j-1] + comb[i-1][j]
		}
	}
}

func trans(s string, b int, inc bool) string {
	x := &big.Int{}
	fmt.Fscan(strings.NewReader(s), x)
	if inc {
		x.Add(x, big.NewInt(1))
	}
	return x.Text(b) // 转成 b 进制
}

func calc(s string, b int, inc bool) (res int) {
	s = trans(s, b, inc)
	// 计算小于 s 的合法数字个数
	// 为什么是小于？注意下面的代码，我们没有统计每个数位都填 s[i] 的情况
	pre := 0
	for i, d := range s {
		hi := int(d - '0')
		if hi < pre {
			break
		}
		m := len(s) - 1 - i
		res += comb[m+b-pre][b-1-pre] - comb[m+b-hi][b-1-hi] // 不受约束的方案数
		pre = hi                                             // 这一位填 hi，继续计算剩余数位的方案数
	}
	return
}

func countNumbers(l, r string, b int) int {
	// 小于 r+1 的合法数字个数 - 小于 l 的合法数字个数
	return (calc(r, b, true) - calc(l, b, false)) % 1_000_000_007
}

func main() {
	l := "23"
	r := "28"
	b := 8
	result := countNumbers(l, r, b)
	fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

import math

maxN = 333  # 进制转换后的最大长度
maxB = 10

# 预处理组合数
comb = [[0] * maxB for _ in range(maxN + maxB)]
for i in range(len(comb)):
    comb[i][0] = 1
    for j in range(1, min(i + 1, maxB)):
        # 注意本题组合数较小，无需取模
        comb[i][j] = comb[i-1][j-1] + comb[i-1][j]

def trans(s: str, b: int, inc: bool) -> str:
    # 将字符串转换为b进制
    x = int(s)
    if inc:
        x += 1
    # 转换为b进制字符串
    if x == 0:
        return "0"
    
    digits = []
    while x > 0:
        x, remainder = divmod(x, b)
        digits.append(str(remainder))
    
    return ''.join(reversed(digits))

def calc(s: str, b: int, inc: bool) -> int:
    s = trans(s, b, inc)
    # 计算小于 s 的合法数字个数
    res = 0
    pre = 0
    for i, char in enumerate(s):
        hi = int(char)
        if hi < pre:
            break
        m = len(s) - 1 - i
        # 不受约束的方案数
        res += comb[m + b - pre][b - 1 - pre] - comb[m + b - hi][b - 1 - hi]
        pre = hi  # 这一位填 hi，继续计算剩余数位的方案数
    return res

def countNumbers(l: str, r: str, b: int) -> int:
    # 小于 r+1 的合法数字个数 - 小于 l 的合法数字个数
    return (calc(r, b, True) - calc(l, b, False)) % 1_000_000_007

if __name__ == "__main__":
    l = "23"
    r = "28"
    b = 8
    result = countNumbers(l, r, b)
    print(result)