6893. 特别的排列
Description
Difficulty: 中等
Related Topics:
给你一个下标从 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 <= 14
- 1 <= nums[i] <= 109
Solution
排列问题时间复杂度为O(n!),一般阶乘能支持最大10! ~= 106,这里已经到了14,显然需要降低到2n,因此需要用状态压缩。
只需要考虑将剩余的数字用二进制保存下来即可,然后dfs。
Language: Python3
class Solution:
def specialPerm(self, nums: List[int]) -> int:
MOD = 10 ** 9 + 7
n = len(nums)
@cache
def dfs(i, rest):
if rest == 0: return 1
res = 0
for j, num in enumerate(nums):
if rest & (1 << j) and (nums[j] % nums[i] == 0 or nums[i] % nums[j] == 0):
res = (res + dfs(j, rest ^ (1 << j))) % MOD
return res
rest = (1 << n) - 1
res = 0
for i in range(n):
res = (res + dfs(i, rest ^ (1 << i))) % MOD
return res
标签:特别,排列,nums,压缩,示例,rest,6893
From: https://www.cnblogs.com/hyserendipity/p/17489785.html