[C++] Two methods: Lucas theorem vs Mod inv
ApproachThis is a surprisingly interesting problem from Leetcode. Most solutions use the Lucas theorem, however I also came accross a method not using it at all
# Approach
This is a surprisingly interesting problem from Leetcode. Most solutions use the Lucas theorem, however I also came accross a method not using it at all (credit to lee215). Since Lee's solution does not have explanation, I decided to make a post to explain the methods a bit better.

The problem: check whether $\sum_{i=0}^{n-2} {n-2 \choose i}(a_i-a_{i+1}) \equiv 0 \pmod {10}$.

First of all, we can make the observation that any two numbers $x \equiv y \pmod{n}$ if and only if $x \equiv y \pmod{n_1}$ and $x \equiv y \pmod{n_2}$, where $n = n_1n_2$ and $n_1,n_2$ are different prime numbers. This can be inferred from the Chinese Remainder Theorem, but is also kind of obvious. Therefore, the we can write a function `check` for $n_1=2$ and $n_2 = 5$. 

In other words, equivalent problem: Check whether 
$\sum_{i=0}^{n-2} {n-2 \choose i}(a_i-a_{i+1}) \equiv 0 \pmod {2}$ and
$\sum_{i=0}^{n-2} {n-2 \choose i}(a_i-a_{i+1}) \equiv 0 \pmod {5}$.

The implementation for `check` differs for the 2 methods. 

(1) If we use Lucas thm (you can google it), then we just iterate through each digit of $n-2$ and $i$, very standard.

(2) If we don't want to use Lucas thm, we need to use standard modular inverse on the factorials. We have already broken 10 into primes 2 and 5, so we can apply Fermat Little Thm now. However, we know that $a^{p-1} \equiv 1 \pmod p$ only holds if $a$ and $p$ are coprime. For large p such as 1e9+7 or 998244353 (the usual culprits), this is always true for $n\leq 1e5$. But how do we make it work for $p=2,5$? The trick is to break the number into 2 components - one part is exponent of p, the other part is the remainder: $x = y p^t$. Then, we only perform modular inverse on the remainder part, and maintain the exponent as a separate variable.

# Complexity
- Time complexity: $O(nlogn)$ with constant depending on the exact implementation.

# Code (Lucas Thm)
```cpp []
class Solution {  // lucas thm.
public:

    int comb(int n, int r){  // for small n,r
        if (r > n) { return 0; }
        int res = 1;
        for (int t = 1; t <= n; ++t) { res *= t; }
        for (int t = 1; t <= r; ++t) { res /= t; }
        for (int t = 1; t <= n - r; ++t) { res /= t; }
        return res;
    }

    bool check(vector<int>& a, int mod){
        int res = 0;
        int n = a.size();
        for (int i = 0; i != n; ++i){
            // res += c(n-1, i) * ai
            int ncr = 1;
            int x = n - 1;
            int y = i;
            while (x && y){
                ncr = ncr * comb(x % mod, y % mod) % mod;
                x /= mod;
                y /= mod;
            }
            res = (res + ncr * a[i]) % mod;
        }
        return res == 0;
    }

    bool hasSameDigits(string s) {
        int n = s.size();
        vector<int> a(n - 1);
        for (int i = 0; i != n - 1; ++i){
            a[i] = (s[i] - '0') - (s[i + 1] - '0');
            a[i] = (a[i] + 10) % 10;
        }
        return check(a, 2) && check(a, 5);
    }
};
```

# Code (Mod Inv)
```cpp []
class Solution {  // does not use lucas theorem. main difficulty is that some numbers cannot calc mod inv directly, need to decompose.
public:

    int modpow(int n, int p, int mod){
        int res = 1;
        while (p){
            if (p & 1) { res = res * n % mod; }
            n = n * n % mod;
            p >>= 1;
        }
        return res;
    }

    pair<int, int> decompose(int x, int mod){
        // decompose x into x = y * pow(mod, ct). so that we can calc mod inv of y (cannot directly calculate on x)
        int ct = 0;
        while (x % mod == 0){
            x /= mod;
            ++ct;
        }
        return {x % mod, ct};
    }

    bool check(vector<int>& a, int mod){
        int res = 0;
        int n = a.size();
        int ncr = 1;  // maintains c(n - 1, i)
        int ct = 0;  // maintains the exponent part of mod
        for (int i = 0; i != n; ++i){
            if (ct == 0){  // ct >= 0
                res = (res + a[i] * ncr) % mod;
            }
            // update ncr = ncr * (n - 1 - i) / (i + 1)
            if (i == n - 1) { continue; }  // guarantee the x fed to decompose() is pos.
            pair<int, int> p1 = decompose(n - 1 - i, mod);
            ncr = ncr * p1.first % mod;
            ct += p1.second;
            pair<int, int> p2 = decompose(i + 1, mod);
            ncr = ncr * modpow(p2.first, mod - 2, mod) % mod;
            ct -= p2.second;
        }
        return res == 0;
    }

    bool hasSameDigits(string s) {
        int n = s.size();
        vector<int> a(n - 1);
        for (int i = 0; i != n - 1; ++i){
            a[i] = (s[i] - '0') - (s[i + 1] - '0');
            a[i] = (a[i] + 10) % 10;
        }
        return check(a, 2) && check(a, 5);
    }
};```
['C++']