LeetCode (X) LeetMath (O) C++ solution with Lucas' Theorem for Pascal's triangle
IntuitionSince the length of s can be up to 100,000, the only feasible approach is to use Lucas' Theorem to compute the (n−2)th row of Pascal's triangle.A brute
# Intuition
Since the length of s can be up to 100,000, the only feasible approach is to use Lucas' Theorem to compute the (n−2)th row of Pascal's triangle.
A brute-force approach will inevitably result in an overflow in any programming language.
The math theory background is needed.
Lucas' Theorem: https://en.wikipedia.org/wiki/Pascal%27s_triangle

# Approach
We can easy know that the final two word can be calculate with $$\Sigma s[i]*\binom{n-2}{i}$$ and $$\Sigma s[i+1]*\binom{n-2}{i}$$.
However, the n can be 100000, and the $$\binom{n}{n/2}$$ can be 30000 digits. No any type can handle it.
Therefore, we need to use Lucas' Theorem to module the number first.
$${\displaystyle {\binom {m}{n}}\equiv \prod _{i=0}^{k}{\binom {m_{i}}{n_{i}}}{\pmod {p}}}$$
p can only be prime number, so we use 2 and 5. 

# Complexity
- Time complexity:
O(n)

- Space complexity:
O(n)

# Code
```cpp []
class Solution {
public:
    bool hasSameDigits(string s) {
        int n = s.size();
        vector<int> matrix(n-1);
        for(int i=0; i<n-1; ++i){
            // Use Lucas's theorem, Calculate C(n-2,i)
            matrix[i] = Lucas(n-2, i);
        }
        int first = 0;
        int second = 0;
        for(int i=0; i<n-1; ++i){ // i: 0 ~ n-2 and i+1: 1 ~ n-1
            first += (s[i]-'0') * matrix[i];
            second += (s[i+1]-'0') * matrix[i];
        }
        first %= 10;
        second %= 10;
        return first == second;
    }
    int Lucas(int n, int k){
        int val2 = Lucas2(n, k);
        int val5 = Lucas5(n, k);
        return val5 % 2 == val2? val5 : val5 + 5;
    }
    int Lucas2(int n, int k){
        while(k > 0){ // when k < 0, C(X,0) is always 1
            int nn = n%2;
            int kk = k%2;
            if(kk > nn) return 0; 
            n/=2;
            k/=2;
        }
        return 1; // both C(1,0) or C(0,0) is 1
    }
    int Lucas5(int n, int k){
        int res = 1;
        while(k > 0){ // when k < 0, C(X,0) is always 1
            int nn = n%5;
            int kk = k%5;
            if(kk > nn) return 0; 
            res *= combination(nn, kk);
            n/=5;
            k/=5;
        }
        return res % 5;
    }
    // Calculate C(n,k)
    int combination(int n, int k){
        int res = 1;
        for(int i=0; i<k; ++i){
            res *= n-i;
            res /= i+1;
        }
        return res;
    }
};
```
['C++']