题目描述

如果一个$1$~$n$的排列$p$，对于每个$i=1,2,3,…n$，都满足$i$和$p[i]$ 其中一个能整除另一个，则称$p$是好的。

输入$n(1 \leq n \leq 15)$，输出有多少个$1$~$n$的排列是好的。

输入样例$1$

2

输入样例$1$

2

输入样例$2$

1

输入样例$2$

1

算法

状压DP

这么小的数据范围，直接状压DP来进行计数。用一个$n$位二进制数$mask$来表示$1$~$n$中数字的使用情况，如果第$i$位为$1$，说明排列中已经使用了数字$i+1$。

状态定义

$dp[mask][i]$表示数集为$mask$且以$i+1$结尾的排列数目，在这个定义下，答案就应该是$\Sigma_{i \in [0,n)}dp[2^n-1][i]$。

状态转移

先初始化排列长度为$1$时的答案，由于任何数字放在第一位都是可以的，因此$dp[2^i][i]=1,i \in [0,n)$。然后枚举所有状态$mask$，只要$mask$中超过一个$1$就进行状态转移，枚举排列的最后两个数$i$和$j$，$i$是最后一个数，$j$是倒数第二个数。

状态转移需要满足$i+1|sz$或$sz|i+1$，其中$sz$为$mask$中$1$的数量，$|$表示整除符号。状态转移方程为$dp[mask][i]=\Sigma_{j \in [0,n),i \neq j}dp[mask \oplus 2^i][j]$。

复杂度分析

时间复杂度

枚举$mask$的时间复杂度为$O(2^n)$，内部双重循环枚举序列的后两个元素时间复杂度为$O(n^2)$。因此，整个算法的时间复杂度为$O(n^2 \times 2^n)$

空间复杂度

状态数量为$n2^n$，因此算法的额外空间复杂度为$O(n2^n)$。

C++ 代码

const int N = 16;
int dp[1<<N][N];

class Solution {
public:
    int countArrangement(int n) {
        memset(dp, 0, sizeof(dp));
        for(int i = 0; i < n; i++) {
            dp[1<<i][i] = 1;
        }
        for(int mask = 1; mask < 1<<n; mask++) {
            int sz = __builtin_popcount(mask);
            if(sz == 1) continue;
            for(int i = 0; i < n; i++) {
                if(mask>>i&1) {
                    // i放在排列的最后
                    for(int j = 0; j < n; j++) {
                        if(i == j) continue;
                        if((i + 1) % sz == 0 || sz % (i + 1) == 0) {
                            dp[mask][i] += dp[mask^(1<<i)][j];
                        }
                    }
                }
            }
        }
        int ans = 0;
        for(int i = 0; i < n; i++) {
            ans += dp[(1<<n) - 1][i];
        }
        return ans;
    }
};