2992. 自整除排列的数量 🔒
题目描述
给定一个整数 n，返回 下标从 1 开始 的数组 nums = [1, 2, ..., n]的 可能的排列组合数量，使其满足 自整除 条件。
如果对于每个 1 <= i <= n，满足 gcd(a[i], i) == 1，数组 nums 就是 自整除 的。
数组的 排列 是对数组元素的重新排列组合，例如，下面是数组 [1, 2, 3] 的所有排列组合：
[1, 2, 3][1, 3, 2][2, 1, 3][2, 3, 1][3, 1, 2][3, 2, 1]
示例 1：
输入：n = 1 输出：1 解释：数组 [1] 只有一个排列，它是自整除的。
示例 2：
输入：n = 2 输出：1 解释：数组 [1,2] 有 2 个排列，但只有其中一个是自整除的： nums = [1,2]：这不是自整除的，因为 gcd(nums[2], 2) != 1。 nums = [2,1]：这是自整除的，因为 gcd(nums[1], 1) == 1 并且 gcd(nums[2], 2) == 1。
示例 3：
输入：n = 3 输出：3 解释：数组 [1,2,3] 有 3 个自整除的排列：[1,2,3]、[2,1,3]、[3,2,1]。 其他 3 个排列不能满足自整除条件。因此答案是 3。
提示：
1 <= n <= 12
解法
方法一：状态压缩 + 记忆化搜索
我们可以用一个二进制数 $mask$ 来表示当前排列的状态，其中第 $i$ 位为 $1$ 表示数字 $i$ 已经被使用，为 $0$ 表示数字 $i$ 还未被使用。
那么，我们设计一个函数 $dfs(mask)$，表示从当前排列的状态 $mask$ 开始，能够构造出的满足题目要求的排列的数量。答案即为 $dfs(0)$。
我们可以用记忆化搜索的方法来计算 $dfs(mask)$ 的值。
在计算 $dfs(mask)$ 的过程中，我们用 $i$ 表示当前要加入排列的是第几个数字，如果 $i \gt n$，说明排列已经构造完毕，我们可以返回 $1$。
否则，我们枚举当前排列中还未被使用的数字 $j$，如果 $i$ 和 $j$ 满足题目要求，那么我们就可以将 $j$ 加入排列中，此时状态变为 $mask \mid 2^j$，其中 $|$ 表示按位或运算。由于 $j$ 已经被使用，因此我们需要递归计算 $dfs(mask \mid 2^j)$ 的值，并将其累加到 $dfs(mask)$ 上。
最终，我们可以得到 $dfs(0)$ 的值，即为答案。
时间复杂度 $O(n \times 2^n)$，空间复杂度 $O(2^n)$。其中 $n$ 为排列的长度。
Python3
class Solution:
def selfDivisiblePermutationCount(self, n: int) -> int:
@cache
def dfs(mask: int) -> int:
i = mask.bit_count() + 1
if i > n:
return 1
ans = 0
for j in range(1, n + 1):
if (mask >> j & 1) == 0 and gcd(i, j) == 1:
ans += dfs(mask | 1 << j)
return ans
return dfs(0)
Java
class Solution {
private int n;
private Integer[] f;
public int selfDivisiblePermutationCount(int n) {
this.n = n;
f = new Integer[1 << (n + 1)];
return dfs(0);
}
private int dfs(int mask) {
if (f[mask] != null) {
return f[mask];
}
int i = Integer.bitCount(mask) + 1;
if (i > n) {
return 1;
}
f[mask] = 0;
for (int j = 1; j <= n; ++j) {
if ((mask >> j & 1) == 0 && (i % j == 0 || j % i == 0)) {
f[mask] += dfs(mask | 1 << j);
}
}
return f[mask];
}
}
C++
class Solution {
public:
int selfDivisiblePermutationCount(int n) {
int f[1 << (n + 1)];
memset(f, -1, sizeof(f));
function<int(int)> dfs = [&](int mask) {
if (f[mask] != -1) {
return f[mask];
}
int i = __builtin_popcount(mask) + 1;
if (i > n) {
return 1;
}
f[mask] = 0;
for (int j = 1; j <= n; ++j) {
if ((mask >> j & 1) == 0 && (i % j == 0 || j % i == 0)) {
f[mask] += dfs(mask | 1 << j);
}
}
return f[mask];
};
return dfs(0);
}
};
Go
func selfDivisiblePermutationCount(n int) int {
f := make([]int, 1<<(n+1))
for i := range f {
f[i] = -1
}
var dfs func(int) int
dfs = func(mask int) int {
if f[mask] != -1 {
return f[mask]
}
i := bits.OnesCount(uint(mask)) + 1
if i > n {
return 1
}
f[mask] = 0
for j := 1; j <= n; j++ {
if mask>>j&1 == 0 && (i%j == 0 || j%i == 0) {
f[mask] += dfs(mask | 1<<j)
}
}
return f[mask]
}
return dfs(0)
}
TypeScript
function selfDivisiblePermutationCount(n: number): number {
const f: number[] = Array(1 << (n + 1)).fill(-1);
const dfs = (mask: number): number => {
if (f[mask] !== -1) {
return f[mask];
}
const i = bitCount(mask) + 1;
if (i > n) {
return 1;
}
f[mask] = 0;
for (let j = 1; j <= n; ++j) {
if (((mask >> j) & 1) === 0 && (i % j === 0 || j % i === 0)) {
f[mask] += dfs(mask | (1 << j));
}
}
return f[mask];
};
return dfs(0);
}
function bitCount(i: number): number {
i = i - ((i >>> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
i = (i + (i >>> 4)) & 0x0f0f0f0f;
i = i + (i >>> 8);
i = i + (i >>> 16);
return i & 0x3f;
}
方法二：状态压缩 + 动态规划
我们可以将方法一中的记忆化搜索改写为动态规划的形式，定义 $f[mask]$ 表示当前排列的状态为 $mask$，且满足题目要求的排列的数量。初始时 $f[0]=1$，其余值均为 $0$。
我们在 $[0, 2^n)$ 的范围内枚举 $mask$，对于每个 $mask$，我们用 $i$ 表示当前最后一个加入排列的是第几个数字，然后我们枚举当前排列中最后一个加入的数字 $j$，如果 $i$ 和 $j$ 满足题目要求，那么状态 $f[mask]$ 就可以从状态 $f[mask \oplus 2^(j-1)]$ 转移而来，其中 $\oplus$ 表示按位异或运算。我们将所有转移得到的状态 $f[mask \oplus 2^(j-1)]$ 的值累加到 $f[mask]$ 上，即为 $f[mask]$ 的值。
最终，我们可以得到 $f[2^n - 1]$ 的值，即为答案。
时间复杂度 $O(n \times 2^n)$，空间复杂度 $O(2^n)$。其中 $n$ 为排列的长度。
Python3
class Solution:
def selfDivisiblePermutationCount(self, n: int) -> int:
f = [0] * (1 << n)
f[0] = 1
for mask in range(1 << n):
i = mask.bit_count()
for j in range(1, n + 1):
if (mask >> (j - 1) & 1) == 1 and gcd(i, j) == 1:
f[mask] += f[mask ^ (1 << (j - 1))]
return f[-1]
Java
class Solution {
public int selfDivisiblePermutationCount(int n) {
int[] f = new int[1 << n];
f[0] = 1;
for (int mask = 0; mask < 1 << n; ++mask) {
int i = Integer.bitCount(mask);
for (int j = 1; j <= n; ++j) {
if (((mask >> (j - 1)) & 1) == 1 && (i % j == 0 || j % i == 0)) {
f[mask] += f[mask ^ (1 << (j - 1))];
}
}
}
return f[(1 << n) - 1];
}
}
C++
class Solution {
public:
int selfDivisiblePermutationCount(int n) {
int f[1 << n];
memset(f, 0, sizeof(f));
f[0] = 1;
for (int mask = 0; mask < 1 << n; ++mask) {
int i = __builtin_popcount(mask);
for (int j = 1; j <= n; ++j) {
if (((mask >> (j - 1)) & 1) == 1 && (i % j == 0 || j % i == 0)) {
f[mask] += f[mask ^ (1 << (j - 1))];
}
}
}
return f[(1 << n) - 1];
}
};
Go
func selfDivisiblePermutationCount(n int) int {
f := make([]int, 1<<n)
f[0] = 1
for mask := 0; mask < 1<<n; mask++ {
i := bits.OnesCount(uint(mask))
for j := 1; j <= n; j++ {
if mask>>(j-1)&1 == 1 && (i%j == 0 || j%i == 0) {
f[mask] += f[mask^(1<<(j-1))]
}
}
}
return f[(1<<n)-1]
}
TypeScript
function selfDivisiblePermutationCount(n: number): number {
const f: number[] = Array(1 << n).fill(0);
f[0] = 1;
for (let mask = 0; mask < 1 << n; ++mask) {
const i = bitCount(mask);
for (let j = 1; j <= n; ++j) {
if ((mask >> (j - 1)) & 1 && (i % j === 0 || j % i === 0)) {
f[mask] += f[mask ^ (1 << (j - 1))];
}
}
}
return f.at(-1)!;
}
function bitCount(i: number): number {
i = i - ((i >>> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
i = (i + (i >>> 4)) & 0x0f0f0f0f;
i = i + (i >>> 8);
i = i + (i >>> 16);
return i & 0x3f;
}