lc
lc3463
对数字字符串重复执行“相邻数字和模10替换原字符”的操作，直到只剩两个数字，判断这两个数字是否相同。
解法:预处理阶乘、逆元及因子2和5的计数，用组合数计算字符串相邻字符差值的加权和
判断其模10是否为0，以此验证字符串是否符合特定数字特征
const int MOD = 10;
const int MX = 100'000;
array<int, MX + 1> f, inv_f, p2, p5;
int qpow(int x, int n) {
int res = 1;
while (n > 0) {
if (n % 2 > 0) {
res = res * x % MOD;
}
x = x * x % MOD;
n /= 2;
}
return res;
}
auto init = []() {
f[0] = inv_f[0] = 1;
for (int i = 1; i <= MX; i++) {
int x = i;
// 计算 2 的幂次
int e2 = countr_zero((unsigned) x);
x >>= e2;
// 计算 5 的幂次
int e5 = 0;
while (x % 5 == 0) {
e5++;
x /= 5;
}
f[i] = f[i - 1] * x % MOD;
inv_f[i] = qpow(f[i], 3); // 欧拉定理求逆元
p2[i] = p2[i - 1] + e2;
p5[i] = p5[i - 1] + e5;
}
return 0;
}();
int comb(int n, int k) {
// 由于每项都 < 10，所以无需中途取模
return f[n] * inv_f[k] * inv_f[n - k] *
qpow(2, p2[n] - p2[k] - p2[n - k]) *
qpow(5, p5[n] - p5[k] - p5[n - k]) % MOD;
}
class Solution {
public:
bool hasSameDigits(string s) {
int diff = 0;
for (int i = 0; i + 1 < s.size(); i++) {
diff += comb(s.size() - 2, i) * (s[i] - s[i + 1]);
}
return diff % MOD == 0;
}
};
