Description#
You are given a 0-indexed integer array nums containing n distinct positive integers. A permutation of nums is called special if:
- For all indexes
0 <= i < n - 1, either nums[i] % nums[i+1] == 0 or nums[i+1] % nums[i] == 0.
Return the total number of special permutations. As the answer could be large, return it modulo 109 + 7.
Example 1:
Input: nums = [2,3,6]
Output: 2
Explanation: [3,6,2] and [2,6,3] are the two special permutations of nums.
Example 2:
Input: nums = [1,4,3]
Output: 2
Explanation: [3,1,4] and [4,1,3] are the two special permutations of nums.
Constraints:
2 <= nums.length <= 141 <= nums[i] <= 109
Solutions#
Solution 1#
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
}
|
