题目大意是这样的:

无论行与列,都必须满足炮的数量$\le 2$

所以我们需要设计一个方程来满足这两个条件。

状态可以描述列的正确性

转移可以描述行的正确性

因此就有状态$f_{i,j,k}$表示前$i$行,有$j$列有一个炮,有$k$列有两个炮,有$m-j-k$列没有炮的方案数。

转移可以描述成,第$i$行不放,放一个,放两个。

具体请自行实现。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define ll long long
#define gc getchar()
using namespace std;
const int N=105,mod=9999973;
template<class o>
inline void qr(o &x)
{
    x=0;char c=gc;
    while(c<'0'||c>'9')c=gc;
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
}
void qw(ll x)
{
    if(x<0)putchar('-'),x=-x;
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
ll f[N][N][N];
int main()
{
    int n,m;qr(n),qr(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++)
            {
                int z=(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]*(z+1);
                if(k>=1)f[i][j][k]+=f[i-1][j+1][k-1]*(j+1);
                if(k>=1)f[i][j][k]+=f[i-1][j][k-1]*j*(z+1);
                if(k>=2)f[i][j][k]+=f[i-1][j+2][k-2]*((j+2)*(j+1)/2);
                if(j>=2)f[i][j][k]+=f[i-1][j-2][k]*((z+2)*(z+1)/2);
                f[i][j][k]%=mod;
            }
    ll ans=0;
    for(int j=0;j<=m;j++)
        for(int k=0;k<=m-j;k++)
            ans=(ans+f[n][j][k])%mod;
    qw(ans);puts("");
    return 0;
}