UVA11806 Cheerleaders 题解

题目链接：UVA11806 Cheerleaders

题意：

你有一个\(n \times m\) 的网格图，现在你要将 \(k\) 个人放在网格中，满足一下条件：

1. 网格图的四个边都至少有一个人。
2. 每个格子上不能有两个人。
3. 每个人必须都有位置。
4. 四个角的人可以同时算作在两个边上。

求合法方案数。

输入格式：

The first line of input contains a positive integer \(T \leq 50\), which denotes the number of test cases. \(T\) lines then follow each describing one test case. Each case consists of three nonnegative integers, \(2 \leq M,N \leq 20\) and \(K \leq 500\). Here \(M\) is the number of rows and \(N\) is the number of columns in the grid. \(K\) denotes the number of cheerleaders that must be assigned to the cells in the grid.

输出格式：

For each case of input, there will be one line of output. It will first contain the case number followed by the number of ways to place the cheerleaders as described earlier. Look at the sample output for exact formatting. Note that, the numbers can be arbitrarily large. Therefore you must output the answers modulo \(1000007\).

考虑容斥。设 \(A,B,C,D\) 分别表示 正一行、负一行、正一列、负一列。然后就是朴素的组合数了。

时间复杂度 \(\mathcal{O}(nmk+16T)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define popc(x) __builtin_popcountll(x)
const int mod = 1e6 + 7;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
void add(int &x,int y) { (x += y) >= mod ? x -= mod : 0; }
#define N ((int)(555))

int q,C[N][N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    for(int i = 0; i <= N - 10; i++) C[i][0] = 1;
    for(int i = 1; i <= N - 10; i++)
        for(int j = 1; j <= i; j++) add(C[i][j] = C[i - 1][j - 1], C[i - 1][j]);
    cin >> q;
    for(int i = 1, n,m,k,res; i <= q; i++)
    {
        res = 0; cin >> n >> m >> k;
        for(int S = 0; S < 16; S++)
        {
            int cnt = popc(S), r = n, c = m;
            (S & 1) && (--r), (S & 2) && (--r);
            (S & 4) && (--c), (S & 8) && (--c);
            add(res, (cnt & 1) ? mod - C[r * c][k] : C[r * c][k]);
        }
        cout << "Case " << i << ": " << res << '\n';
    }
    return 0;
}