难度: Medium
给你一个下标从 0 开始的整数数组 nums ，它包含 n 个 互不相同 的正整数。如果 nums 的一个排列满足以下条件，我们称它是一个特别的排列：
0 <= i < n - 1 的下标 i ，要么 nums[i] % nums[i+1] == 0 ，要么 nums[i+1] % nums[i] == 0 。请你返回特别排列的总数目，由于答案可能很大，请将它对 109 + 7 取余 后返回。
示例 1：
输入：nums = [2,3,6] 输出：2 解释：[3,6,2] 和 [2,6,3] 是 nums 两个特别的排列。
示例 2：
输入：nums = [1,4,3] 输出：2 解释：[3,1,4] 和 [4,1,3] 是 nums 两个特别的排列。
提示：
2 <= nums.length <= 141 <= nums[i] <= 109运行时间: 305 ms
内存: 29.2 MB
class Solution:
def specialPerm(self, nums: List[int]) -> int:
nums.sort()
r, mod = range(len(nums)), 10**9 + 7
g = [1 << i for i in r]
for i, j in combinations(r, 2):
if nums[j] % nums[i] == 0:
g[i] |= 1 << j
g[j] |= 1 << i
ends = [i for i, b in enumerate(g) if b.bit_count() == 2]
if any(i.bit_count() == 1 for i in g) or len(ends) > 2:
return 0
def ones(mask):
while mask:
i = mask.bit_length() - 1
yield i
mask ^= 1 << i
@cache
def complete(mask):
return all(g[i] & mask == mask for i in ones(mask)) and factorial(mask.bit_count() - 1)
@cache
def unconnected(mask):
return any(g[i] & mask == 1 << i for i in ones(mask))
@cache
def dfs(start, mask):
intersection = g[start] & mask
if intersection == 0:
return 0
if cm := complete(mask):
return cm * intersection.bit_count()
if unconnected(mask):
return 0
return sum(dfs(i, mask ^ (1 << i)) for i in ones(intersection))
universal = (1 << len(nums)) - 1
g.append(1 << ends[0] if ends else universal)
ans = dfs(-1, universal) % mod
return ans * 2 % mod if ends else ans
该题解采用了动态规划与深度优先搜索（DFS）结合的方法来解决问题。首先对数组进行排序，利用排序的特性简化除法运算的条件检查。接着，构建一个图的表示方式，用一个整数数组g来表示节点之间的连接关系，其中g[i]的二进制中的第j位如果是1，表示nums[i]和nums[j]之间可以相互整除。然后，通过DFS遍历所有可能的排列组合，使用位掩码技术来表示当前已经选择的元素集合。最后，利用缓存机制（@cache）来优化重复计算，提高效率。
时间复杂度: O(n * 2^n)
空间复杂度: O(n + 2^n)
class Solution:
def specialPerm(self, nums: List[int]) -> int:
nums.sort() # 先对数组排序
r, mod = range(len(nums)), 10**9 + 7
g = [1 << i for i in r] # 初始化每个数自己的掩码
for i, j in combinations(r, 2): # 生成所有可能的两数组合
if nums[j] % nums[i] == 0: # 检查是否整除
g[i] |= 1 << j
g[j] |= 1 << i
ends = [i for i, b in enumerate(g) if b.bit_count() == 2] # 查找端点
if any(i.bit_count() == 1 for i in g) or len(ends) > 2: # 检查是否存在单独点或端点过多
return 0
def ones(mask): # 生成mask中所有为1的位的索引
while mask:
i = mask.bit_length() - 1
yield i
mask ^= 1 << i
@cache
def complete(mask): # 检查mask是否为一个完整的子图
return all(g[i] & mask == mask for i in ones(mask)) and factorial(mask.bit_count() - 1)
@cache
def unconnected(mask): # 检查是否有未连接的点
return any(g[i] & mask == 1 << i for i in ones(mask))
@cache
def dfs(start, mask): # 深度优先搜索
intersection = g[start] & mask
if intersection == 0:
return 0
if cm := complete(mask):
return cm * intersection.bit_count()
if unconnected(mask):
return 0
return sum(dfs(i, mask ^ (1 << i)) for i in ones(intersection))
universal = (1 << len(nums)) - 1
g.append(1 << ends[0] if ends else universal)
ans = dfs(-1, universal) % mod
return ans * 2 % mod if ends else ans
在数组排序之后，较小的数字会位于数组的前面，较大的数字则位于后面。这种排序可以简化除法条件的检查，因为对于任何两个数nums[i]和nums[j]，如果i < j，那么nums[i]必然不大于nums[j]。这使得我们只需要检查nums[j]是否可以被nums[i]整除，而不必再检查nums[i]是否可以被nums[j]整除，从而减少了需要进行的除法运算次数，并提高了整体算法的效率。
在题解中，每一个整数g[i]的二进制表示形式用来表示元素nums[i]与其他元素之间的关系。具体来说，如果g[i]的第j位是1（从0开始计数），这表示nums[i]可以与nums[j]相互整除。使用这种二进制位来表示连接关系的优势在于它极大地节省了空间，同时也方便了快速的位运算处理，如位与（&）、位或（|），以及位异或（^）。这种表示方法使得检查和更新节点之间关系的操作更加高效，特别是在需要频繁查询和修改节点间关系的图算法中。
在题解中，'端点'指的是那些在整除关系图中只与一个其他节点相连的节点。在二进制表示中，这样的端点的g[i]会恰好有两个1位（包括自身和连接的另一个节点）。如果一个图的端点数量超过两个，这意味着无法形成一个闭合的环或一条简单的链，这通常代表图不连贯或存在多个独立的子图，这不符合题目要求的特别排列条件。因此，如果端点数量超过两个，函数会直接返回0，表示不存在有效的排列方式。
在DFS函数中，位掩码用于有效地跟踪和管理在当前递归调用中已经被选中的元素。位掩码是一个整数，其中的每一位对应于nums数组中的一个元素。如果某位是1，这表示对应的元素已经被选中。在DFS递归过程中，每选择一个新元素，我们就通过位或运算将该元素对应的位设置为1。这种方法不仅减少了存储空间的需求（不需要额外的数组来跟踪选择状态），还使得操作如检查元素是否被选中（位与操作）和更新选择状态（位异或操作）变得非常快速和直接。