DP。状态设计是点睛之笔。
首先显然有每行或每列只能有至多 \(2\) 个棋子。
设状态 \(f_{i,j,k}\) 为第 \(i\) 行，有 \(j\) 列只放了一个棋子，\(k\) 列放了两个棋子。
之后直接转移即可。注意边界判断。
code：
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define debug cout<<"debug\n"
#define vi vector<int>
#define imp map<int,int>
#define il inline
#define pb push_back
using namespace std;
const int N=105,mod=9999973;
int n,m;
ll f[N][N][N];
ll C(ll x){
return (x*(x-1))/2%mod;
}
int main(){
freopen("D.in","r",stdin);
freopen("D.out","w",stdout);
cin>>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>0){//0+1
f[i][j][k]+=f[i-1][j-1][k]*(m-(j-1)-k)%mod;
f[i][j][k]%=mod;
}
if(k>0){//1+2
f[i][j][k]+=f[i-1][j+1][k-1]*(j+1)%mod;
f[i][j][k]%=mod;
}
if(k>1){//1*2+2*2
f[i][j][k]+=f[i-1][j+2][k-2]*C(j+2)%mod;
f[i][j][k]%=mod;
}
if(j>1){//0*2+1*2
f[i][j][k]+=f[i-1][j-2][k]*C(m-(j-2)-k)%mod;
f[i][j][k]%=mod;
}
if(j>0&&k>0){//0+1,1+2
f[i][j][k]+=f[i-1][j][k-1]*(m-j-(k-1))*j;
f[i][j][k]%=mod;
}
}
}
}
ll ans=0;
for(int i=0;i<=m;i++){
for(int j=0;j<=m;j++){
ans+=f[n][i][j];
ans%=mod;
}
}
cout<<ans<<"\n";
return 0;
}