<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:
        pow10modk = [1] * n
        for i in range(1, n):
            pow10modk[i] = pow10modk[i - 1] * 10 % k

        m = (n + 1) // 2
        memo = {}
        def dfs(i: int, q: int, path) -> bool:
            if i == m:
                if q == 0:
                    self.res = ''.join(path)
                    return True
                return False
            
            if (i, q) in memo:
                return memo[(i, q)]

            for d in range(9, -1, -1):  # 贪心：从大到小枚举
                if n % 2 and i == m - 1:  # 正中间
                    q2 = (q + d * pow10modk[i]) % k
                else:
                    q2 = (q + d * (pow10modk[i] + pow10modk[-1 - i])) % k
                path.append(str(d))
                if dfs(i + 1, q2, path):
                    memo[(i, q)] = True
                    return True
                path.pop()
            memo[(i, q)] = False
            return False
        self.res = ''
        dfs(0, 0, [])
        if n % 2 == 0:
            return self.res + self.res[::-1]
        return self.res + self.res[::-1][1:]

# https://leetcode.cn/problems/find-the-largest-palindrome-divisible-by-k/solutions/2884548/tong-yong-zuo-fa-jian-tu-dfsshu-chu-ju-t-m3pu/
227136