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

发表于 | 分类于

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

链接

UVa 11806

题解

  1. 设 、 分别表示第一行、第 行没有摆放石子的方案集合；
  2. 设 、 分别表示第一列、第 列没有摆放石子的方案集合；
  3. 设 表示在 的矩阵中任意摆放 只石子的方案集合。

则问题转化为，求在集合 内但不在集合 、、、 内的元素总数。

由容斥原理得，答案

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

代码

#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;
}