3533：判断连接可整除性（2257 分）

Ian

2025-04-27 约 516 字预计阅读 2 分钟次阅读

力扣第 447 场周赛第 3 题

题目

给你一个正整数数组 nums 和一个正整数 k。

当 nums 的一个排列中的所有数字，按照排列顺序 连接其十进制表示 后形成的数可以被 k 整除时，我们称该排列形成了一个 可整除连接 。

返回能够形成 可整除连接 且 字典序最小 的排列（按整数列表的形式表示）。如果不存在这样的排列，返回一个空列表。

示例 1：

输入: nums = [3,12,45], k = 5

输出: [3,12,45]

解释:

排列	连接后的值	是否能被 5 整除
[3, 12, 45]	31245	是
[3, 45, 12]	34512	否
[12, 3, 45]	12345	是
[12, 45, 3]	12453	否
[45, 3, 12]	45312	否
[45, 12, 3]	45123	否

可以形成可整除连接且字典序最小的排列是 [3,12,45]。

示例 2：

输入: nums = [10,5], k = 10

输出: [5,10]

解释:

排列	连接后的值	是否能被 10 整除
[5, 10]	510	是
[10, 5]	105	否

可以形成可整除连接且字典序最小的排列是 [5,10]。

示例 3：

输入: nums = [1,2,3], k = 5

输出: []

解释:

由于不存在任何可以形成有效可整除连接的排列，因此返回空列表。

提示：

1 <= nums.length <= 13
1 <= nums[i] <= 10⁵
1 <= k <= 100

分析

状压 dp，令 dfs(st,a) 表示前面已选的部分 mod k 为 a 的情况下剩下的集合 st 的合法排列
从小到大枚举 st 中的数，若选了后存在合法排列直接返回，即是最小的

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class Solution:
    def concatenatedDivisibility(self, nums: List[int], k: int) -> List[int]:
        @cache
        def dfs(st,a):
            if not st:
                return [] if a==0 else None
            for i in range(n):
                if st&1<<i:
                    A = dfs(st^1<<i,(a*f[i]+nums[i])%k)
                    if A!=None:
                        return [nums[i]]+A
            return None
        
        n = len(nums)
        nums.sort()
        f = [pow(10,len(str(a))) for a in nums]
        res = dfs((1<<n)-1,0)
        return res if res!=None else []

315 ms

目录

3533：判断连接可整除性（2257 分）

题目

分析

解答