Chinese Theorem + Lucas' Theorem
ApproachLucas' Theorem: Allows one to calculate C(n, k) mod p for primes p by breaking the numbers down into digits in base p.Chinese Theorem: Combines the resu
# Approach
<!-- Describe your approach to solving the problem. -->
Lucas' Theorem: Allows one to calculate C(n, k) mod p for primes p by breaking the numbers down into digits in base p.

Chinese Theorem: Combines the results mod 2 and 5 to obtain the coefficient mod 10.
# Complexity
- Time complexity:NLogN
# Code
```csharp []
public class Solution {
    public bool HasSameDigits(string s) {
        int n = s.Length;
    if (n == 2) return s[0] == s[1];
    int k = n - 2;

    // Предварительно вычисленные биномиальные коэффициенты для p=2 и p=5
    int[,] comb2 = new int[2, 2] { { 1, 0 }, { 1, 1 } };
    int[,] comb5 = new int[5, 5] {
        { 1, 0, 0, 0, 0 },
        { 1, 1, 0, 0, 0 },
        { 1, 2, 1, 0, 0 },
        { 1, 3, 3, 1, 0 },
        { 1, 4, 1, 4, 1 }
    };

    int sumFirst = 0, sumSecond = 0;
    for (int i = 0; i <= k; i++) {
        int mod2 = Lucas(k, i, 2, comb2);
        int mod5 = Lucas(k, i, 5, comb5);
        int mod10 = (5 * mod2 + 6 * mod5) % 10;

        sumFirst = (sumFirst + (s[i] - '0') * mod10) % 10;
        sumSecond = (sumSecond + (s[i + 1] - '0') * mod10) % 10;
    }

    return sumFirst == sumSecond;
}

private int Lucas(int n, int k, int p, int[,] comb) {
    int result = 1;
    while (n > 0 || k > 0) {
        int a = n % p;
        int b = k % p;
        if (b > a) return 0;
        result = (result * comb[a, b]) % p;
        n /= p;
        k /= p;
    }
    return result;
}
}
```
['C#']