特别的排列

6893. 特别的排列

给你一个下标从 0 开始的整数数组 nums ，它包含 n 个 互不相同 的正整数。如果 nums 的一个排列满足以下条件，我们称它是一个特别的排列：

对于 0 <= i < n - 1 的下标 i ，要么 nums[i] % nums[i+1] == 0 ，要么 nums[i+1] % nums[i] == 0 。

请你返回特别排列的总数目，由于答案可能很大，请将它对 10⁹+ 7 取余后返回。

示例 1：

输入：nums = [2,3,6]
输出：2
解释：[3,6,2] 和 [2,6,3] 是 nums 两个特别的排列。

示例 2：

输入：nums = [1,4,3]
输出：2
解释：[3,1,4] 和 [4,1,3] 是 nums 两个特别的排列。

提示：

2 <= nums.length <= 14
1 <= nums[i] <= 10⁹

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int specialPerm(vector<int>& nums) { } };

cpp 解法, 执行用时: 383 ms, 内存消耗: 197.2 MB, 提交时间: 2024-06-27 22:29:30

class Solution {
public:
    int specialPerm(vector<int>& nums) {
        int n = nums.size(), u = (1 << n) - 1;
        vector<vector<long long>> memo(u, vector<long long>(n, -1)); // -1 表示没有计算过
        auto dfs = [&](auto&& dfs, int s, int i) -> long long {
            if (s == 0) {
                return 1; // 找到一个特别排列
            }
            auto& res = memo[s][i]; // 注意这里是引用
            if (res != -1) { // 之前计算过
                return res;
            }
            res = 0;
            for (int j = 0; j < n; j++) {
                if ((s >> j & 1) && (nums[i] % nums[j] == 0 || nums[j] % nums[i] == 0)) {
                    res += dfs(dfs, s ^ (1 << j), j);
                }
            }
            return res;
        };
        long long ans = 0;
        for (int i = 0; i < n; i++) {
            ans += dfs(dfs, u ^ (1 << i), i);
        }
        return ans % 1'000'000'007;
    }
};

cpp 解法, 执行用时: 671 ms, 内存消耗: 197 MB, 提交时间: 2024-06-27 22:29:20

class Solution {
public:
    int specialPerm(vector<int>& nums) {
        int n = nums.size(), u = (1 << n) - 1;
        vector<vector<long long>> f(u, vector<long long>(n));
        ranges::fill(f[0], 1LL);
        for (int s = 1; s < u; s++) {
            for (int i = 0; i < n; i++) {
                if (s >> i & 1) {
                    continue;
                }
                for (int j = 0; j < n; j++) {
                    if ((s >> j & 1) && (nums[i] % nums[j] == 0 || nums[j] % nums[i] == 0)) {
                        f[s][i] += f[s ^ (1 << j)][j];
                    }
                }
            }
        }
        long long ans = 0;
        for (int i = 0; i < n; i++) {
            ans += f[u ^ (1 << i)][i];
        }
        return ans % 1'000'000'007;
    }
};

java 解法, 执行用时: 364 ms, 内存消耗: 53.7 MB, 提交时间: 2024-06-27 22:29:04

public class Solution {
    public int specialPerm(int[] nums) {
        int n = nums.length;
        int u = (1 << n) - 1;
        long[][] f = new long[u][n];
        Arrays.fill(f[0], 1L);
        for (int s = 1; s < u; s++) {
            for (int i = 0; i < n; i++) {
                if ((s >> i & 1) != 0) {
                    continue;
                }
                for (int j = 0; j < n; j++) {
                    if ((s >> j & 1) != 0 && (nums[i] % nums[j] == 0 || nums[j] % nums[i] == 0)) {
                        f[s][i] += f[s ^ (1 << j)][j];
                    }
                }
            }
        }
        long ans = 0;
        for (int i = 0; i < n; i++) {
            ans += f[u ^ (1 << i)][i];
        }
        return (int) (ans % 1_000_000_007);
    }
}

