HDU 5155 Harry And Magic Box：容斥原理計算矩陣填數方案數

問題重述

n×m 矩陣每格放 0/1，要求每行至少一個 1，每列至少一個 1。求方案數模 1e9+7。n,m ≤ 50。

容斥推導

先保證每行有 1。枚舉有 i 列全為 0（C(m,i) 選法），剩餘 m-i 列每行可任意填但不全 0，即 (2^{m-i}-1) 種/行，n 行共 (2^{m-i}-1)^n。容斥原理：

Ans = Σ_{i=0}^{m} (-1)^i * C(m,i) * (2^{m-i}-1)^n

代碼實現

• 預處理組合數 C[n][k] (n≤50)。
• 快速冪計算 (2^{m-i}-1)^n mod MOD。
• 按奇偶累加/減，注意取模非負。

動態規劃替代視角

dp[i][j] 表示前 i 行恰有 j 列出現過 1 的方案數。轉移枚舉第 i 行新增 k 列 1，組合數選列。最終 dp[n][m] 即答案。雖複雜度 O(n m³) 但 n,m≤50 也可過。

總結

容斥法將「每行每列至少一 1」轉化為單一條件枚舉，代碼極簡；DP 法提供另一思路，適合條件更複雜時擴展。兩種方法均屬組合數學經典套路。