DeepSeek LeetCode 3855. 给定范围内 K 位数字之和 Python3实现

这道题本质上是一个组合数学问题可以直接通过数学公式高效解决无需遍历。解题思路每个数的每一位都独立地从 [l, r] 中选择因此每一位的贡献是独立的。一个 k 位数 d_{k-1}...d_1d_0 可以表示为数字和 Σ(d_i × 10^i)其中 i 从 0 到 k-1根据独立性和对称性1. 每个位置 i 的贡献该位置有 count (r - l 1) 种数字选择其他 k-1 个位置各有 count 种选择总组合数为 count^(k-1)。2. 该位置上数字的总和可选数字 l 到 r 的和为 sum_range (l r) * count / 2。3. 单个位置对所有数字的总贡献sum_range × count^(k-1) × 10^i。将所有位置 i 的贡献相加总和为答案 sum_range × count^(k-1) × (10^0 10^1 ... 10^(k-1))其中等比数列求和为 (10^k - 1) / 9。---Python3 实现pythonclass Solution:def sumOfNumbers(self, l: int, r: int, k: int) - int:MOD 10**9 7count r - l 1sum_range (l r) * count // 2# 计算 count^(k-1) mod MODt2 pow(count, k - 1, MOD) # Python 内置快速幂[reference:3]# 计算 (10^k - 1) / 9 mod MOD# 用逆元处理除法除以9 等于乘以 9^(MOD-2)[reference:4]repunit (pow(10, k, MOD) - 1) % MODinv9 pow(9, MOD - 2, MOD)t3 repunit * inv9 % MODans (sum_range % MOD) * t2 % MODans ans * t3 % MODreturn ans---复杂度分析· 时间复杂度O(log k)主要来自三次快速幂运算pow 内置· 空间复杂度O(1)---示例验证· 示例 1l1, r2, k2 → 输出 66· 示例 2l0, r1, k3 → 输出 444· 示例 3l5, r5, k10 → 输出 555555520