[Java] Super fast pre-calculation solution
IntuitionNoticed that for somens, the value of(kn​)mod10is very sparse, meaning for thosens, there are very limited number ofks that makes(kn​)mod10=0.Then we
# Intuition

Noticed that for some $$n$$s, the value of $${n \choose k} \mod 10$$ is very sparse, meaning for those $$n$$s, there are very limited number of $$k$$s that makes $${n \choose k} \mod 10 \ne 0$$.

Then we can try to find those $$n$$s and reduce the input size using them. In the end we can just bruteforcely calculate the final result.

The key is to find those $$n$$s, and pick up about $${\log_2 n}$$ of them.

It is not so easy to have a definite way to find them (requires knowledge of the Lucas theorem), but inituitively, those $$n$$ should likely end with many $$0$$s.

# Complexity
- Time complexity:

About $$O(nlogn)$$

- Space complexity:

$$O(n)$$

# Code
```java []
/*
Runtime 65 ms
Beats 100.00% of users with Java
Memory 46.5 MB
Beats 100.00% of users with Java
*/

class Solution {
    static TreeMap<Integer, int[][]> BC_MOD_PRE = new TreeMap<>();
    static {
        int size = 5;
        BC_MOD_PRE.put(size, new int[][] {{0,1},{1,5},{4,5},{5,1}});

        size = 20;
        BC_MOD_PRE.put(size, new int[][] {{0,1},{4,5},{5,4},{10,6},{15,4},{16,5},{20,1}});

        size = 50;
        BC_MOD_PRE.put(size, new int[][] {{0,1},{2,5},{16,5},{18,5},{25,2},{32,5},{34,5},{48,5},{50,1}});

        size = 130;
        BC_MOD_PRE.put(size, new int[][] {{0,1},{2,5},{5,6},{125,6},{128,5},{130,1}});

        size = 260;
        BC_MOD_PRE.put(size, new int[][] {{0,1},{4,5},{5,2},{10,6},{125,2},{130,4},{135,2},{250,6},{255,2},{256,5},{260,1}});

        size = 640;
        BC_MOD_PRE.put(size, new int[][] {{0,1},{5,8},{10,8},{15,6},{128,5},{512,5},{625,6},{630,8},{635,8},{640,1}});

        size = 1280;
        BC_MOD_PRE.put(size, new int[][] {{0,1},{5,6},{25,6},{30,6},{256,5},{625,2},{630,2},{650,2},{655,2},{1024,5},{1250,6},{1255,6},{1275,6},{1280,1}});

        size = 3200;
        BC_MOD_PRE.put(size, new int[][] {{0,1},{25,8},{50,8},{75,6},{128,5},{1024,5},{1152,5},{2048,5},{2176,5},{3072,5},{3125,6},{3150,8},{3175,8},{3200,1}});

        size = 6400;
        BC_MOD_PRE.put(size, new int[][] {{0,1},{25,6},{125,6},{150,6},{256,5},{2048,5},{2304,5},{3125,2},{3150,2},{3250,2},{3275,2},{4096,5},{4352,5},{6144,5},{6250,6},{6275,6},{6375,6},{6400,1}});

        size = 16400;
        BC_MOD_PRE.put(size, new int[][] {{0,1},{16,5},{25,6},{125,6},{150,6},{625,6},{650,6},{750,6},{775,6},{15625,6},{15650,6},{15750,6},{15775,6},{16250,6},{16275,6},{16375,6},{16384,5},{16400,1}});

        size = 53250;
        BC_MOD_PRE.put(size, new int[][] {{0,1},{2,5},{125,6},{3125,2},{3250,2},{4096,5},{4098,5},{6250,6},{6375,6},{15625,8},{15750,8},{16384,5},{16386,5},{18750,6},{18875,6},{20480,5},{20482,5},{21875,8},{22000,8},{31250,8},{31375,8},{32768,5},{32770,5},{34375,6},{34500,6},{36864,5},{36866,5},{37500,8},{37625,8},{46875,6},{47000,6},{49152,5},{49154,5},{50000,2},{50125,2},{53125,6},{53248,5},{53250,1}});

        size = 82000;
        BC_MOD_PRE.put(size, new int[][] {{0,1},{16,5},{64,5},{80,5},{125,6},{625,6},{750,6},{3125,6},{3250,6},{3750,6},{3875,6},{16384,5},{16400,5},{16448,5},{16464,5},{65536,5},{65552,5},{65600,5},{65616,5},{78125,6},{78250,6},{78750,6},{78875,6},{81250,6},{81375,6},{81875,6},{81920,5},{81936,5},{81984,5},{82000,1}});
    }

    public boolean hasSameDigits(String s) {
        List<Integer> digits = new ArrayList<>();
        for (char c : s.toCharArray()) {
            digits.add(c - '0');
        }
        int n = digits.size() - 2;
        Integer last = BC_MOD_PRE.floorKey(n);
        while (last != null) {
            List<Integer> next = new ArrayList<>();
            for (int i = 0; i + last < digits.size(); i++) {
                int result = 0;
                for (int[] map : BC_MOD_PRE.get(last)) {
                    result += map[1] * digits.get(i + map[0]);
                }
                next.add(result % 10);
            }
            digits = next;
            n = digits.size() - 2;
            last = BC_MOD_PRE.floorKey(n);
        }
        if (digits.size() == 2) {
            return digits.get(0) == digits.get(1);
        }
        return hasSameDigits(digits);
    }

    private boolean hasSameDigits(List<Integer> digits) {
        int n = digits.size() - 2;

        long b = 1;

        int[] bc = new int[n + 1];
        bc[0] = 1;
        for (int i = 1; i <= n / 2; i++) {
            b = b * (n - i + 1) / i;
            bc[i] = (int) (b % 10);
        }

        int r1 = 0;
        for (int i = 0; i < digits.size() - 1; i++) {
            r1 += digits.get(i) * bc[Math.min(i, n - i)];
            r1 %= 10;
        }
        int r2 = 0;
        for (int i = 1; i < digits.size(); i++) {
            r2 += digits.get(i) * bc[Math.min(i - 1, n - i + 1)];
            r2 %= 10;
        }
        return r1 == r2;
    }
}
```
['Math', 'Java']