[AHOI2009] 中国象棋

大意

给定 $n$ 行， $m$ 列的格子，可以涂黑，求每行每列涂黑不超过 $2$ 个的方案数。

题解

设 $f(i, j, k)$ 为考虑了前 $i$ 行，有 $j$ 列涂黑 $1$ 个， $k$ 列涂黑 $2$ 个的方案数。

有转移：

$$f(i, j, k) \leftarrow f(i, j, k) \newline f(i + 1, j, k) \leftarrow f(i, j, k) \binom {m - j - k} 1 \newline f(i + 1, j - 1, k + 1) \leftarrow f(i, j, k) \binom j 1 \newline f(i + 1, j + 2, k) \leftarrow f(i, j, k) \binom {m - j - k} 2 \newline f(i + 1, j, k + 1) \leftarrow f(i, j, k) \binom {m - j - k} 1 \newline f(i + 1, j - 2, k + 2) \leftarrow f(i, j, k) \binom j 2 \newline$$

代码

提交记录

/*
author: byronwan
problem:
    url: https://www.luogu.com.cn/problem/P1972
    title: [AHOI2009] 中国象棋
date: 2022-09-12
*/

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 110, MOD = 9999973, INV2 = 4999987;

typedef long long ll;

int n, m;
ll f[MAXN][MAXN][MAXN];

ll comb(ll x, ll y)
{
    assert(y == 1 || y == 2);
    if (y == 1) return x;
    else return x * (x - 1) % MOD * INV2 % MOD;
}

signed main()
{
    cin >> n >> m;
    f[0][0][0] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= m; j++) {
            for (int k = 0; j + k <= m; k++) {
                f[i + 1][j][k] = (f[i + 1][j][k] + f[i][j][k]) % MOD;
                if (m - j - k >= 1)
                    f[i + 1][j + 1][k]
                      = (f[i + 1][j + 1][k] + f[i][j][k] * comb(m - j - k, 1) % MOD) % MOD;
                if (j >= 1)
                    f[i + 1][j - 1][k + 1]
                      = (f[i + 1][j - 1][k + 1] + f[i][j][k] * comb(j, 1)) % MOD;
                if (m - j - k >= 2)
                    f[i + 1][j + 2][k]
                      = (f[i + 1][j + 2][k] + f[i][j][k] * comb(m - j - k, 2)) % MOD;
                if (j >= 1 && m - j - k >= 1)
                    f[i + 1][j][k + 1]
                      = (f[i + 1][j][k + 1]
                          + f[i][j][k] * comb(m - j - k, 1) % MOD * comb(j, 1) % MOD)
                      % MOD;
                if (j >= 2)
                    f[i + 1][j - 2][k + 2]
                      = (f[i + 1][j - 2][k + 2] + f[i][j][k] * comb(j, 2) % MOD) % MOD;
            }
        }
    }

    ll res = 0;
    for (int j = 0; j <= m; j++)
        for (int k = 0; k + j <= m; k++) res = (res + f[n][j][k]) % MOD;

    cout << res << endl;
}