传送门
解题思路
设dp[i][j][k]为到前i行，有j列放了1个炮，k列放了两个炮的方案数。
显然讨论各种情况，从i-1进行转移即可。
可以滚动数组，但没必要。
- 一个不放：方案数等于dp[i-1][j][k]。
- 放一个，放在原来一个没有的列上：方案数等于dp[i-1][j-1][k]*(m-(j-1)-k)
- 放一个，放在原来有一个炮的列上：方案数等于dp[i-1][j+1][k-1]*(j+1)
- 放两个，全放在原来一个没有的列上：方案数等于dp[i-1][j-2][k]*(m-(j-2)-k)*(m-(j-2)-k-1)/2
- 放连个，全放在原来有一个炮的列上：方案数等于dp[i-1][j+2][k-2]*(j+2)*(j+1)/2
- 放两个，一个放在原来没有炮的列上，一个放在原来有一个炮的列上：方案数等于dp[i-1][j][k-1]*(m-j-(k-1))*j
注意取模和边界判断即可。
AC代码
#include<cstdio>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cmath>
#include<algorithm>
using namespace std;
const int mod=9999973;
const int maxn=105;
int n,m;
long long dp[maxn][maxn][maxn];
long long ans;
inline long long c(int x){
return (long long)x*(x-1)/2;
}
int main(){
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=0;i<=n;i++) dp[i][0][0]=1;
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){
for(int k=0;k<=m;k++){
if(j+k>m) break;
dp[i][j][k]=dp[i-1][j][k];
if(j>=1) dp[i][j][k]+=dp[i-1][j-1][k]*(m-j+1-k);
if(k>=1) dp[i][j][k]+=dp[i-1][j+1][k-1]*(j+1);
if(j>=2) dp[i][j][k]+=dp[i-1][j-2][k]*c(m-j+2-k);
if(k>=2) dp[i][j][k]+=dp[i-1][j+2][k-2]*c(j+2);
if(j>=1&&j-1+k<m) dp[i][j][k]+=dp[i-1][j][k-1]*(m-j+1-k)*j;
dp[i][j][k]%=mod;
if(i==n) ans=(ans+dp[i][j][k])%mod;
}
}
}
cout<<ans;
return 0;
}