「UVa 11806」Cheerleaders - 组合数 + 容斥原理

在一个 M * N 的矩阵中摆放 K 只石子,要求第一行、第一列、第 M 行、第 N 列必须有石子,求方案总数。

链接

UVa 11806

题解

  1. A C 分别表示第一行、第 M 没有摆放石子的方案集合;
  2. B D 分别表示第一列、第 N 没有摆放石子的方案集合;
  3. S 表示在 M * N 的矩阵中任意摆放 K 只石子的方案集合。

则问题转化为,求在集合 S 内但不在集合 A B C D 内的元素总数。

由容斥原理得,答案

\begin{align*} & = |S| \\ & - |A| - |B| - |C| - |D| \\ & + |A{\cup}B| + |B{\cup}C| + |C{\cup}D| + |D{\cup}A| + |A{\cup}C| + |B{\cup}D| \\ & - |A{\cup}B{\cup}C| - |B{\cup}C{\cup}D| - |A{\cup}C{\cup}D| - |A{\cup}B{\cup}D| \\ & + |A{\cup}B{\cup}C{\cup}D| \\ \end{align*}

各个集合的元素数量可用组合数计算,组合数需要预处理。

代码

#include <cstdio>
#include <climits>

const int MAXT = 50;
const int MAXN = 20;
const int MAXK = 500;
const int p = 1000007;

int combo[MAXK + 1][MAXK + 1];

inline void makeComboTable() {
    for (int i = 0; i <= MAXK; i++) {
        combo[i][0] = combo[i][i] = 1;
        for (int j = 1; j < i; j++) {
            combo[i][j] = (combo[i - 1][j] + combo[i - 
1][j - 1]) % p;
        }
    }
}

inline long long C(int a, int b) {
    return (long long)combo[a][b];
}

inline int solve(int m, int n, int k) {
    long long ans = C(m * n, k);

    // |A| = |C| = C(m(n - 1), k)
    // |B| = |D| = C((m - 1)n, k)
    ans -= C(m * (n - 1), k), ans += p, ans %= p;
    ans -= C(m * (n - 1), k), ans += p, ans %= p;
    ans -= C((m - 1) * n, k), ans += p, ans %= p;
    ans -= C((m - 1) * n, k), ans += p, ans %= p;

    // |AB| = |BC| = |CD| = |DA| = C((m - 1)(n - 1), k)
    // |AC| = C(m(n - 2), k)
    // |BD| = C((m - 2)n, k)
    ans += C((m - 1) * (n - 1), k), ans %= p;
    ans += C((m - 1) * (n - 1), k), ans %= p;
    ans += C((m - 1) * (n - 1), k), ans %= p;
    ans += C((m - 1) * (n - 1), k), ans %= p;
    ans += C(m * (n - 2), k), ans %= p;
    ans += C((m - 2) * n, k), ans %= p;

    // |ABC| = |ADC| = C((m - 1)(n - 2), k)
    // |ABD| = |CBD| = C((m - 2)(n - 1), k)
    ans -= C((m - 1) * (n - 2), k), ans += p, ans %= p;
    ans -= C((m - 1) * (n - 2), k), ans += p, ans %= p;
    ans -= C((m - 2) * (n - 1), k), ans += p, ans %= p;
    ans -= C((m - 2) * (n - 1), k), ans += p, ans %= p;

    // |ABCD| = C((m - 2)(n - 2), k);
    ans += C((m - 2) * (n - 2), k), ans %= p;

    return ans;
}

int main() {
    makeComboTable();

    int t;
    scanf("%d", &t);

    for (int i = 1; i <= t; i++) {
        int n, m, k;
        scanf("%d %d %d", &m, &n, &k);
        printf("Case %d: %d\n", i, solve(m, n, k));
    }

    return 0;
}