java 解法, 执行用时: 161 ms, 内存消耗: 53.8 MB, 提交时间: 2024-06-27 22:28:54

public class Solution {
    public int specialPerm(int[] nums) {
        int n = nums.length;
        int u = (1 << n) - 1;
        long[][] memo = new long[u][n];
        for (long[] row : memo) {
            Arrays.fill(row, -1); // -1 表示没有计算过
        }
        long ans = 0;
        for (int i = 0; i < n; i++) {
            ans += dfs(u ^ (1 << i), i, nums, memo);
        }
        return (int) (ans % 1_000_000_007);
    }

    private long dfs(int s, int i, int[] nums, long[][] memo) {
        if (s == 0) {
            return 1; // 找到一个特别排列
        }
        if (memo[s][i] != -1) { // 之前计算过
            return memo[s][i];
        }
        long res = 0;
        for (int j = 0; j < nums.length; j++) {
            if ((s >> j & 1) > 0 && (nums[i] % nums[j] == 0 || nums[j] % nums[i] == 0)) {
                res += dfs(s ^ (1 << j), j, nums, memo);
            }
        }
        return memo[s][i] = res; // 记忆化
    }
}

golang 解法, 执行用时: 784 ms, 内存消耗: 7.4 MB, 提交时间: 2023-06-19 09:45:49

// 递推
func specialPerm(nums []int) (ans int) {
	const mod int = 1e9 + 7
	n := len(nums)
	m := 1 << n
	f := make([][]int, m)
	f[0] = make([]int, n)
	for j := range f[0] {
		f[0][j] = 1
	}
	for i := 1; i < m; i++ {
		f[i] = make([]int, n)
		for j, x := range nums {
			for k, y := range nums {
				if i>>k&1 > 0 && (x%y == 0 || y%x == 0) {
					f[i][j] = (f[i][j] + f[i^(1<<k)][k]) % mod
				}
			}
		}
	}
	for j := range nums {
		ans = (ans + f[(m-1)^(1<<j)][j]) % mod
	}
	return
}

golang 解法, 执行用时: 232 ms, 内存消耗: 7.2 MB, 提交时间: 2023-06-19 09:45:27

func specialPerm(nums []int) (ans int) {
	const mod int = 1e9 + 7
	n := len(nums)
	m := 1 << n
	memo := make([][]int, m)
	for i := range memo {
		memo[i] = make([]int, n)
		for j := range memo[i] {
			memo[i][j] = -1
		}
	}
	var dfs func(int, int) int
	dfs = func(i, j int) (res int) {
		if i == 0 {
			return 1 // 找到一个特别排列
		}
		p := &memo[i][j]
		if *p != -1 {
			return *p
		}
		for k, x := range nums {
			if i>>k&1 > 0 && (nums[j]%x == 0 || x%nums[j] == 0) {
				res = (res + dfs(i^(1<<k), k)) % mod
			}
		}
		*p = res
		return
	}
	for j := range nums {
		ans = (ans + dfs((m-1)^(1<<j), j)) % mod
	}
	return
}

python3 解法, 执行用时: 3660 ms, 内存消耗: 213.2 MB, 提交时间: 2023-06-19 09:43:14

'''
状态压缩dp
dfs(i, j) 表示当前可选的下表集合为i, 上一个选的数的下标是j时，可构造出多少个特别排列。
'''
class Solution:
    def specialPerm(self, nums: List[int]) -> int:
        MOD = 10 ** 9 + 7
        @cache
        def dfs(i: int, j: int) -> int:
            if i == 0: return 1  # 找到一个特别排列
            res = 0
            for k, x in enumerate(nums):
                if i >> k & 1 and (nums[j] % x == 0 or x % nums[j] == 0):
                    res += dfs(i ^ (1 << k), k)
            return res % MOD
        n = len(nums)
        return sum(dfs(((1 << n) - 1) ^ (1 << j), j) for j in range(n)) % MOD

上一题

下一题

详情