您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> C++ 入門

UVA 11806 - Cheerleaders：數論與容斥原理解題詳解

編輯：C++ 入門

題目連結：UVA 11806 - Cheerleaders

這道題目要求在一個棋盤上擺放旗子，使得四周的四行都至少有一面旗子，我們需要計算總共有多少種合法的擺放方法。

核心思路：容斥原理

直接計算滿足條件的方案數容易遺漏或重複，因此我們採用容斥原理來轉化問題。設四條邊分別為集合 A、B、C、D，表示該邊沒有旗子的情況。根據容斥原理：

合法方案數 = 總方案數 - |A ∪ B ∪ C ∪ D|

其中聯集的計算公式為：

|A ∪ B ∪ C ∪ D| = Σ|單個集合| - Σ|兩兩交集| + Σ|三三交集| - |四個交集|

位運算枚舉子集

利用 4 位二進制數（0 到 15）分別代表四條邊是否被選入「無旗子」集合。對於每個狀態 s：

統計被選中的邊數 count
根據被選中的邊，減少可用的行數 r 和列數 c
剩餘格子數為 r * c，從中選 k 個放旗子的方案數為 C(r*c, k)
若 count 為奇數則減去，偶數則加上（容斥原理符號）

預處理組合數

由於模數 MOD = 1,000,007 非質數，但 n, m ≤ 500，故 r*c ≤ 250,000，可用帕斯卡三角形遞推預處理所有 C[n][k] mod MOD。

完整代碼（C 語言）

#include <stdio.h>
#include <string.h>

const int MOD = 1000007;
const int N = 505;
int C[N][N];

int main() {
    // 預處理組合數
    C[0][0] = 1;
    for (int i = 1; i < N; 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 cas = 1; cas <= T; cas++) {
        int n, m, k; scanf("%d%d%d", &n, &m, &k);
        int ans = 0;

        // 枚舉 16 種邊的選取狀態
        for (int s = 0; s < 16; s++) {
            int cnt = 0, r = n, c = m;
            if (s & 1) { cnt++; r--; }      // 上邊
            if (s & 2) { cnt++; r--; }      // 下邊
            if (s & 4) { cnt++; c--; }      // 左邊
            if (s & 8) { cnt++; c--; }      // 右邊

            int ways = C[r * c][k];
            if (cnt & 1) ans = (ans - ways + MOD) % MOD;
            else         ans = (ans + ways) % MOD;
        }
        printf("Case %d: %d\n", cas, ans);
    }
    return 0;
}