AHOI中国象棋（dp）

大力dp题。

每行每列最多放两个，考虑用行作为dp阶段。

dp[i][j][k]表示i行，有一个的有j列，有两个的有k列。

然后就是分类讨论。

一个都不放，放一个在0出，放一个在1出，放两个在0，放两个在1，放两个在01，大力转移。

Code

#include<iostream>
using namespace std;
long long n,m,dp[102][102][102],ans,mod;
inline int c(int n){return (n*(n-1))>>1;}
int main()
{
    cin>>n>>m;
    mod=9999973;
    dp[0][0][0]=1;
    for(int i=1;i<=n;++i)
       for(int j=0;j<=m;++j)
         for(int k=0;k+j<=m;++k)
         {
             dp[i][j][k]+=dp[i-1][j][k];
             dp[i][j][k]%=mod;
             if(m-k-j+1>0&&j-1>=0)dp[i][j][k]+=dp[i-1][j-1][k]*(m-k-j+1);
             dp[i][j][k]%=mod;
             if(j+1<=m&&k-1>=0)dp[i][j][k]+=dp[i-1][j+1][k-1]*(j+1);
             dp[i][j][k]%=mod;
             if(j-2>=0&&m-k-j+2>0)dp[i][j][k]+=dp[i-1][j-2][k]*c(m-k-j+2);
             dp[i][j][k]%=mod;
            if(j+2<=m&&k-2>=0)dp[i][j][k]+=dp[i-1][j+2][k-2]*c(j+2);
            dp[i][j][k]%=mod;
            if(k-1>=0&&j>0)dp[i][j][k]+=dp[i-1][j][k-1]*(m-j-k+1)*j; 
            dp[i][j][k]%=mod;
         }
   for(int i=0;i<=m;++i)
     for(int j=0;j+i<=m;++j)
       ans+=dp[n][i][j],ans%=mod;
    cout<<ans;
    return 0;
}