以下是 LeetCode 3463 的 Python3 实现核心思路是利用组合数模 10 的性质直接计算最终结果避免 O(n^2) 的模拟。解题思路每次操作相当于相邻数字求和模 10反复进行后最终剩下的两个数字可以表示为原始数字的加权和权重恰好是组合数帕斯卡三角形。具体来说- 对于长度为 n 的字符串最终左数第一个结果等于 \sum{i0}^{n-2} C(n-2, i) \cdot s[i] \pmod{10}- 最终左数第二个结果等于 \sum{i0}^{n-2} C(n-2, i) \cdot s[i1] \pmod{10}因此只需判断这两个结果是否相等即可。由于 n \le 10^5需要 O(1) 计算组合数模 10。但 10 不是质数不能直接用费马小定理求逆元。解决方法是1. 预处理阶乘时提取所有因子 2 和 52. 剩余部分与 10 互质可用欧拉定理求逆元\varphi(10)4逆元为 a^3 \bmod 103. 计算组合数时再把提取的 2 和 5 补回去完整代码pythonMOD 10MX 10 ** 5# 预处理去掉因子 2 和 5 的阶乘f [0] * (MX 1) # f[i] i! 去掉所有因子 2 和 5 后模 10f[0] 1f_inv [0] * (MX 1) # f[i] 的模 10 逆元f_inv[0] 1# 前缀和记录阶乘中因子 2 和 5 的个数ps2 [0] * (MX 1)ps5 [0] * (MX 1)for i in range(1, MX 1):x icnt2 cnt5 0# 提取因子 2while x % 2 0:x // 2cnt2 1# 提取因子 5while x % 5 0:x // 5cnt5 1ps2[i] ps2[i - 1] cnt2ps5[i] ps5[i - 1] cnt5# 剩余部分与 10 互质直接累乘模 10f[i] f[i - 1] * x % MOD# 欧拉定理a^φ(10)-1 a^3 是逆元因为 φ(10)4f_inv[i] f_inv[i - 1] * pow(x, 3, MOD) % MODclass Solution:def hasSameDigits(self, s: str) - bool:a [int(c) for c in s]# 比较 s[0..n-2] 和 s[1..n-1] 两个子串的最终结果return self._solve(a[:-1]) self._solve(a[1:])def _solve(self, a):计算一个数组经过反复操作后最终剩下的唯一数字模 10n len(a)res 0for i in range(n):res self._cnk_mod10(n - 1, i) * a[i]return res % MODdef _cnk_mod10(self, n, k):计算 C(n, k) mod 10# 先算去掉 2 和 5 的部分res f[n] * f_inv[k] * f_inv[n - k]# 补回因子 2res * pow(2, ps2[n] - ps2[k] - ps2[n - k], MOD)# 补回因子 5res * pow(5, ps5[n] - ps5[k] - ps5[n - k], MOD)return res % MOD复杂度分析- 预处理O(MX) 时间O(MX) 空间MX 10^5- 单次查询O(n) 时间O(1) 额外空间关键点说明1. 为什么提取 2 和 5 因为 10 2 \times 5任何含因子 2 或 5 的数在模 10 下没有乘法逆元。提取后剩余部分与 10 互质逆元存在。2. 为什么比较两个子串 最终字符串长度为 2左字符来自原串 s[0..n-2] 的加权组合右字符来自 s[1..n-1] 的加权组合分别计算即可。3. 预处理放在类外LeetCode 评测时只会实例化一次 Solution将预处理放在全局可确保只执行一次避免重复计算。