点击获取AI摘要

3272. 统计好整数的数目 H

给你两个 正 整数 n 和 k 。

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

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

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

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

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

示例 1：

输入： n = 3, k = 5

输出： 27

解释：

部分好整数如下：

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

示例 2：

输入： n = 1, k = 4

输出： 2

解释：

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

示例 3：

输入： n = 5, k = 6

输出： 2468

提示：

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

分析思路

我们可以把问题拆分为两个部分：

  1. 判断数位集合是否有回文排列
    一个数的数位可以重新排列成回文数当且仅当：
    • 当 n 为偶数：所有数字出现次数均为偶数。
    • 当 n 为奇数：最多只有一个数字出现次数为奇数，其余为偶数。
  2. 存在回文排列且该排列满足被 k 整除
    • 由于我们要求构造的回文排列不能有前导 0，所以构造时需要保证最左位数字不为 0。
    • 对于一个给定的符合“回文排列”条件的数位集合，若存在一种排列构成的回文数能被 k 整除，则我们将此多重集认为是合格的。
    • 注意：一个 n 位整数只要其数位集合满足条件（存在至少一种排列构成合格的 k 回文数），那么所有拥有相同数位多重集的 n 位整数都是好整数。

构造方案

由于 n 的范围最多为 10，因此直接枚举所有 n 位回文数来检查被 k 整除的条件是可行的。根据 n 的奇偶性，我们可以分为两种情况：

  • n 为偶数：
    设 m = n/2，回文数为：

    1
    half + reverse(half)

    枚举长度为 m 的数字串，其中第一个字符（对应整体最高位）不为 0。

  • n 为奇数：
    设 m = n//2，则回文数为：

    1
    half + mid + reverse(half)

    其中 half 枚举同上（第一个字符非 0），mid 为 0～9 均可。

对于每个构造出来的回文数，如果它满足能被 k 整除的条件，则提取其“数字多重集”（即各个数字出现的次数），并存入一个集合中，确保对于同一多重集只记录一次。

计数方法

对于一个记录下来的数字多重集（长度为 n），所有的排列数为

total=n!∏d=09(count[d]!)\text{total} = \frac{n!}{\prod_{d=0}^{9} (\text{count}[d]!)}

但由于存在前导 0 的问题，对于包含 0 的情况，我们需要剔除那些首位为 0 的排列。

  • 若多重集中 0 出现次数为 c0 > 0，则固定首位为 0后，剩余排列数为

invalid=(n−1)!(c0−1)!∏d=19(count[d]!)\text{invalid} = \frac{(n-1)!}{(c_0-1)! \prod_{d=1}^{9} (\text{count}[d]!)}

  • 故该多重集对应的合法 n 位数字数为

    valid=total−invalid(当 c0>0)\text{valid} = \text{total} - \text{invalid} \quad \left( \text{当}\ c_0 > 0 \right)

    或者当 c0=0，则 valid = total。

对所有满足条件的多重集，将其合法排列数累加即为答案。

算法时间复杂度分析

  • 枚举回文数

    • 对于 n 为偶数：需要枚举 10n2−1∗910^{\frac{n}{2}-1} * 9 个数，最多约O(10n2)O(10^\frac{n}{2})；
    • 对于 n 为奇数：乘上 10 种中间数字情况，依然是 O(10n2)O(10^\frac{n}2)。

    由于 n ≤ 10，最坏情形枚举数量不会超过 10510^5，计算量是可接受的。

  • 多重集计数
    对于每个多重集，计算排列数的时间复杂度为 O(10)（数字个数恒定），因此总体时间复杂度主要取决于回文数枚举部分，为 O(10n2)O(10^\frac{n}2)。

总结

  1. 枚举所有符合 n 位、无前导 0 的回文数；
  2. 检查该回文数能否被 k 整除；
  3. 对满足条件的回文数，提取其数字多重集，并保证每个多重集只计入一次；
  4. 对每个多重集，计算所有排列中首位不为 0 的排列数，并累加结果。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
from math import factorial

class Solution:
    def countGoodIntegers(self, n: int, k: int) -> int:
        """
        统计 n 位整数中好整数的数量。
        好整数定义为：其数位重新排列后可以得到一个回文且能被 k 整除，
        且排列后不能有前导 0。
        """
        # 对 n==1 情况单独处理
        if n == 1:
            count = 0
            for d in range(1, 10):
                if d % k == 0:
                    count += 1
            return count
        
        good_multisets = set()  # 存储符合条件的多重集（以元组形式存储 0~9 的数字出现次数）
        
        if n % 2 == 0:
            # n 为偶数，回文数由半边构造
            half_len = n // 2
            start = 10 ** (half_len - 1)
            end = 10 ** half_len
            for num in range(start, end):
                half_str = str(num)
                pal_str = half_str + half_str[::-1]  # 构造回文数
                # 已经保证 half_str 的首位不为 '0'
                pal_num = int(pal_str)
                if pal_num % k == 0:
                    counts = [0] * 10
                    for ch in pal_str:
                        counts[int(ch)] += 1
                    good_multisets.add(tuple(counts))
        else:
            # n 为奇数，多一位中间数字
            half_len = n // 2
            # 当 n>=3 时，half_len>=1，此时可以按原逻辑构造
            start = 10 ** (half_len - 1)
            end = 10 ** half_len
            for num in range(start, end):
                half_str = str(num)
                for mid in range(10):
                    pal_str = half_str + str(mid) + half_str[::-1]
                    # half_str 保证首位不为 '0'
                    pal_num = int(pal_str)
                    if pal_num % k == 0:
                        counts = [0] * 10
                        for ch in pal_str:
                            counts[int(ch)] += 1
                        good_multisets.add(tuple(counts))
        
        # 预计算阶乘
        fact = [1] * (n + 1)
        for i in range(1, n + 1):
            fact[i] = fact[i - 1] * i
        
        total_good = 0
        # 对每个符合条件的数字多重集，计算满足无前导0限制的排列数
        for counts in good_multisets:
            # 计算该多重集所有排列数： n! / (c0! * c1! * ... * c9!)
            total_perm = fact[n]
            for c in counts:
                total_perm //= fact[c]
            
            # 如果该多重集中包含0，需要排除首位为0的排列
            if counts[0] > 0:
                # 固定首位为0，剩余的排列数为 (n-1)! / ((c0-1)! * (c1)! ... (c9)!)
                prod_nonzero = 1
                for d in range(1, 10):
                    prod_nonzero *= fact[counts[d]]
                invalid = fact[n - 1] // (fact[counts[0] - 1] * prod_nonzero)
                valid_perm = total_perm - invalid
            else:
                valid_perm = total_perm
            
            total_good += valid_perm
        
        return total_good

注意：需要对 n==1 的情况进行单独处理。由于一位数的重排列只能为其本身，所以对于一位数，只需要统计 1 到 9 中能被 k 整除的数字即可。

  1. 对 n==1 的处理
    直接遍历 1～9 的单个数字，检查每个数字是否能被 k 整除，若能则计数。

  2. 回文数生成

  • 当 n 为偶数时，构造回文数格式为 half + reverse(half)。

  • 当 n 为奇数时，遍历中间数字 mid，构造回文数格式为 half + mid + reverse(half)。

    注：此处保证 half 的首位非 0。

  1. 多重集记录与排列数计算
  • 将符合条件的回文数的数字多重集（各个数字出现的次数）存入集合避免重复计入。
  • 利用阶乘及组合公式计算总排列数，再剔除那些首位为 0 的排列（当数字 0 存在时）。