UVA 11806 Cheerleaders：容斥原理計算矩陣邊界放石子方案數

問題描述

在 n×m 矩陣中放 k 個石子（每格至多一個），要求**第一行、最後一行、第一列、最後一列**每行/列至少有一個石子。求方案數模 1,000,007。

容斥原理建模

設四個「違反條件」的集合：
A：第一行無石子；B：最後一行無石子；
C：第一列無石子；D：最後一列無石子。
合法方案 = 總方案 - |A∪B∪C∪D|。
用容斥原理計算並集大小：

|A∪B∪C∪D| = Σ|單個| - Σ|雙個交| + Σ|三個交| - |四個交|

計算交集大小

選定某些行/列為「禁區」後，可用格子數為 `(n - r) * (m - c)`，其中 `r` 為禁用行數，`c` 為禁用列數。
從中選 k 個石子的方案數為 `C((n-r)*(m-c), k)`。
預處理組合數 `C[n][k]` (n ≤ 500) 模 MOD。

代碼實現

#include 
#include 
const int MOD = 1000007;
const int MAXN = 505;
int C[MAXN][MAXN];

int main() {
    // 組合數預處理
    C[0][0] = 1;
    for (int i = 1; i <= 500; ++i) {
        C[i][0] = C[i][i] = 1;
        for (int j = 1; j < i; ++j)
            C[i][j] = (C[i-1][j] + C[i-1][j-1]) % MOD;
    }
    int T; scanf("%d", &T);
    for (int cs = 1; cs <= T; ++cs) {
        int n, m, k; scanf("%d%d%d", &n, &m, &k);
        int ans = 0;
        // 枚舉 4 個集合的包含情況 (0..15)
        for (int s = 0; s < 16; ++s) {
            int r = n, c = m, bits = 0;
            if (s & 1) { r--; bits++; } // 第一行
            if (s & 2) { r--; bits++; } // 最後一行
            if (s & 4) { c--; bits++; } // 第一列
            if (s & 8) { c--; bits++; } // 最後一列
            int ways = C[r * c][k];
            if (bits & 1) ans = (ans - ways + MOD) % MOD; // 奇數個集合：減
            else ans = (ans + ways) % MOD;                // 偶數個集合：加
        }
        printf("Case %d: %d\n", cs, ans);
    }
    return 0;
}

複雜度

預處理 O(500²)，每測試用例 O(16) = O(1)。極快。

總結

矩陣邊界約束問題，通過容斥原理轉化為枚舉 4 個禁用行/列組合（16 種），利用預處理組合數 O(1) 計算。位掩碼枚舉子集是容斥實現的標準技巧。