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];
    }
};

Link

LeetCode-526 Beautiful Arrangement