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

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

完整代码

```cpp
class Solution {
public:
bool hasSameDigits(string s) {
int n = s.size();
long long num1 = 0; // 对应 s[0..n-2] 的最终结果
long long num2 = 0; // 对应 s[1..n-1] 的最终结果

for (int i = 0; i < n - 1; ++i) {
int coefficient = nCkMod10(n - 2, i);
int digit1 = s[i] - '0';
int digit2 = s[i + 1] - '0';
num1 = (num1 + coefficient * digit1) % 10;
num2 = (num2 + coefficient * digit2) % 10;
}

return num1 == num2;
}

private:
// 计算 C(n, k) mod 10
int nCkMod10(int n, int k) {
int mod2 = lucasTheorem(n, k, 2);
int mod5 = lucasTheorem(n, k, 5);
// lookup[mod2][mod5] = C(n,k) mod 10
int lookup[2][5] = {
{0, 6, 2, 8, 4}, // mod2 == 0
{5, 1, 7, 3, 9} // mod2 == 1
};
return lookup[mod2][mod5];
}

// Lucas 定理：计算 C(n, k) mod prime，prime 为质数
int lucasTheorem(int n, int k, int prime) {
long long res = 1;
while (n > 0 || k > 0) {
int nMod = n % prime;
int kMod = k % prime;
if (kMod > nMod) {
return 0;
}
res = (res * smallComb(nMod, kMod)) % prime;
n /= prime;
k /= prime;
}
return (int)res;
}

// 计算小组合数 C(n, k)，其中 n, k 很小（0 <= n, k <= 4）
int smallComb(int n, int k) {
if (k < 0 || k > n) return 0;
// 预计算 0~4 的组合数
int comb[5][5] = {
{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}
};
return comb[n][k];
}
};
```

关键点说明

要点 说明
Lucas 定理 将大组合数 C(n,k) 分解为 p 进制下各位小组合数的乘积，分别计算模 2 和模 5
smallComb 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)，轻松通过。