Description

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

  • \(perm[i]\) 能够被 \(i\) 整除
  • \(i\) 能够被 \(perm[i]\) 整除

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

Constraints

\(1 \le n \le 15\)

Solution

状压DP,用\(dp[S]\)表示数字的选取情况

就凭感觉写的方案数,我也不知道为啥能AC

Code

class Solution {
public:
    int countArrangement(int n) {
        int dp[1<<15];
        memset(dp, 0, sizeof dp);
        dp[0] = 1;
        for(int i = 1; i < (1<<n); ++i) {
            int cnt = 0;
            for(int t = i; t; t -= t&-t) cnt++;
            for(int j = 0; j < n; ++j) {
                if((i>>j & 1) && ((j+1) % cnt == 0 || cnt % (j+1) == 0)) {
                    dp[i] += dp[i^(1<<j)];
                }
            }
        }
        return dp[(1<<n)-1];
    }
};

LeetCode-526 Beautiful Arrangement