题目描述

给你两个 正 整数 n 和 k。

如果一个整数 x 满足以下条件，那么它被称为 k 回文 整数 。

• x 是一个 回文整数。
• x 能被 k 整除。

如果一个整数的数位重新排列后能得到一个 k 回文整数，那么我们称这个整数为 好 整数。比方说，k = 2，那么 2020 可以重新排列得到 2002，2002 是一个 k 回文串，所以 2020 是一个好整数。而 1010 无法重新排列数位得到一个 k 回文整数。

请你返回 n 个数位的整数中，有多少个 好 整数。

注意，任何整数在重新排列数位之前或者之后 都不能 有前导 0。比方说 1010 不能重排列得到 101。

样例

输入：n = 3, k = 5

输出：27

解释：

部分好整数如下：

551，因为它可以重排列得到 515。
525，因为它已经是一个 k 回文整数。

输入：n = 1, k = 4

输出：2

解释：

两个好整数分别是 4 和 8。

输入：n = 5, k = 6

输出：2468

限制

• 1 <= n <= 10
• 1 <= k <= 9

算法

(暴力枚举，组合数学) $O(n^2 + \cdot 10^{\lceil \frac{n}{2} \rceil} \cdot n \log n)$

1. 暴力枚举长度为 $n$ 的所有 k 回文整数，并将整数转为字符串最小的字典序存到哈希表中。
2. 遍历哈希表，对于每个数字字符串，统计出其能组成多少个合法的重排列。
3. 这是一个经典的组合数学和乘法原理问题：统计出每个数字的出现次数，并按顺序依次考虑每个数字。数字 $0$ 可以放到除首位外的其他位，其他数字可以放到任意位置，按照组合数计算每一步的值。

时间复杂度

• 预处理的时间复杂度为 $O(n^2)$。
• 枚举回文数的时间复杂度为 $O(10^{\lceil \frac{n}{2} \rceil})$，每个回文数都需要 $O(n \log n)$ 的时间存储到哈希表中。
• 计算每个数字组成答案个数的时间复杂度为 $O(n)$。
• 故总时间复杂度为 $O(n^2 + \cdot 10^{\lceil \frac{n}{2} \rceil} \cdot n \log n)$。

空间复杂度

• 需要 $O(n^2 + \cdot 10^{\lceil \frac{n}{2} \rceil} \cdot n)$ 的额外空间存储预处理数组，哈希表和排序的系统栈。

C++ 代码

#define LL long long

class Solution {
private:
    int C[11][11];
    LL power[11];

    void init() {
        C[0][0] = 1;
        power[0] = 1;
        for (int i = 1; i <= 10; i++) {
            C[i][0] = C[i - 1][0];
            for (int j = 1; j <= 10; j++)
                C[i][j] = C[i - 1][j] + C[i - 1][j - 1];

            power[i] = power[i - 1] * 10;
        }
    }

    int calc(int n, const string &r) {
        vector<int> d(10, 0);
        for (char c : r)
            ++d[c - '0'];

        int tot = C[n - 1][d[0]];
        n -= d[0];
        for (int i = 1; i < 10; i++) {
            tot *= C[n][d[i]];
            n -= d[i];
        }

        return tot; 
    }

public:
    LL countGoodIntegers(int n, int k) {
        init();

        unordered_set<string> h;
        for (int i = 1; i < power[(n + 1) / 2]; i++) {
            if (i % 10 == 0)
                continue;

            int x = i;
            LL num = i;
            for (int k = 1; k <= n / 2; k++) {
                num += x % 10 * power[n - k];
                x /= 10;
            }

            if (num % k != 0)
                continue;

            string r = to_string(num);
            sort(r.begin(), r.end());
            h.insert(r);
        }

        LL ans = 0;
        for (const string &r : h)
            ans += calc(n, r);

        return ans;
    }
};