原题链接：Leetcode 526. 优美的排列

DFS:

class Solution {
public:
    vector<vector<int>> match;
    vector<int> vis;
    int res=0;
    void dfs(int i,int n)
    {
        if(i==n+1)
        {
            res++;
            return;
        }
        for(auto x:match[i])
        {
            if(!vis[x])
            {
                vis[x]=1;
                dfs(i+1,n);
                vis[x]=0;
            }
        }
    }
    int countArrangement(int n) {
        match.resize(n+1);
        vis.resize(n+1);
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(i%j==0 || j%i==0)
                {
                    match[i].push_back(j);
                }
            }
        }   
        dfs(1,n);
        return res;
    }
};

状态压缩：【宫水三叶】详解两种状态压缩 DP 思路

class Solution {
public:
    int countArrangement(int n) {
        int mask=1<<n;
        vector<vector<int>> f(n+1,vector<int>(mask));
        f[0][0]=1;
        for(int i=1;i<=n;i++)
        {    // 枚举所有的状态
            for(int state=0;state<mask;state++)
            {   // 枚举位置 i（最后一位）选的数值是 k
                for(int  k=1;k<=n;k++)
                {
                    // 首先 k 在 state 中必须是 1
                    if(((state>>(k-1))&1)==0) continue;
                    // 数值 k 和位置 i 之间满足任一整除关系
                    if(k%i!=0 && i%k!=0) continue;
                    // state & (~(1 << (k - 1))) 代表将 state 中数值 k 的位置置零
                    f[i][state]+=f[i-1][state&(~(1<<(k-1)))];
                }
            }
        }
        return f[n][mask-1];
    }
};