题解
不好形容的DP。设$f(i,j,k)$表示当前在第$i$行，有$j$列没炮，$k$列$1$个炮。就可以愉快的转移了。
转移的时候注意系数。（也就是组合数）1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
using namespace std;
typedef long long ll;
int read(){
int f=1,x=0;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return f*x;
}
ll n,m,f[105][105][105]={0};
//f(i,j,k) 第i行 j列0个 k列1个
void init(){
n=read(),m=read();
f[1][m][0]=1,f[1][m-1][1]=m;
if(m!=1)f[1][m-2][2]=m*(m-1)/2;
}
void solve(){
for(int i=2;i<=n;i++)
for(ll j=0;j<=m;j++)
for(ll k=0;k+j<=m;k++){
f[i][j][k]+=f[i-1][j][k];
if(k>=2)f[i][j][k]+=f[i-1][j+2][k-2]*(j+2)*(j+1)/2;
if(j+1<=m)f[i][j][k]+=f[i-1][j+1][k]*(j+1)*k;
if(k+2<=m)f[i][j][k]+=f[i-1][j][k+2]*(k+2)*(k+1)/2;
if(k>=1)f[i][j][k]+=f[i-1][j+1][k-1]*(j+1);
if(k+1<=m)f[i][j][k]+=f[i-1][j][k+1]*(k+1);
f[i][j][k]%=Mod;
}
ll ans=0;
for(int j=0;j<=m;j++)
for(int k=0;k+j<=m;k++)
ans=(ans+f[n][j][k])%Mod;
printf("%lld\n",ans);
}
int main(){
init();
solve();
return 0;
}