11806 Cheerleaders

程式碼

// author: Piau
#include <bits/stdc++.h>
using namespace std;

#define WA() cin.tie(0)->sync_with_stdio(0)
#define all(x) (x).begin(), (x).end()
#define int long long

int N = 501, P = 1e6 + 7;

signed main() {
    WA();
    vector<vector<int>> C(N, vector<int>(N));
    for (int i = 0, j; i < N; i++) {
        for (C[i][0] = C[i][i] = 1, j = 1; j < i; j++) {
            C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % P;
        }
    }
    int t, T = 0;
    for (cin >> t; t--;) {
        int n, m, k;
        cin >> n >> m >> k;
        cout << "Case " << ++T << ": ";
        cout << ((C[m * n][k] - 2 * C[(m - 1) * n][k] - 2 * C[m * (n - 1)][k] +
                  C[(m - 2) * n][k] + C[m * (n - 2)][k] +
                  4 * C[(m - 1) * (n - 1)][k] - 2 * C[(m - 2) * (n - 1)][k] -
                  2 * C[(m - 1) * (n - 2)][k] + C[(m - 2) * (n - 2)][k]) %
                     P +
                 P) %
                    P
             << '\n';
    }
}