🔗 🟡 2741. Special Permutations 2021

tags: `Weekly Contest 350` `狀態壓縮(Bitmask)` `動態規劃(DP)` `位運算(Bit Manipulation)` `狀壓DP`

題意

給定一個包含 $n$ 個不同正整數的整數陣列 $nums$ ，下標從 $0$ 開始。如果 $nums$ 的一個排列 $\text{perm}$ 滿足以下條件，則稱其為特殊排列：

對於 $0 \leq i < n - 1$ 的下標 $i$ ，滿足 $\text{perm}[i] \bmod \text{perm}[i+1] = 0 \lor \text{perm}[i+1] \bmod \text{perm}[i] = 0$ 。

返回特殊排列的總數量，由於答案可能很大，請將其對 $10^9 + 7$ 取模後返回。

約束條件

$2 \leq n \leq 14$
$1 \leq \text{nums}[i] \leq 10^9$

思路：狀壓 DP ：排列型－相鄰相關

令 $dfs(S, i)$ 表示當前已選擇的集合為 $S$ ，且最後一個選擇的數字是 $nums[i]$ 時，滿足條件的特殊排列的數量。則我們可以得到狀態轉移方程：

$dfs(S, i) = \displaystyle\sum_{j=0}^{n-1} dfs(S \cup \{j\}, j)$ $df s (S, i) = j = 0 \sum n - 1 df s (S \cup {j}, j)$ ，其中 $j$ $j$ 是下一個選擇的數字的下標。
- 需滿足 $j \notin S$ 且 $nums[i] \bmod nums[j] = 0 \lor nums[j] \bmod nums[i] = 0$ 。
遞迴終點為 $S = U$ ，即所有數字都已經被選擇，其中 $U$ 為 宇集合(Universal Set) 。

而注意到 $|S| = n \leq 14$ ，因此我們可以使用一個 $14$ 位的二進制數字來表示 $S$ ，其中第 $i$ 位為 $1$ 表示 $i$ 已經被選擇，為 $0$ 表示未被選擇，狀態壓縮成一個整數，並將集合的運算轉換為位運算(Bit Manipulation)。

由於添加到集合的操作會使該位從 $0$ 變為 $1$ ，因此可以使用 $s | (1 << j)$ 來表示添加 $j$ 到 $S$ 中。
宇集合 $U$ 可以表示為 $u = (1 << n) - 1$ 。

由於會存在一些重複的子問題，因此我們可以使用動態規劃(DP) 來避免重複計算，這裡使用了 Top-Down 的方式進行遞迴計算，並使用記憶化搜尋(Memoization) 來保存已經計算過的結果。

初始化時可以考慮第一個選擇的數字，即 $dfs(1 << i, i)$ ，其中 $i$ 是 $nums$ 的下標，將其所有的結果相加即為答案。

複雜度分析

時間複雜度： $\mathcal{O}(n^2 \cdot 2^n)$ ，其中 $n$ 是 $nums$ 的長度。總共有 $n \cdot 2^n$ 種狀態，每種狀態需要 $\mathcal{O}(n)$ 的時間進行轉移計算。
空間複雜度： $\mathcal{O}(n \cdot 2^n)$ ，即狀態數量。

class Solution:
    def specialPerm(self, nums: List[int]) -> int:
        MOD = 10 ** 9 + 7
        n = len(nums)
        u = (1 << n) - 1 # 全部選擇

        @cache
        def dfs(s: int, i: int) -> int: # s: 已選擇的集合, i: 前一個選擇的 index
            if s == u:
                return 1
            res = 0
            pre = nums[i]
            for j, x in enumerate(nums): # 枚舉下一個選擇的 index
                if (s >> j) & 1: # 已選擇過
                    continue
                if pre % x == 0 or x % pre == 0: # 符合條件
                    res += dfs(s | (1 << j), j)
            return res
        
        return sum(dfs(1 << i, i) % MOD for i in range(n)) % MOD

class Solution {
public:
    const int MOD = 1e9 + 7;
    int specialPerm(vector<int>& nums) {
        int n = nums.size();
        int u = (1 << n) - 1;
        
        vector<vector<int>> memo(1 << n, vector<int>(n, -1));
        function<int(int, int)> dfs = [&](int s, int i) -> int {
            if (s == u) return 1;
            if (memo[s][i] != -1) return memo[s][i];
            int res = 0;
            for (int j = 0; j < n; j++) {
                if ((s >> j) & 1) continue;
                if (nums[i] % nums[j] == 0 || nums[j] % nums[i] == 0) {
                    res = (res + dfs(s | (1 << j), j)) % MOD;
                }
            }
            return memo[s][i] = res;
        };

        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans = (ans + dfs(1 << i, i)) % MOD;
        }
        return ans;
    }
};