Extending the common idea of computing binomial coefficient mod prime
IntuitionWe see a lot of problems in contests requiring us to compute binomial coefficients mod a large prime (for example109+7). This is possible because we kn
# Intuition
We see a lot of problems in contests requiring us to compute binomial coefficients mod a large prime (for example $10^9+7$). This is possible because we know factorials with relatively small factors will always be coprime with this large prime. In this problem, we must find a workaround for mod 10 because the factorials are probably not coprime with it.

# Approach
We can derive the coefficient mod 10 if we find it mod 2 and mod 5. However, the factorials may contain factors of 2 and 5. Therefore, we should find the factorials rid of factors of 2 and 5 to allow safe computation of multiplicative inverse, while keeping track of whether the coefficient is a multiple of 2 or 5.

# Complexity
- Time complexity: $O(N)$

- Space complexity: $O(N)$

# Code
```cpp []
static constexpr int lookup[2][5] = {
    {0, 6, 2, 8, 4},
    {5, 1, 7, 3, 9}
}, minv2[2] = {-1, 1}, minv5[5] = {-1, 1, 3, 2, 4};
class Solution {
public:
    bool hasSameDigits(string s) {
        int n = s.size(), a = 0, b = 0;
        vector<int> facno2(n), facno5(n), freq2(n, 0), freq5(n, 0);
        facno2[0] = facno5[0] = 1;
        for(int i = 1; i < n; ++i) {
            int p = i, q = i;
            while(p % 2 == 0) {
                p /= 2;
                ++freq2[i];
            }
            while(q % 5 == 0) {
                q /= 5;
                ++freq5[i];
            }
            facno2[i] = (facno2[i - 1] * p) % 2;
            facno5[i] = (facno5[i - 1] * q) % 5;
            freq2[i] += freq2[i - 1];
            freq5[i] += freq5[i - 1];
        }
        auto binom2 = [&](int n, int k) {
            if(freq2[n] - freq2[n - k] - freq2[k] > 0) return 0;
            return (facno2[n] * minv2[facno2[n - k]] * minv2[facno2[k]]) % 2;
        };
        auto binom5 = [&](int n, int k) {
            if(freq5[n] - freq5[n - k] - freq5[k] > 0) return 0;
            return (facno5[n] * minv5[facno5[n - k]] * minv5[facno5[k]]) % 5;
        };
        auto binom10 = [&](int n, int k) {
            return lookup[binom2(n, k)][binom5(n, k)];
        };
        for(int i = 0; i <= (n - 2) / 2; ++i) {
            a += binom10(n - 2, i) * (s[i] - '0');
            b += binom10(n - 2, i) * (s[i + 1] - '0');
        }
        for(int i = n - 2; i > (n - 2) / 2; --i) {
            a += binom10(n - 2, n - 2 - i) * (s[i] - '0');
            b += binom10(n - 2, n - 2 - i) * (s[i + 1] - '0');
        }
        return a % 10 == b % 10;
    }
};
```
['C++']