[AHOI2009]中国象棋

每行每列最多放两个
dp 数组记录第i 行，有j 列放了1个，k 列放了2个的方案数
不放

$$dp\left [i \right ]\left [ j \right ]\left [k \right ]+=dp\left [i-1 \right ]\left [ j \right ]\left [k \right ]$$

放一个

$$dp\left [i\right ]\left [ j+1 \right ]\left [k \right ]+=dp\left [i-1 \right ]\left [ j \right ]\left [k \right ]*(m-j-k)(m-j-k>0)$$ $$dp\left [i \right ]\left [ j \right ]\left [k +1 \right ]+=dp\left [i -1\right ]\left [ j \right ]\left [k \right ]*j(j>0)$$

放两个

$$dp\left [i \right ]\left [ j -2\right ]\left [k +2 \right ]+=dp\left [i-1 \right ]\left [ j \right ]\left [k \right ]*C_{j}^{2}(j\geq 2)$$ $$dp\left [i \right ]\left [ j +2\right ]\left [k \right ]+=dp\left [i-1 \right ]\left [ j \right ]\left [k \right ]*C_{m-j-k}^{2}(m-j-k\geq 2)$$ $$dp\left [i \right ]\left [ j \right ]\left [k +1\right ]+=dp\left [i-1 \right ]\left [ j \right ]\left [k \right ]*(m-j-k)*j(j>0,m-j-k>0)$$

#include<cstdio>
#define LL long long
const int N=105,mod=9999973;
int n,m;
LL dp[N][N][N]; //row,1,2
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;j+k<=m;k++) 
            {
                dp[i][j][k]=(dp[i][j][k]+dp[i-1][j][k])%mod;
                if (m-j-k>0) dp[i][j+1][k]=(dp[i][j+1][k]+dp[i-1][j][k]*(m-j-k))%mod;
                if (j>0) dp[i][j-1][k+1]=(dp[i][j-1][k+1]+dp[i-1][j][k]*j)%mod;
                if (j>=2) dp[i][j-2][k+2]=(dp[i][j-2][k+2]+dp[i-1][j][k]*j*(j-1)/2)%mod;
                if (m-j-k>=2) dp[i][j+2][k]=(dp[i][j+2][k]+dp[i-1][j][k]*(m-j-k)*(m-j-k-1)/2)%mod;
                if (j>0&&m-j-k>0) dp[i][j][k+1]=(dp[i][j][k+1]+dp[i-1][j][k]*(m-j-k)*j)%mod;                
            }
    int ans=0;
    for(int i=0;i<=m;i++)
        for(int j=0;i+j<=m;j++)
            ans=(ans+dp[n][i][j])%mod;
    printf("%d\n",ans);
    return 0;
}