golang 解法, 执行用时: 4 ms, 内存消耗: 2.3 MB, 提交时间: 2022-11-17 10:52:59

func countArrangement(n int) int {
    f := make([]int, 1<<n)
    f[0] = 1
    for mask := 1; mask < 1<<n; mask++ {
        num := bits.OnesCount(uint(mask))
        for i := 0; i < n; i++ {
            if mask>>i&1 > 0 && (num%(i+1) == 0 || (i+1)%num == 0) {
                f[mask] += f[mask^1<<i]
            }
        }
    }
    return f[1<<n-1]
}

python3 解法, 执行用时: 164 ms, 内存消耗: 15.2 MB, 提交时间: 2022-11-17 10:52:40

'''
状态压缩+动态规划

由于题目保证了排列的长度 n 至多为 15，因此我们可以用一个位数为 n 的二进制数 mask 表示排列中的数被选取的情况。
若 mask 中的第 i 位为 1（从 0 开始编号），则数 i+1 已经被选取，否则就还未被选取。
我们可以利用这样的二进制数表示选取数的过程的状态，以 n = 4, mask=(0110)2 为例，这代表数 2,3 都已经被选取，
并以任意顺序放置在排列中前两个位置。

令 f[mask] 表示状态为 mask 时的可行方案总数，这样答案即为 f[2^n - 1]
'''
class Solution:
    def countArrangement(self, n: int) -> int:
        f = [0] * (1 << n)
        f[0] = 1
        for mask in range(1, 1 << n):
            num = bin(mask).count("1")
            for i in range(n):
                if mask & (1 << i) and (num % (i + 1) == 0 or (i + 1) % num == 0):
                    f[mask] += f[mask ^ (1 << i)]
        
        return f[(1 << n) - 1]

golang 解法, 执行用时: 16 ms, 内存消耗: 1.8 MB, 提交时间: 2022-11-17 10:48:06

func countArrangement(n int) (ans int) {
    vis := make([]bool, n+1)
    match := make([][]int, n+1)
    for i := 1; i <= n; i++ {
        for j := 1; j <= n; j++ {
            if i%j == 0 || j%i == 0 {
                match[i] = append(match[i], j)
            }
        }
    }

    var backtrack func(int)
    backtrack = func(index int) {
        if index > n {
            ans++
            return
        }
        for _, x := range match[index] {
            if !vis[x] {
                vis[x] = true
                backtrack(index + 1)
                vis[x] = false
            }
        }
    }
    backtrack(1)
    return
}

python3 解法, 执行用时: 456 ms, 内存消耗: 14.9 MB, 提交时间: 2022-11-17 10:47:47

'''
回溯法，从左向右依次向目标排列中放入数即可。

具体地，我们定义函数 backtrack(index,n)，表示尝试向位置 index 放入数。其中 n 表示排列的长度。
在当前函数中，我们首先找到一个符合条件的未被使用过的数，然后递归地执行 backtrack(index+1,n)，
当该函数执行完毕，回溯到当前层，我们再尝试下一个符合条件的未被使用过的数即可。

回溯过程中，我们可以用 vis 数组标记哪些数被使用过，每次我们选中一个数 x，我们就将 vis[x] 标记为 true，
回溯完成后，我们再将其置为 false。

特别地，为了优化回溯效率，我们可以预处理每个位置的符合条件的数有哪些，
用二维数组 match 保存。当我们尝试向位置 index 放入数时，我们只需要遍历 match[index] 即可。
'''
class Solution:
    def countArrangement(self, n: int) -> int:
        match = defaultdict(list)
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                if i % j == 0 or j % i == 0:
                    match[i].append(j)
        
        num = 0
        vis = set()

        def backtrack(index: int) -> None:
            if index == n + 1:
                nonlocal num
                num += 1
                return
            
            for x in match[index]:
                if x not in vis:
                    vis.add(x)  # 加入
                    backtrack(index + 1) # 递归回溯其他位置
                    vis.discard(x)  # 丢弃
                   
        backtrack(1) # 从index=1的位置开始
        return num