以下是 LeetCode 3463 的 C 实现核心思路与之前一致利用 Lucas 定理 分别计算组合数模 2 和模 5再通过查表合并得到模 10。完整代码cppclass 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 10int nCkMod10(int n, int k) {int mod2 lucasTheorem(n, k, 2);int mod5 lucasTheorem(n, k, 5);// lookup[mod2][mod5] C(n,k) mod 10int 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 primeprime 为质数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 4int 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 和模 5smallComb Lucas 定理中每位数字最大为 4prime 最大为 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)轻松通过。