这也是一道dp方程很难想出来的dp
要是想通了方程，后续的推导也需要花费一定的时间，所以是一道好题
我直接讲dp方程吧
因为我也没有想出来dp方程，是某个同学告诉我的
dp[i][j][k]表示到了第i行，这一行之前有j列放了1个棋子，有k列放了2个棋子
这个方程确实不好想
转移有一点多
总共有6个转移方程
其实是压了一维，这一维是放了0个棋子的列数
因为这一维可以由其他两维推出他就=m-j-k;
dp[i][j][k]=(dp[i][j][k]+dp[i-1][j][k])%mod;
表示这一行什么棋子也不取
dp[i][j][k]=(dp[i][j][k]+dp[i-1][j-1][k]*(m-j-k+1))%mod;
表示这一行将之前的一个0个全变成1个有多少种方案
就是由j-1在加上了这个变来得1
dp[i][j][k]=(dp[i][j][k]+dp[i-1][j+1][k-1]*(j+1))%mod;
表示这一行将之前的一个1全变成2有多少种方案
由j+1减去了1，k-1加上了1
dp[i][j][k]=(dp[i][j][k]+dp[i-1][j-2][k]*calc(m-j-k+2))%mod;
这是将之前的2个0全都变成1
因为可以任取2个，所以运用组合数就是C（m-j-k+2，2）
dp[i][j][k]=(dp[i][j][k]+dp[i-1][j+2][k-2]*calc(j+2))%mod;
这是将之前的2个1全变成2
通过组合数同样是C（j+2，2）
dp[i][j][k]=(dp[i][j][k]+dp[i-1][j][k-1]*(m-j-k+1)*j)%mod;
这里表示将之前的1个0变成1，一个1变成2
j-1加上当前由0变成的1就是j，再将两个方案乘起来
这就是所有的6个方程
代码如下
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 typedef long long ll; 8 const ll mod=9999973; 9 const ll N=105;10 ll dp[N][N][N],n,m;11 ll calc(ll x)12 {13 return (x*(x-1)/2)%mod;14 }15 int main()16 {17 scanf("%lld %lld",&n,&m);18 dp[0][0][0]=1;19 for(ll i=1;i<=n;i++)20 for(ll j=0;j<=m;j++)21 for(ll k=0;k<=m-j;k++)22 {23 dp[i][j][k]=(dp[i][j][k]+dp[i-1][j][k])%mod;// 124 if(m-j-k+1>=0 && j>=1)25 dp[i][j][k]=(dp[i][j][k]+dp[i-1][j-1][k]*(m-j-k+1))%mod;// 226 if(j+1>=0 && k>=1)27 dp[i][j][k]=(dp[i][j][k]+dp[i-1][j+1][k-1]*(j+1))%mod;// 328 if(m-j-k+2>=0 && j>=2)29 dp[i][j][k]=(dp[i][j][k]+dp[i-1][j-2][k]*calc(m-j-k+2))%mod;//430 if(j+2>=0 && k>=2)31 dp[i][j][k]=(dp[i][j][k]+dp[i-1][j+2][k-2]*calc(j+2))%mod;// 532 if(m-j-k+1>=0 && k>=1 && j>=1)33 dp[i][j][k]=(dp[i][j][k]+dp[i-1][j][k-1]*(m-j-k+1)*j)%mod;// 634 }35 ll ans=0;36 for(int j=0;j<=m;j++)37 for(int k=0;k+j<=m;k++)38 {39 ans=(ans+dp[n][j][k])%mod;40 }41 printf("%lld\n",ans);42 return 0;43 }