洛谷2051 [AHOI2009]中国象棋

原题链接

这题挺难想状态的，刚看题感觉是状压，但数据\(100\)显然不可能。
注意到每行每列只能放\(0\sim 2\)个棋子，所以我们可以将这个写入状态。
设\(f[i][j][k]\)表示放了前\(i\)行，共有\(j\)列只放了一个棋子，共有\(k\)列放了两个棋子，而没有放棋子的列数则可以直接计算，即\(m - j - k\)。
然后分类讨论。

• 第\(i\)行不放
  只有一种放法，直接由上一层转移：\[f[i][j][k] = f[i][j][k] + f[i - 1][j][k]\]

• 第\(i\)行放一个棋子

1. 放在原本没有放棋子的列上，共\(m - (j - 1) - k\)种放法：\[f[i][j][k] = f[i][j][k] + f[i - 1][j - 1][k] \times (m - (j - 1) - k)\]
2. 放在原本只有一个棋子的列上，共\(j + 1\)种放法：\[f[i][j][k] = f[i][j][k] + f[i - 1][j + 1][k - 1] \times (j + 1)\]

• 第\(i\)行放两个棋子

1. 都放在原本没有放棋子的列上，共\(C_{m - (j - 2) - k} ^ 2\)种放法：\[f[i][j][k] = f[i][j][k] + f[i - 1][j - 2][k] \times C_{m - (j - 2) - k} ^ 2\]
2. 一个放在空列，一个放在原本只有一个棋子的列上，共\(j \times (m - j - (k - 1))\)种放法：\[f[i][j][k] = f[i][j][k] + f[i - 1][j][k - 1] \times j \times (m - j - (k - 1))\]
3. 都放在原本只有一个棋子的格子上，共\(C_{j + 2} ^ 2\)种放法：\[f[i][j][k] = f[i][j][k] + f[i - 1][j + 2][k - 2] \times C_{j + 2} ^ 2\]

初值\(f[0][0][0] = 1\)，其它为\(0\)。
在\(DP\)过程中注意取模和边界问题。
最后答案就是\(\sum\limits_{i = 0} ^ m \sum \limits _{j = 0} ^ m f[n][i][j]\)。

#include<cstdio>
using namespace std;
const int N = 110;
const int mod = 9999973;
int f[N][N][N];
inline int re()
{
    int x = 0;
    char c = getchar();
    bool p = 0;
    for (; c < '0' || c > '9'; c = getchar())
        p |= c == '-';
    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
    return p ? -x : x;
}
inline int C(int x)
{
    return (1LL * x * (x - 1) >> 1) % mod;
}
int main()
{
    int i, j, k, n, m, s = 0;
    n = re();
    m = re();
    f[0][0][0] = 1;
    for (i = 1; i <= n; i++)
        for (j = 0; j <= m; j++)
            for (k = 0; k + j <= m; k++)
            {
                f[i][j][k] = f[i - 1][j][k];
                if (k)
                {
                    f[i][j][k] = ((1LL * f[i - 1][j + 1][k - 1] * (j + 1) % mod) + f[i][j][k]) % mod;
                    f[i][j][k] = ((1LL * f[i - 1][j][k - 1] * j % mod * (m - j - k + 1) % mod) + f[i][j][k]) % mod;
                }
                if (j)
                    f[i][j][k] = ((1LL * f[i - 1][j - 1][k] * (m - j - k + 1) % mod) + f[i][j][k]) % mod;
                if (j > 1)
                    f[i][j][k] = ((1LL * f[i - 1][j - 2][k] * C(m - j - k + 2) % mod) + f[i][j][k]) % mod;
                if (k > 1)
                    f[i][j][k] = ((1LL * f[i - 1][j + 2][k - 2] * C(j + 2) % mod) + f[i][j][k]) % mod;
            }
    for (i = 0; i <= m; i++)
        for (j = 0; j <= m; j++)
            s = (1LL * s + f[n][i][j]) % mod;
    printf("%d", s);
    return 0;
}

洛谷2051 [AHOI2009]中国象棋

原文：https://www.cnblogs.com/Iowa-Battleship/p/9842424.html