• T1 - 模拟
• T2 - 排序 heap
• T3 - 初等数论：欧拉定理、费马小定理、同余的应用求逆元
  - 在质数情况下: 扩展卢卡斯定理 (那么不用推导 - 直接用卢卡斯定理的逆元)
  - 合数情况下：中国余数定理
• T4 - 二分 topK问题
  - 2022年做过的topK
  - 曼哈顿距离转化为切比雪夫距离（3102）；二分

in

// @ TsReaper
class Solution {
public:
    bool hasSameDigits(string s) {
        int n = s.size();

        // 预处理 2 和 5 的幂次
        int P2[n + 1], P5[n + 1];
        P2[0] = P5[0] = 1;
        for (int i = 1; i <= n; i++) P2[i] = P2[i - 1] * 2 % 10, P5[i] = P5[i - 1] * 5 % 10;

        // 扩展欧几里得算法
        auto exgcd = [&](this auto &&self, int a, int b, int &x, int &y) -> void {
            if (b == 0) {
                x = 1; y = 0;
                return;
            }
            self(b, a % b, y, x);
            y -= a / b * x;
        };

        // 求 s[l] 到 s[r] 合并起来的结果
        auto calc = [&](int l, int r) {
            int n = r - l;
            // c：抛掉因数 2 和 5 后，组合数 mod 10 的结果
            // two：组合数里因数 2 有几个
            // five：组合数里因数 5 有几个
            int c = 1, two = 0, five = 0, sm = 0;
            for (int i = l, j = 0; ; i++, j++) {
                // 按公式求和
                sm = (sm + (s[i] - '0') * P2[two] * P5[five] * c) % 10;
                if (i == r) break;
                // 组合数递推式，先乘 (n - m)
                int t = n - j;
                while (t % 2 == 0) two++, t /= 2;
                while (t % 5 == 0) five++, t /= 5;
                c = c * t % 10;
                // 组合数递推式，再除 (m + 1)
                t = j + 1;
                while (t % 2 == 0) two--, t /= 2;
                while (t % 5 == 0) five--, t /= 5;
                // 扩展欧几里得算法求逆元
                int x, y;
                exgcd(t, 10, x, y);
                c = c * (x % 10 + 10) % 10;
            }
            return sm;
        };

        return calc(0, n - 2) == calc(1, n - 1);
    }
};

# lukas
class Solution:
    def hasSameDigits(self, s: str) -> bool:
        n = len(s)
        if n == 2:
            return s[0] == s[1]
        m = n - 2
        
        def lucas(n, k, p):
            res = 1
            while n > 0 or k > 0:
                ni = n % p
                ki = k % p
                if ki > ni:
                    return 0
                num = 1
                denom = 1
                for i in range(ki):
                    num = num * (ni - i) % p
                    denom = denom * (i + 1) % p
                denom_inv = pow(denom, p - 2, p)
                res = res * num * denom_inv % p
                n = n // p
                k = k // p
            return res
        
        def comb_mod_10(n, k):
            mod2 = lucas(n, k, 2)
            mod5 = lucas(n, k, 5)
            inv2_mod5 = 3
            k_crt = ((mod5 - mod2) * inv2_mod5) % 5
            c = (mod2 + 2 * k_crt) % 10
            return c
        
        coeff = [comb_mod_10(m, i) for i in range(m + 1)]
        
        num1 = 0
        num2 = 0
        for i in range(m + 1):
            num1 += int(s[i]) * coeff[i]
            num2 += int(s[i + 1]) * coeff[i]
        num1 %= 10
        num2 %= 10
        
        return num1 == num2