状压DP，感觉状态不太好想...
设(f[i][j][k])表示前i行，有j列放了1个，有k列放了2个。
对当前列放棋子的情况进行分类讨论：
-
放0个
- 直接从上一行转移： (f[i][j][k] = f[i-1][j][k])
-
放1个
- 放在有0个棋子的列：(f[i][j][k] += f[i-1][j-1][k] * C_{m-j-k+1}^1)
- 放在有1个棋子的列：(f[i][j][k] += f[i-1][j+1][k-1] * C_{j+1}^1)
-
放2个
- 都放在有0个棋子的列：(f[i][j][k] += f[i-1][j-2][k] * C_{m-j-k+2}^2)
- 分别放在有0个、有1个的棋子的列：(f[i][j][k] += f[i-1][j][k-1] * C_{m-j-k+1}^1 * C_{j}^1)
- 都放在有1个棋子的列：(f[i][j][k] += f[i-1][j+2][k-2] * C_{j+2}^2)
不要忘记取模和(long long)
(code)
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#define MogeKo qwq
using namespace std;
const int mod = 9999973;
int n,m;
long long ans,f[105][105][105];
long long C(int x,int y) {
long long sum = 1;
for(int i = x; i > x-y; i--)
sum *= i;
for(int i = y; i > 1; i--)
sum /= i;
return sum % mod;
}
int main() {
scanf("%d%d",&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 <= m-j; k++) {
f[i][j][k] += f[i-1][j][k];
if(j>=1) f[i][j][k] += f[i-1][j-1][k] * C(m-j-k+1,1);
if(k>=1) f[i][j][k] += f[i-1][j+1][k-1] * C(j+1,1);
if(j>=2) f[i][j][k] += f[i-1][j-2][k] * C(m-j-k+2,2);
if(k>=1) f[i][j][k] += f[i-1][j][k-1] * C(m-j-k+1,1) * C(j,1);
if(k>=2) f[i][j][k] += f[i-1][j+2][k-2] * C(j+2,2);
f[i][j][k] %= mod;
}
for(int j = 0; j <= m; j++)
for(int k = 0; k <= m-j; k++)
(ans += f[n][j][k]) %= mod;
printf("%lld",ans);
return 0;
}