题目描述

假设有从 1 到 n 的 n 个整数。用这些整数构造一个数组 perm（下标从 1 开始），只要满足下述条件 之一，该数组就是一个 优美的排列：

• perm[i] 能够被 i 整除
• i 能够被 perm[i] 整除

给你一个整数 n，返回可以构造的 优美排列 的 数量。

样例

输入：n = 2
输出：2
解释：
第 1 个优美的排列是 [1,2]：
    - perm[1] = 1 能被 i = 1 整除
    - perm[2] = 2 能被 i = 2 整除
第 2 个优美的排列是 [2,1]:
    - perm[1] = 2 能被 i = 1 整除
    - i = 2 能被 perm[2] = 1 整除

输入：n = 1
输出：1

限制

• 1 <= n <= 15

算法

(动态规划，状态压缩) $O(n \cdot 2^n)$

1. 状态 $f(S)$ 表示用去的数字集合为 $S$的方案数。其中 $S$ 是一个整数，$S$ 的二进制表示中，为 0 的数位表示该数字还没被用过，为 1 的数位表示已经被用过。
2. 从 1 开始枚举 $S$，保证 $f(S) > 0$（否则没有意义），统计 $S$ 中用过数字的个数 $tot$，然后从 $S$ 中选择一个没有被使用过的数字$i$，然后用$tot$ 和 $i$ 判断该数字是否满足题目中的两个条件。若满足，则 f(S | 1 << i) += f(S)。
3. 初始时，$f(1 << i) = 1$。最终答案为 $f((1 << n) - 1)$。

时间复杂度

• 状态数为 $O(2^n)$，决策数为 $O(n)$，转移时间为 $O(1)$，故总时间复杂度为 $O(n \cdot 2^n)$。

C++ 代码

class Solution {
public:
    int countArrangement(int n) {
        vector<int> f(1 << n, 0);
        for (int i = 0; i < n; i++)
            f[1 << i] = 1;

        for (int s = 1; s < (1 << n); s++) {
            if (f[s] == 0)
                continue;

            int tot = 0;
            for (int i = 0; i < n; i++)
                if (s & (1 << i))
                    tot++;

            for (int i = 0; i < n; i++)
                if (!(s & (1 << i)) &&
                ((tot + 1) % (i + 1) == 0 || (i + 1) % (tot + 1) == 0))
                    f[s | 1 << i] += f[s];
        }

        return f[(1 << n) - 1];         
    }
};