Finally learnt Lucas's Theorem and CRT (solution with resource links for references)
IntuitionThe question is related to Pascial triangle:say the digits are: a + b + c + d + e + f
We are comparing the modulus 10 of pairwise-reduction-sum (the op
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
The question is related to Pascial triangle:

say the digits are: a + b + c + d + e + f
We are comparing the modulus 10 of pairwise-reduction-sum (the operation in the question) of (a + b + c + d + e) and (b + c + d + e + f).
And we can observe that the pairwise-reduction-sum is actually the sum of each digit multiplying nCr (Binomial coefficient/Pascal's triangle/combination/whatever it is called):
```
a + b + c + d + e
(a + b) + (b + c) + (c + d) + (d + e)
(a + 2b + c) + (b + 2c + d) + (c + 2d + e)
(a + 3b + 3c + d) + (b + 3c + 3d + e)
a + 4b + 6c + 4d + e

1  4  6  4  1 <-- this is the 4-th row of Pascal's triangle (n = 4 for nCr).
```


# Approach
I have tried the following ways to calculate the nCr, and then mod 10 it, but all got TLE:
- calculate it directly n! / (k!(n-k)!)
- construct the triangle from top to n-th row
- construct the row from left to right using nCr = nC(r-1) * (n-r+1)/r
probably because n can go very large making the factorial or even simple multiplication very slow.

To make it pass all tests, as the hint stated, we can use Lucas's theorem to efficiently calculate `nCr mod 5` and `nCr mod 2`, and then use Chinese Remainder Theorem (CRT) to get `nCr mod 10`.

# Code
```python3 []
from math import comb

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    '''
    https://stackoverflow.com/questions/4798654/modular-multiplicative-inverse-function-in-python
    '''
    g, x, y = egcd(a, m)
    return x % m

def numberToBase(n, b):
    if n == 0:
        return [0]
    digits = []
    while n:
        digits.append(int(n % b))
        n //= b
    return digits

def CRT(a, m):
    '''
    https://cp-algorithms.com/algebra/chinese-remainder-theorem.html#implementation
    '''
    M = 1
    for m_i in m:
        M *= m_i

    ans = 0
    for i in range(len(a)):
        a_i = a[i]
        m_i = M / m[i]
        n_i = modinv(m_i, m[i])
        ans = (ans + a_i * m_i % M * n_i) % M
    return ans

def lucasTheorem(n, r, p):
        '''
        https://brilliant.org/wiki/lucas-theorem/
        '''
        nDigits = numberToBase(n, p)
        rDigits = numberToBase(r, p)
        ans = 1
        for i in range(len(nDigits)):
            ni = nDigits[i]
            if i < len(rDigits):
                ri = rDigits[i]
            else:
                ri = 0
            ans *= comb(ni, ri)
        return ans

class Solution:
    def hasSameDigits(self, s: str) -> bool:
        # Convert the string to a list of integers once
        digits = [int(ch) for ch in s]
        n = len(digits) - 2  # Based on your original logic

        # Initialize accumulators with the first two digits
        acc1 = digits[0]
        acc2 = digits[1]

        comb = 1  # This will hold C(n, 0), then C(n, 1), etc. in turn

        # We already accounted for r = 0 in acc1, acc2, so start from r = 1
        for r in range(1, n + 1):
            # calculate mod 10 of the binomial coefficient
            nCr_mod_5 = lucasTheorem(n, r, 5)
            nCr_mod_2 = lucasTheorem(n, r, 2)
            nCr_mod_10 = CRT([nCr_mod_5, nCr_mod_2], [5, 2])

            # Update the last-digit sums
            acc1 = (acc1 + digits[r] * nCr_mod_10) % 10
            acc2 = (acc2 + digits[r + 1] * nCr_mod_10) % 10

        return acc1 == acc2
```
['Python3']