AtCoder 🟢 AT_dp_o Matching

題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 🟢 AT_dp_o Matching

Problem Statement

題目簡述

有 $N$ 位男性與 $N$ 位女性，給定相容性矩陣 $a_{i,j}$，其中 $a_{i,j} = 1$ 表示男性 $i$ 與女性 $j$ 相容。求將所有男女配成 $N$ 對（每人恰屬一對）的方案數，答案對 $10^9+7$ 取模。

Constraints

約束條件

• $1 \le N \le 21$
• $a_{i,j} \in \{0, 1\}$

---

思路：狀態壓縮 DP

問題分析

本題本質上是求二分圖完美匹配的計數問題。若使用暴力枚舉所有排列，時間複雜度為 $O(N!)$，對於 $N = 21$ 是無法接受的。

注意到 $N \le 21$，可以使用 Bitmask DP 來優化：用一個集合 $S \subseteq \{1, 2, \ldots, N\}$ 來表示哪些女性已經被分配（實作時以 $N$ 位的 bitmask 儲存）。

方法一：記憶化搜索

狀態定義

定義 $\text{dfs}(S)$ 為：集合 $S$ 中的女性已被前 $|S|$ 位男性匹配時，剩餘男女完成配對的方案數。

• 邊界條件：當 $|S| = N$ 時，所有人已配對，返回 $1$。
• 遞迴轉移：對於第 $i = |S|$ 位男性，枚舉所有相容且未配對的女性 $j \notin S$，累加 $\text{dfs}(S \cup \{j\})$。
• 答案：$\text{dfs}(\emptyset)$

Python 實作限制

使用 @cache 裝飾器的遞迴版本會遇到遞迴深度限制與雜湊效率較低的問題，無法通過本題。可將遞迴改寫為顯式堆疊模擬，避免遞迴深度問題。

複雜度分析

• 時間複雜度：$\mathcal{O}(N \cdot 2^N)$，共有 $2^N$ 個狀態，每個狀態需枚舉 $O(N)$ 位女性。
• 空間複雜度：$\mathcal{O}(2^N)$，記憶化需儲存所有狀態的結果。

---

方法二：遞推 DP

狀態定義

設 $f[S]$ 為：當前已考慮前 $|S|$ 位男性，且集合 $S$ 中的女性已被匹配時，到達此狀態的配對方案數。

兩種方法的狀態定義差異

• 方法一：$\text{dfs}(S)$ 計算的是從狀態 $S$ 往後完成配對的方案數（後綴計數）。
• 方法二：$f[S]$ 計算的是從初始狀態 $\emptyset$ 到達 $S$ 的方案數（前綴計數）。

兩者本質相同，只是計數方向相反。遞推適合從小狀態逐步推向大狀態。

關鍵觀察

由於男性是依序考慮的，當我們處理第 $i$ 位男性時，$|S| = i$（代表前 $i$ 個男性各自匹配了一位女性）。因此 不需要額外維度記錄當前處理到第幾位男性，只需透過 $|S|$ 即可隱式推算。

轉移方程

對於第 $i$ 位男性（$i = |S|$），枚舉所有尚未配對且相容的女性 $j \notin S$：

$$f[S \cup \{j\}] \xleftarrow{a_{i,j} = 1} f[S]$$

初始與答案

• 初始狀態：$f[\emptyset] = 1$（無人配對，唯一的「空」方案）
• 最終答案：$f[\{1, 2, \ldots, N\}]$（所有女性皆已配對）

複雜度分析

• 時間複雜度：$\mathcal{O}(N \cdot 2^N)$，外層遍歷 $N$ 位男性，每位男性需遍歷當前有效狀態（最多 $\binom{N}{i}$ 個）並嘗試 $N$ 位女性。
• 空間複雜度：$\mathcal{O}(2^N)$，需儲存所有可能的集合狀態。由於處理第 $i$ 位男性時，只需保留 $|S| = i$ 的狀態（共 $\binom{N}{i}$ 個），使用滾動陣列可將空間優化為 $O(\binom{N}{\lfloor N/2 \rfloor})$。

---

Code

方法一：記憶化搜索

from functools import cache

MOD = int(1e9 + 7)

def solve():
    N = int(input())
    grid = [list(map(int, input().split())) for _ in range(N)]

    """1. 使用 @cache 裝飾器實現記憶化搜索，但會有遞歸深度限制以及雜湊效率較低的問題"""
    # @cache
    # def dfs(msk: int) -> int:
    #     i = msk.bit_count()
    #     if i == N:
    #         return 1
    #     res = 0
    #     for j in range(N):
    #         if msk & (1 << j) or grid[i][j] == 0:
    #             continue
    #         res = (res + dfs(msk | (1 << j))) % MOD
    #     return res
    # print(dfs(0))

    """2. 將 DFS 轉換成 Stack 實現記憶化搜索"""
    U = 1 << N
    f = [-1] * U
    st = [(0, 0)]  # (msk, flag)
    while st:
        msk, flag = st.pop()
        i = msk.bit_count()
        if f[msk] != -1:
            continue
        if i == N:
            f[msk] = 1
            continue
        if flag == 0:
            st.append((msk, 1))
            for j in range(N):
                if msk & (1 << j) or grid[i][j] == 0:
                    continue
                st.append((msk | (1 << j), 0))
        else:
            res = 0
            for j in range(N):
                if msk & (1 << j) or grid[i][j] == 0:
                    continue
                res = (res + f[msk | (1 << j)]) % MOD
            f[msk] = res
            continue
    print(f[0])

if __name__ == "__main__":
    solve()

方法二：遞推 DP

from collections import defaultdict

MOD = int(1e9 + 7)

def solve():
    N = int(input())
    grid = [list(map(int, input().split())) for _ in range(N)]

    U = 1 << N
    f = defaultdict(int)
    f[0] = 1
    for i in range(N):
        nf = defaultdict(int)
        for msk, val in f.items():
            for j in range(N):
                if msk & (1 << j) or grid[i][j] == 0:
                    continue
                nf[msk | (1 << j)] += val
                nf[msk | (1 << j)] %= MOD
        f = nf
    print(f[U - 1])

if __name__ == "__main__":
    solve()