LC 411 T3

class Solution {
    string ans;
    vector<int> mv;
    using a10i = array<int, 10>;
    vector<a10i> c2;

    bool search(int beg, int end, int mod, int k) {
        if (beg > end) return mod == 0;
        if (c2[beg][mod] != 0) return c2[beg][mod] == 1;

        for (char i = '9'; i >= '0'; --i) {
            int d = i - '0';
            int nm = 0;
            if (beg == end) {
                nm = (mod + d * mv[beg]) % k;
            } else {
                nm = (mod + d * (mv[beg] + mv[end])) % k;
            }

            if (search(beg + 1, end - 1, nm, k)) {
                ans[beg] = ans[end] = i;
                c2[beg][mod] = 1;
                return true;
            }
        }
        c2[beg][mod] = 2;
        return false;
    }

public:
    string largestPalindrome(int n, int k) {
        mv = vector<int>(n);
        mv[0] = 1;
        for (int i = 1; i < n; ++i)
            mv[i] = mv[i - 1] * 10 % k;
        c2 = vector<a10i>((n + 1) / 2);
        ans = string(n, '9');
        search(0, n - 1, 0, k);
        return ans;
    }
};