<p>You are given two <strong>positive</strong> integers <code>n</code> and <code>k</code>.</p>

<p>An integer <code>x</code> is called <strong>k-palindromic</strong> if:</p>

<ul>
	<li><code>x</code> is a <span data-keyword="palindrome-integer">palindrome</span>.</li>
	<li><code>x</code> is divisible by <code>k</code>.</li>
</ul>

<p>Return the<strong> largest</strong> integer having <code>n</code> digits (as a string) that is <strong>k-palindromic</strong>.</p>

<p><strong>Note</strong> that the integer must <strong>not</strong> have leading zeros.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">n = 3, k = 5</span></p>

<p><strong>Output:</strong> <span class="example-io">&quot;595&quot;</span></p>

<p><strong>Explanation:</strong></p>

<p>595 is the largest k-palindromic integer with 3 digits.</p>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">n = 1, k = 4</span></p>

<p><strong>Output:</strong> <span class="example-io">&quot;8&quot;</span></p>

<p><strong>Explanation:</strong></p>

<p>4 and 8 are the only k-palindromic integers with 1 digit.</p>
</div>

<p><strong class="example">Example 3:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">n = 5, k = 6</span></p>

<p><strong>Output:</strong> <span class="example-io">&quot;89898&quot;</span></p>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= k &lt;= 9</code></li>
</ul>

class Solution:
    def largestPalindrome(self, n: int, k: int) -> str:
        # dp[i][j]
        dp = [[-2] * k for _ in range(n // 2 + 1)]
        rems = [[0] * n for _ in range(10)]
        for i in range(10):
            rems[i][0] = i % k
            for p in range(1, n):
                rems[i][p] = (rems[i][p - 1] * 10) % k

        def solve(i, remainder):
            if i >= (n + 1) // 2:
                return -1 if remainder != 0 else 0
            
            if dp[i][remainder] != -2:
                return dp[i][remainder]

            dp[i][remainder] = -1
            pow_l = n - i - 1
            pow_r = i

            for d in range(9, 0 if i else -1, -1):
                new_remainder = (remainder + rems[d][pow_l] + (0 if pow_l == pow_r else rems[d][pow_r])) % k
                if solve(i + 1, new_remainder) >= 0:
                    dp[i][remainder] = d
                    return d

            return dp[i][remainder]

        solve(0, 0)
        ans = ""
        rem = 0
        for i in range((n + 1) // 2):
            d = dp[i][rem]
            ans += str(d)
            pow_l = n - i - 1
            pow_r = i
            rem = (rem + rems[d][pow_l] + rems[d][pow_r]) % k

        return ans + (ans if (n % 2 == 0) else ans[:-1])[::-1]
61983