HDU 4832 Chess

思路：把行列的情况分别dp求出来，然后枚举行用几行，竖用几行。然后相乘累加起来就是答案

代码：

#include <stdio.h>

#include <string.h>

#include <iostream>

using namespace std;

typedef long long ll;

const ll MOD = 9999991;

const int N = 1005;

int t, n, m, k, x, y;

ll dp1[N][N], dp2[N][N], C[N][N];

int main() {

    for (int i = 0; i <= 1000; 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;

    }

    }

    int cas = 0;

    scanf("%d", &t);

    while (t--) {

    scanf("%d%d%d%d%d", &n, &m, &k, &x, &y);

    memset(dp1, 0, sizeof(dp1));

    memset(dp2, 0, sizeof(dp2));

    dp1[0][x] = dp2[0][y] = 1;

    for (int i = 1; i <= k; i++) {

        for (int j = 1; j <= n; j++) {

        if (j >= 2)

            dp1[i][j] = (dp1[i][j] + dp1[i - 1][j - 2]) % MOD;

        if (j >= 1)

            dp1[i][j] = (dp1[i][j] + dp1[i - 1][j - 1]) % MOD;

        dp1[i][j] = (dp1[i][j] + dp1[i - 1][j + 1]) % MOD;

        dp1[i][j] = (dp1[i][j] + dp1[i - 1][j + 2]) % MOD;

        }

    }

    for (int i = 1; i <= k; i++) {

        for (int j = 1; j <= m; j++) {

        if (j >= 2)

            dp2[i][j] = (dp2[i][j] + dp2[i - 1][j - 2]) % MOD;

        if (j >= 1)

            dp2[i][j] = (dp2[i][j] + dp2[i - 1][j - 1]) % MOD;

        dp2[i][j] = (dp2[i][j] + dp2[i - 1][j + 1]) % MOD;

        dp2[i][j] = (dp2[i][j] + dp2[i - 1][j + 2]) % MOD;

        }

    }

    ll heng[N], shu[N];

    memset(heng, 0, sizeof(heng));

    memset(shu, 0, sizeof(shu));

    for (int i = 1; i <= n; i++)

        for (int kk = 0; kk <= k; kk++)

        heng[kk] = (heng[kk] + dp1[kk][i]) % MOD;

    for (int i = 1; i <= m; i++)

        for (int kk = 0; kk <= k; kk++)

        shu[kk] = (shu[kk] + dp2[kk][i]) % MOD;

    ll ans = 0;

    for (int i = 0; i <= k; i++) {

        ans = (ans + (heng[i] * shu[k - i] % MOD) * C[k][i] % MOD) % MOD;

    }

    printf("Case #%d:\n", ++cas);

    cout << ans << endl;

    }

    return 0;

}