Solution
根据题目规则，很显然，每一行每一列最多只能放两个棋子。设 (f_{i,j,k}) 表示处理到第 (i) 行，有 (j) 列放了一个棋子，(k) 列放了两个棋子的方案数。分情况讨论第 (i) 行的棋子放置情况：
什么也不放
直接转移即可：
[f_{i,j,k}=f_{i-1,j,k}
]
放一个棋子
有两种情况：
- 放在没有棋子的一列
[f_{i,j,k}+=f_{i-1,j-1,k}*(m-j-k+1)
]
- 放在有一个棋子的一列
[f_{i,j,k}+=f_{i-1,j+1,k-1}*(j+1)
]
放两个棋子
有三种情况：
- 都放在没有棋子的列上
[f_{i,j,k}+=f_{i-1,j-2,k}*((m-j-k+2)*frac{m-j-k+1}{2})
]
- 都放在有一个棋子的列上
[f_{i,j,k}+=f_{i-1,j+2,k-2}*((j+2)*frac{j+1}{2})
]
- 一个放在没有棋子的列上，一个放在有一个棋子的列上
[f_{i,j,k} += f_{i-1,j,k-1}*j*(m-j-k+1)
]
状态转移方程就写完了，注意判断边界。
Code
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 233, mod = 9999973;
long long n, m, f[N][N][N], ans = 0;
int main()
{
scanf("%lld%lld", &n, &m);
f[0][0][0] = 1;
for(int i = 1; i <= n; i++)
for(int j = 0; j <= m; j++)
for(int k = 0; k + j <= m; k++)
{
f[i][j][k] += (f[i - 1][j][k]) % mod;
if(k > 0) f[i][j][k] += (f[i - 1][j + 1][k - 1] * (j + 1)) % mod;
if(j > 0) f[i][j][k] += (f[i - 1][j - 1][k] * (m - j - k + 1)) % mod;
if(k > 0) f[i][j][k] += (f[i - 1][j][k - 1] * j * (m - j - k + 1)) % mod;
if(j > 1) f[i][j][k] += (f[i - 1][j - 2][k] * ((m - j - k + 2) * (m - j - k + 1) / 2)) % mod;
if(k > 1) f[i][j][k] += (f[i - 1][j + 2][k - 2] * ((j + 2) * (j + 1) / 2)) % mod;
f[i][j][k] %= mod;
}
for(int i = 0; i <= m; i++) for(int j = 0; j <= m; j++)
ans = (ans + f[n][i][j]) % mod;
printf("%lld", ans);
return 0;
}