BZOJ原题链接
洛谷原题链接
这题挺难想状态的，刚看题感觉是状压，但数据(100)显然不可能。
注意到每行每列只能放(0sim 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)行放一个棋子
- 放在原本没有放棋子的列上，共(m - (j - 1) - k)种放法：$$f[i][j][k] = f[i][j][k] + f[i - 1][j - 1][k] imes (m - (j - 1) - k)$$
- 放在原本只有一个棋子的列上，共(j + 1)种放法：$$f[i][j][k] = f[i][j][k] + f[i - 1][j + 1][k - 1] imes (j + 1)$$
- 第(i)行放两个棋子
- 都放在原本没有放棋子的列上，共(C_{m - (j - 2) - k} ^ 2)种放法：$$f[i][j][k] = f[i][j][k] + f[i - 1][j - 2][k] imes C_{m - (j - 2) - k} ^ 2$$
- 一个放在空列，一个放在原本只有一个棋子的列上，共(j imes (m - j - (k - 1)))种放法：$$f[i][j][k] = f[i][j][k] + f[i - 1][j][k - 1] imes j imes (m - j - (k - 1))$$
- 都放在原本只有一个棋子的格子上，共(C_{j + 2} ^ 2)种放法：$$f[i][j][k] = f[i][j][k] + f[i - 1][j + 2][k - 2] imes C_{j + 2} ^ 2$$
初值(f[0][0][0] = 1)，其它为(0)。
在(DP)过程中注意取模和边界问题。
最后答案就是(sumlimits_{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;
}