Kimi LeetCode 3463. 判断操作后字符串中的数字是否相等 II Rust实现

以下是 LeetCode 3463 的 Rust 实现，核心思路与 Python 版本一致：利用 Lucas 定理 分别计算组合数模 2 和模 5，再通过查表合并得到模 10 的结果。

完整代码

```rust
impl Solution {
pub fn has_same_digits(s: String) -> bool {
let n = s.len();
let bytes = s.as_bytes();
let mut num1 = 0i64; // 对应 s[0..n-2] 的最终结果
let mut num2 = 0i64; // 对应 s[1..n-1] 的最终结果

for i in 0..n - 1 {
let coefficient = Self::n_ck_mod10((n - 2) as i32, i as i32);
let digit1 = (bytes[i] - b'0') as i64;
let digit2 = (bytes[i + 1] - b'0') as i64;
num1 = (num1 + coefficient * digit1) % 10;
num2 = (num2 + coefficient * digit2) % 10;
}

num1 == num2
}

/// 计算 C(n, k) mod 10
fn n_ck_mod10(n: i32, k: i32) -> i64 {
let mod2 = Self::lucas_theorem(n, k, 2);
let mod5 = Self::lucas_theorem(n, k, 5);
// lookup[mod2][mod5] = C(n,k) mod 10
let lookup: [[i64; 5]; 2] = [
[0, 6, 2, 8, 4], // mod2 == 0
[5, 1, 7, 3, 9], // mod2 == 1
];
lookup[mod2 as usize][mod5 as usize]
}

/// Lucas 定理：计算 C(n, k) mod prime，prime 为质数
fn lucas_theorem(mut n: i32, mut k: i32, prime: i32) -> i64 {
let mut res = 1i64;
while n > 0 || k > 0 {
let n_mod = n % prime;
let k_mod = k % prime;
if k_mod > n_mod {
return 0;
}
res = (res * Self::small_comb(n_mod, k_mod)) % prime as i64;
n /= prime;
k /= prime;
}
res
}

/// 计算小组合数 C(n, k)，其中 n, k 很小（0 <= n, k <= 4）
fn small_comb(n: i32, k: i32) -> i64 {
if k < 0 || k > n {
return 0;
}
// 预计算 0~4 的组合数
let comb = [
[1, 0, 0, 0, 0],
[1, 1, 0, 0, 0],
[1, 2, 1, 0, 0],
[1, 3, 3, 1, 0],
[1, 4, 6, 4, 1],
];
comb[n as usize][k as usize] as i64
}
}
```

关键点说明

要点 说明
Lucas 定理 将大组合数 C(n,k) 分解为 p 进制下各位小组合数的乘积，分别计算模 2 和模 5
small_comb Lucas 定理中每位数字最多为 4（因为 prime 最大为 5），直接预计算小组合数表，避免依赖外部库
lookup 表 通过中国剩余定理合并模 2 和模 5 的结果，得到唯一的模 10 值
时间复杂度 O(n \cdot \log_p n)，其中 p \in \{2, 5\}，对于 n \le 10^5 非常高效
空间复杂度 O(1)，仅使用常数额外空间

算法原理简述

最终剩下的两个数字分别是原字符串两个子串的加权和，权重为组合数 C(n-2, i)。由于 n \le 10^5，直接模拟 O(n^2) 会超时。利用 Lucas 定理可以在 O(\log n) 时间内计算每个组合数模 10，从而将总复杂度降至 O(n \log n)，轻松通过。