G - Cheerleaders

题意：
要将k个棋子放到n*m的棋盘上,求要求第一行，第一列，最后一行，最后一列必须要有棋子，问有几种放法。
题解：
一共16种状态，枚举每一种状态进行计算。

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int mod = 1000007;
const int maxn = 510;
int c[maxn][maxn];
int n, m, k;
void init() {
    c[0][0] = 1;
    for (int i = 0; i <= maxn; i++) {
        c[i][0] = c[i][i] = 1;
        for (int j = 0; j < i; j++) {
            c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
        }
    }
}
int main() {
    init();
    int t;
    int cas = 1;
    cin >> t;
    while (t--) {
        int ans = 0;
        cin >> n >> m >> k;
        for (int s = 0; s < 16; s++) {
            int a = n;
            int b = m;
            int cnt = 0;
            if (s&(1 << 0)) {
                a--;
                cnt++;
            }
            if (s&(1 << 1)) {
                a--;
                cnt++;
            }
            if (s&(1 << 2)) {
                b--;
                cnt++;
            }
            if (s&(1 << 3)) {
                b--;
                cnt++;
            }
            if (cnt % 2)
                ans = (ans + mod - c[a * b][k]) % mod;
            else
                ans = (ans + c[a * b][k]) % mod;
        }
        cout << "Case " << cas++<<": " << ans << endl;
    }
    return 0;
}

H - Arrange the Numbers

题意：
n个数中刚好固定前m个数中的k个数的位置，问你有多少中排列方案。
题解：
利用错排的思想计算剩下的数的排列方案数

#include<iostream>
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
int n, m, k;
ll c[1010][1010], d[1010];
void init() {
    c[0][0] = 1;
    c[1][0] = c[1][1] = 1;
    for (int i = 2; i < 1010; i++) {
        c[i][0] = c[i][i] = 1;
        for (int j = 1; j < i; j++) {
            c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;
        }
    }
    d[0] = 1;
    d[1] = 0;
    d[2] = 1;
    for (int i = 3; i < 1010; i++) {
        d[i] = (i - 1) * (d[i - 1] + d[i - 2]) % mod;
    }
}
ll solve() {
    ll ans = 0;
    for (int i = 0; i <= n - m; i++) {
        ans += c[n - m][i] * d[n - k - i] % mod;
        ans %= mod;
    }
    return c[m][k] * ans % mod;
}
int main() {
    int cas;
    init();
    cin >> cas;
    for (int c = 1; c <= cas; c++) {
        cin >> n >> m >> k;
        cout << "Case " << c << ": " << solve() << endl;
    }
    return 0;
}