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