<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:
    # 关键是在第i位和第n-1-i位添加一个数d，带来的%k的增量是(10^i + 10^(n-1-i)) * d % k，因此可以dp
    # 从高到低枚举选择的数，贪心地从9到1选择，dfs，找到就可以返回了。
    def largestPalindrome(self, n: int, k: int) -> str:
        P = [0 for i in range(n)]
        P[0] = 1  # 1 % k
        for i in range(1, n):
            P[i] = P[i-1] * 10 % k
        
        ans = ['' for i in range(n)]
        vis = [[0 for i in range(k)] for j in range(n + 1)]
        
        # 当前处理idx，当前已填数字%k是num
        def dfs(idx, num):
            if idx == (n + 1) // 2:
                return num == 0
            
            vis[idx][num] = 1
            for d in range(9, -1, -1):
                if n % 2 and idx == n // 2:
                    t = P[idx] * d % k
                else:
                    t = (P[idx] + P[n-1-idx]) * d % k
                t = (num + t) % k
                if not vis[idx + 1][num] and dfs(idx + 1, t):
                    ans[idx] = ans[n-1-idx] = str(d)
                    return True
            return False
        dfs(0, 0)
        return ''.join(ans)
51328