题目 #

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 $10^9 + 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 <= 14
$1 <= nums[i] <= 10^9$

思路1 dp递推 #

分析 #

一位一位数放，将某个数是否出现过记录在二进制数中
记录上一位出现的数字，枚举下一位可以出现什么数字，记录的是第i位是x的某个状态的数量

代码 #

 1func specialPerm1(nums []int) int {
 2	var mod int = 1e9 + 7
 3	n := len(nums)
 4	// 第一维是上一位是什么数字，第二维是状态（保存什么数字出现过的二进制），value为数量
 5	stMap := map[int]map[uint16]int{}
 6	for i, v := range nums {
 7		stMap[v] = map[uint16]int{
 8			1 << i: 1,
 9		}
10	}
11	for i := 1; i < n; i++ {
12		tmp := stMap
13		stMap = make(map[int]map[uint16]int)
14		// 遍历map，找state中没出现过的数字，看能否填到此位，能填就加上数量
15		for l, vMap := range tmp {
16			// 遍历所有的状态，然后遍历所有的nums，没出现过且可以放就放进去
17			for j, v := range nums {
18				for st, c := range vMap {
19					// 出现过或不能放到下一位就跳过
20					if st&(1<<j) > 0 || (v%l != 0 && l%v != 0) {
21						continue
22					}
23					if stMap[v] == nil {
24						stMap[v] = make(map[uint16]int)
25					}
26					st |= (1 << j)
27					stMap[v][st] = (stMap[v][st] + c) % mod
28				}
29			}
30		}
31	}
32	res := 0
33	for _, c := range stMap {
34		for _, c1 := range c {
35			res = (res + c1) % mod
36		}
37	}
38	return res
39}

思路2 优化时间复杂度 #

分析 #

在上一步的基础上，发现每次要遍历所有的数，如果提前把某个数下一个数能选啥给找出来可以遍历少一点

代码 #

 1func specialPerm(nums []int) int {
 2	var mod int = 1e9 + 7
 3	// 先找出谁能和谁做邻居
 4	// key为数字值，v为index
 5	pMap := map[int][]int{}
 6	n := len(nums)
 7	for i, v := range nums {
 8		for j := i + 1; j < n; j++ {
 9			v1 := nums[j]
10			if v%v1 == 0 || v1%v == 0 {
11				pMap[v] = append(pMap[v], j)
12				pMap[v1] = append(pMap[v1], i)
13			}
14		}
15	}
16	stMap := map[int]map[uint16]int{}
17	for i, v := range nums {
18		stMap[v] = map[uint16]int{
19			1 << i: 1,
20		}
21	}
22	for range nums[:n-1] {
23		tmp := stMap
24		stMap = make(map[int]map[uint16]int)
25		// 遍历map，找state中没出现过的数字，看能否填到此位，能填就加上数量
26		for k, v := range tmp {
27			for _, v1 := range pMap[k] {
28				for st, c := range v {
29					if st&(1<<v1) > 0 {
30						continue
31					}
32					st |= 1 << v1
33					if stMap[nums[v1]] == nil {
34						stMap[nums[v1]] = make(map[uint16]int)
35					}
36					stMap[nums[v1]][st] = (stMap[nums[v1]][st] + c) % mod
37				}
38			}
39		}
40	}
41	res := 0
42	for _, c := range stMap {
43		for _, c1 := range c {
44			res = (res + c1) % mod
45		}
46	}
47	return res
48}