题意
在一个$N$行$M$列的棋盘上放若干个炮（可以是$0$个），使得没有一个炮可以攻击到另一个炮，请问有多少种放置方法。
输出方案数模$9999973$的结果
数据范围：
$1 \le n,m \le 100$
题解
首先，每一行或每一列的炮一定小于等于$2$
由于每一行的炮可以直接进行限制，因此需要记录每一行的炮的数量
考虑用 $f[i][j][k]$ 表示前$i$行中有$1$个炮的列有$j$个，有$2$个炮的列有$k$个（当然有$0$个炮的列就有$m-j-k$个）
对于新的一行，我们可以选择不放/放$1$个/放$2$个，对其分类讨论
1.不放
$$f[i][j][k]=f[i-1][j][k]$$
2.放$1$个
(1)
放这个炮之前有$1$个炮的列有$j-1$个，并且我们可以从$m-(j-1)-k$个没有炮的列中选择
$$f[i][j][k]+=f[i-1][j-1][k] \cdot (m-(j-1)-k)$$
(2)放在有$1$个炮的列
放的这一列本来是有$1$个炮的，放了之后变为有$2$个炮的，因此放这个炮之前有$2$个炮的列有$k-1$个，并且我们可以从$j+1$个有$1$个炮的列中选择
$$f[i][j][k]+=f[i-1][j+1][k-1] \cdot (j+1)$$
3.放$2$个
(1)$1$个放在没有炮的列，另$1$个放在有$1$个炮的列
有$1$个炮的列$+1-1$，不变；有$2$个炮的列$+1$，所以原来应为$k-1$个；因为是从两种列中选出，应相乘
$$f[i][j][k]+=f[i-1][j][k-1] \cdot (m-j-(k-1)) \cdot j$$
(2)$2$个都放在没有炮的列
有$m-(j-2)-k$种选择,但由于从同一种列中选出，涉及到组合，应乘$C_{m-(j-2)-k}^2$
$$f[i][j][k]+=f[i-1][j-2][k] \cdot C_{m-(j-2)-k}^2$$
(3)$2$个都放在有$1$个炮的列
有$j+2$种选择，同上
$$f[i][j][k]+=f[i-1][j+2][k-2] \cdot C_{j+2}^2$$
所有情况已分析完毕，$dp$时注意边界及随时取模即可
代码：
#include<iostream>
#include<cstdio>
using namespace std;
const int N=100+10;
const int mod=9999973;
typedef long long LL;
int n,m;
LL dp[N][N][N];
LL ans;
inline int C2(int n){
return (n*(n-1)/2)%mod;
}
int main(){
scanf("%d%d",&n,&m);
dp[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++){
(dp[i][j][k]+=dp[i-1][j][k])%=mod;
if(j>=1)
(dp[i][j][k]+=dp[i-1][j-1][k]*(m-(j-1)-k))%=mod;
if(k>=1)
(dp[i][j][k]+=dp[i-1][j+1][k-1]*(j+1))%=mod;
if(k>=1)
(dp[i][j][k]+=dp[i-1][j][k-1]*(m-j-(k-1))*j)%=mod;
if(j>=2)
(dp[i][j][k]+=dp[i-1][j-2][k]*C2(m-(j-2)-k))%=mod;
if(k>=2)
(dp[i][j][k]+=dp[i-1][j+2][k-2]*C2(j+2))%=mod;
};
for(int j=0;j<=m;j++)
for(int k=0;k<=m-j;k++)
(ans+=dp[n][j][k])%=mod;
printf("%lld",ans);
return 0;
}