以下是 LeetCode 3533. 判断连接可整除性 的完整 Python3 实现可直接提交pythonfrom functools import lru_cachefrom typing import Listclass Solution:def concatenatedDivisibility(self, nums: List[int], k: int) - List[int]:n len(nums)# 排序保证按升序枚举时第一个可行解即为字典序最小nums.sort()# 预计算每个数字的位数以及 10^位数 % kpow10 [pow(10, len(str(x)), k) for x in nums]# ---------- 状压记忆化搜索判断可行性 ----------lru_cache(None)def dfs(mask: int, mod: int) - bool:mask: 已使用数字的位掩码 (0 ~ 2^n-1)mod: 当前连接数对 k 的余数返回是否存在一种后续排列使得最终能被 k 整除if mask (1 n) - 1: # 所有数字已用完return mod 0for i in range(n):if not (mask i) 1: # nums[i] 尚未使用# 新余数 旧余数 * 10^len(nums[i]) nums[i]new_mod (mod * pow10[i] nums[i]) % kif dfs(mask | (1 i), new_mod):return Truereturn False# 若不存在任何合法排列直接返回空数组if not dfs(0, 0):return []# ---------- 重建字典序最小的合法排列 ----------res []mask, mod 0, 0while mask ! (1 n) - 1:for i in range(n):if not (mask i) 1:new_mod (mod * pow10[i] nums[i]) % kif dfs(mask | (1 i), new_mod):res.append(nums[i])mask | (1 i)mod new_modbreakreturn res---核心思路步骤 说明1. 排序 nums.sort() 确保后续按升序枚举第一个找到的解即为字典序最小2. 预计算 pow10[i] 10^len(str(nums[i])) % k避免重复计算大数次幂3. 状压DP dfs(mask, mod) 表示已用 mask 中的数字、当前余数为 mod能否完成整除连接4. 状态转移 枚举未使用的 nums[i]新余数 (mod × 10^len nums[i]) % k5. 路径重建 利用已缓存的 dfs 结果贪心选择第一个能导向合法解的数字---复杂度分析- 时间复杂度O(n \cdot 2^n \cdot k)共 2^n \cdot k 个状态每个状态最多枚举 n 个转移- 空间复杂度O(2^n \cdot k)lru_cache 缓存所有状态---关键点1. 字典序最小如何保证先排序DFS 和重建路径时都按升序尝试。由于一旦找到可行解就立即返回第一个成功路径必然是字典序最小的。2. 为什么用 pow(10, len, k)Python 内置三参数 pow(base, exp, mod) 使用快速幂算法可在 O(\log \text{len}) 内完成取模避免大整数运算。3. 重建路径时为何直接调用 dfsdfs 已被 lru_cache 缓存重建时的调用均为 O(1) 查表不会重复计算。