2025-10-08：统计逐位非递减的整数用go语言，给定两个用字符串

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

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

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

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

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

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。

• 创建一个组合数表 comb，用于后续计算。

• 组合数 comb[n][k] 表示从 n 个元素中取 k 个的组合数。

• 由于题目中 b ≤ 10，我们只需要计算 k

• 使用递推公式计算：comb[i][j] = comb[i-1][j-1] + comb[i-1][j]。

• 这些组合数将在后面用于计算"不受约束"的方案数。

• 将字符串表示的大整数转换为指定进制的字符串表示。

• 如果 inc 参数为 true，会先将原数加 1 再转换。

• 使用 Go 的 big.Int 处理大数，确保能处理超长数字字符串。

• 计算小于给定数字 s 的合法数字个数。

• 首先将 s 转换为 b 进制字符串。

• 使用数位 DP 的思想，逐位处理：

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

• 计算小于 r+1 的合法数字个数：calc(r, b, true)

• 计算小于 l 的合法数字个数：calc(l, b, false)

• 两者相减得到区间 [l, r] 内的合法数字个数。

• 对结果取模 1,000,000,007。

对于输入 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)

• 临时变量：O(len(s)) 用于存储转换后的字符串

• 总体：O(maxN × maxB + len(s)) ≈ O(3500)

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

package mAInimport ( "fmt" "math/big" "strings")const maxN = 333// 进制转换后的最大长度const maxB = 10var comb [maxN + maxB][maxB]intfunc init { // 预处理组合数 for i := 0; i

# -*-coding:utf-8-*-import mathmaxN = 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 int: # 小于 r+1 的合法数字个数 - 小于 l 的合法数字个数 return (calc(r, b, True) - calc(l, b, False)) % 1_000_000_007if __name__ == "__main__": l = "23" r = "28" b = 8 result = countNumbers(l, r, b) print(result)