题目描述
给你一个下标从 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
解法
方法一：状态压缩动态规划
我们注意到题目中数组的长度最大不超过 $14$，因此，我们可以用一个二进制整数来表示当前的状态，其中第 $i$ 位为 $1$ 表示数组中的第 $i$ 个数已经被选取，为 $0$ 表示数组中的第 $i$ 个数还未被选取。
我们定义 $f[i][j]$ 表示当前选取的整数状态为 $i$，且最后一个选取的整数下标为 $j$ 的方案数。初始时 $f[0][0]=0$，答案为 $\sum_{j=0}{n-1}f[2n-1][j]$。
考虑 $f[i][j]$，如果当前只有一个数被选取，那么 $f[i][j]=1$。否则，我们可以枚举上一个选择的数的下标 $k$，如果 $k$ 与 $j$ 对应的数满足题目要求，那么 $f[i][j]$ 可以从 $f[i \oplus 2^j][k]$ 转移而来。即：
$$
f[i][j]=
\begin{cases}
1, & i=2^j\
\sum_{k=0}^{n-1}f[i \oplus 2^j][k], & i \neq 2^j \textit{且} \textit{nums}[j] \textit{与} \textit{nums}[k] \textit{满足题目要求}\
\end{cases}
$$
最终答案即为 $\sum_{j=0}{n-1}f[2n-1][j]$。注意答案可能很大，需要对 $10^9+7$ 取模。
时间复杂度 $O(n^2 \times 2^n)$，空间复杂度 $O(n \times 2^n)$。其中 $n$ 为数组的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | class Solution:
def specialPerm(self, nums: List[int]) -> int:
mod = 10**9 + 7
n = len(nums)
m = 1 << n
f = [[0] * n for _ in range(m)]
for i in range(1, m):
for j, x in enumerate(nums):
if i >> j & 1:
ii = i ^ (1 << j)
if ii == 0:
f[i][j] = 1
continue
for k, y in enumerate(nums):
if x % y == 0 or y % x == 0:
f[i][j] = (f[i][j] + f[ii][k]) % mod
return sum(f[-1]) % mod
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29 | class Solution {
public int specialPerm(int[] nums) {
final int mod = (int) 1e9 + 7;
int n = nums.length;
int m = 1 << n;
int[][] f = new int[m][n];
for (int i = 1; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if ((i >> j & 1) == 1) {
int ii = i ^ (1 << j);
if (ii == 0) {
f[i][j] = 1;
continue;
}
for (int k = 0; k < n; ++k) {
if (nums[j] % nums[k] == 0 || nums[k] % nums[j] == 0) {
f[i][j] = (f[i][j] + f[ii][k]) % mod;
}
}
}
}
}
int ans = 0;
for (int x : f[m - 1]) {
ans = (ans + x) % mod;
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31 | class Solution {
public:
int specialPerm(vector<int>& nums) {
const int mod = 1e9 + 7;
int n = nums.size();
int m = 1 << n;
int f[m][n];
memset(f, 0, sizeof(f));
for (int i = 1; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if ((i >> j & 1) == 1) {
int ii = i ^ (1 << j);
if (ii == 0) {
f[i][j] = 1;
continue;
}
for (int k = 0; k < n; ++k) {
if (nums[j] % nums[k] == 0 || nums[k] % nums[j] == 0) {
f[i][j] = (f[i][j] + f[ii][k]) % mod;
}
}
}
}
}
int ans = 0;
for (int x : f[m - 1]) {
ans = (ans + x) % mod;
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29 | func specialPerm(nums []int) (ans int) {
const mod int = 1e9 + 7
n := len(nums)
m := 1 << n
f := make([][]int, m)
for i := range f {
f[i] = make([]int, n)
}
for i := 1; i < m; i++ {
for j, x := range nums {
if i>>j&1 == 1 {
ii := i ^ (1 << j)
if ii == 0 {
f[i][j] = 1
continue
}
for k, y := range nums {
if x%y == 0 || y%x == 0 {
f[i][j] = (f[i][j] + f[ii][k]) % mod
}
}
}
}
}
for _, x := range f[m-1] {
ans = (ans + x) % mod
}
return
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25 | function specialPerm(nums: number[]): number {
const mod = 1e9 + 7;
const n = nums.length;
const m = 1 << n;
const f = Array.from({ length: m }, () => Array(n).fill(0));
for (let i = 1; i < m; ++i) {
for (let j = 0; j < n; ++j) {
if (((i >> j) & 1) === 1) {
const ii = i ^ (1 << j);
if (ii === 0) {
f[i][j] = 1;
continue;
}
for (let k = 0; k < n; ++k) {
if (nums[j] % nums[k] === 0 || nums[k] % nums[j] === 0) {
f[i][j] = (f[i][j] + f[ii][k]) % mod;
}
}
}
}
}
return f[m - 1].reduce((acc, x) => (acc + x) % mod);
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32 | impl Solution {
pub fn special_perm(nums: Vec<i32>) -> i32 {
const MOD: i32 = 1_000_000_007;
let n = nums.len();
let m = 1 << n;
let mut f = vec![vec![0; n]; m];
for i in 1..m {
for j in 0..n {
if (i >> j) & 1 == 1 {
let ii = i ^ (1 << j);
if ii == 0 {
f[i][j] = 1;
continue;
}
for k in 0..n {
if nums[j] % nums[k] == 0 || nums[k] % nums[j] == 0 {
f[i][j] = (f[i][j] + f[ii][k]) % MOD;
}
}
}
}
}
let mut ans = 0;
for &x in &f[m - 1] {
ans = (ans + x) % MOD;
}
ans
}
}
|