2741. 特别的排列

描述

给你一个下标从 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 两个特别的排列。

看不懂

代码

const MOD int64 = 1000000007

func specialPerm(nums []int) int {
	n := len(nums)
	// 1<<n   2的n次方
	f := make([][]int64, 1<<n)
	for i := range f {
		f[i] = make([]int64, n)
	}
	for i := 0; i < n; i++ {
		f[1<<i][i] = 1
	}
	
	for state := 1; state < (1 << n); state++ {
		for i := 0; i < n; i++ {
			if state>>i&1 == 0 {
				continue
			}
			for j := 0; j < n; j++ {
				if i == j || state>>j&1 == 0 {
					continue
				}
				x := nums[i]
				y := nums[j]
				if x%y != 0 && y%x != 0 {
					continue
				}
				f[state][i] = (f[state][i] + f[state^(1<<i)][j]) % MOD
			}
		}
	}

	var sum int64
	for i := 0; i < n; i++ {
		sum = (sum + f[(1<<n)-1][i]) % MOD
	}
	return int(sum)
}