其实就是再问你在任意行或列棋子数量不超过$2$，所以考虑$dp$维护这个结论
我们可以直接限制行，开维限制列，所以设$dp(i,j,k)$为前$i$行有$j$列有$1$个棋子，有$k$列有$2$个棋子
然后分类讨论一下这行取一个，两个，或者不取的个数。最后累加即可
详情见代码
#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> #define mod 9999973 #define int long long using namespace std; inline int read(){ int f=1,ans=0;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();} return f*ans; } const int MAXN=101; int dp[MAXN][MAXN][MAXN],n,m; int C(int x,int y){ return (x*(x-1)/2)%mod; } int ans; signed main(){ n=read(),m=read(); dp[0][0][0]=1; for(int i=1;i<=n;i++){ for(int j=0;j<=m;j++){ for(int z=0;z<=m-j;z++){ dp[i][j][z]+=dp[i-1][j][z];/*不放*/ dp[i][j][z]%=mod; /*放一个*/ if(z>=1)dp[i][j][z]+=dp[i-1][j+1][z-1]*(j+1); dp[i][j][z]%=mod; if(j>=1)dp[i][j][z]+=dp[i-1][j-1][z]*(m-(j-1+z)); dp[i][j][z]%=mod; /*放两个*/ if(z>=2)dp[i][j][z]+=dp[i-1][j+2][z-2]*C(j+2,2); dp[i][j][z]%=mod; if(z>=1)dp[i][j][z]+=dp[i-1][j][z-1]*j*(m-j-z+1);/*一个放在有棋子的列*/ // dp[i][j][z]%=mod; if(j>=2)dp[i][j][z]+=dp[i-1][j-2][z]*C(m-(j-2+z),2);/*放在都没有棋子的列上*/ dp[i][j][z]%=mod; } } } for(int i=0;i<=m;i++) for(int j=0;j<=m-i;j++) ans+=dp[n][i][j],ans%=mod; cout<<ans; }