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

解题思路

核心在于逐位独立计算贡献：每个数位上的数字都独立地从 [l, r] 中选取。

· 总数字个数：共有 n = r - l + 1 个可选数字，因此 k 位数字的总数为 n^k。
· 单个数位贡献：固定一个数位，其余 k-1 位可任意选择，共有 n^(k-1) 种组合。该数位上所有数字之和为 (l+r) * n / 2。
· 数位权值总和：所有 k 个数位的权值（1, 10, ..., 10^(k-1)）之和，即等比数列和 (10^k - 1) / 9。

最终公式为：
答案 = (数位和) × n^(k-1) × (1 + 10 + ... + 10^(k-1))

其中，数位和 = (l + r) * n / 2。

---

Rust 实现

```rust
const MOD: i64 = 1_000_000_007;

impl Solution {
pub fn sum_of_numbers(l: i32, r: i32, k: i32) -> i32 {
let l = l as i64;
let r = r as i64;
let k = k as i64;

let n = r - l + 1; // 可选数字个数
let digit_sum = (l + r) * n / 2; // 单个数位上的数字和

// term1 = digit_sum * n^(k-1) % MOD
let term1 = (digit_sum % MOD) * Self::mod_pow(n, k - 1) % MOD;

// term2 = (10^k - 1) / 9 % MOD，使用费马小定理计算 9 的逆元
let pow10 = Self::mod_pow(10, k);
let inv9 = Self::mod_pow(9, MOD - 2);
let term2 = (pow10 - 1 + MOD) % MOD * inv9 % MOD;

((term1 * term2) % MOD) as i32
}

// 快速幂：计算 a^b % MOD
fn mod_pow(mut a: i64, mut b: i64) -> i64 {
let mut result = 1;
a %= MOD;
while b > 0 {
if b & 1 == 1 {
result = (result * a) % MOD;
}
a = (a * a) % MOD;
b >>= 1;
}
result
}
}
```

复杂度分析

· 时间复杂度：O(log k)，主要来自快速幂运算（mod_pow）。
· 空间复杂度：O(1)。