题目描述
给你一个下标从 0 开始的整数数组 nums
,它包含 n
个 互不相同 的正整数。如果 nums
的一个排列满足以下条件,我们称它是一个特别的排列:
对于 0 <= i < n - 1
的下标 i
,要么 nums[i] % nums[i+1] == 0
,要么 nums[i+1] % nums[i] == 0
。
请你返回特别排列的总数目,由于答案可能很大,请将它对 10^9 + 7
取余 后返回。
样例
输入:nums = [2,3,6]
输出:2
解释:[3,6,2] 和 [2,6,3] 是 nums 两个特别的排列。
输入:nums = [1,4,3]
输出:2
解释:[3,1,4] 和 [4,1,3] 是 nums 两个特别的排列。
限制
2 <= nums.length <= 14
1 <= nums[i] <= 10^9
算法
(状态压缩动态规划) $O(n^2 \cdot 2^n)$
- 设状态 $f(mask, i)$ 表示考虑的下标集合为 $mask$,且最后一个元素的下标为 $i$ 的方案数。
- 初始时,$f(\{i\}, i) = 1$,其余为 $0$ 待定。
- 转移时,枚举不在 $mask$ 中的元素下标 $j$,判定满足题目条件后,转移 $f(mask \bigcup \{j\}, j) = f(mask \bigcup \{j\}, j) + f(mask, i)$。
- 最终答案为 $\sum f(\{0, 1, 2, \dots n - 1\}, i)$。
时间复杂度
- 状态数为 $O(n \cdot 2^n)$,转移时间为 $O(n)$,故总时间复杂度为 $O(n^2 \cdot 2^n)$。
空间复杂度
- 需要 $O(n \cdot 2^n)$ 的额外空间存储状态。
C++ 代码
class Solution {
public:
int specialPerm(vector<int>& nums) {
const int n = nums.size();
const int mod = 1000000007;
vector<vector<int>> f(1 << n, vector<int>(n, 0));
for (int i = 0; i < n; i++)
f[1 << i][i] = 1;
for (int mask = 1; mask < (1 << n); mask++)
for (int i = 0; i < n; i++) {
if (((mask >> i) & 1) == 0)
continue;
for (int j = 0; j < n; j++) {
if (((mask >> j) & 1))
continue;
if ((nums[i] % nums[j]) && (nums[j] % nums[i]))
continue;
int new_mask = mask | (1 << j);
f[new_mask][j] = (f[new_mask][j] + f[mask][i]) % mod;
}
}
int ans = 0;
for (int i = 0; i < n; i++)
ans = (ans + f[(1 << n) - 1][i]) % mod;
return ans;
}
};