DP，递推，组合数
其实相当于就是一个递推推式子，然后要用到一点组合数的知识
一道很妙的题，因为不能互相攻击，所以任意行列不能有超过两个炮
首先令f[i][j][k]代表前i行，有j列为一个炮，有k列为两个炮的方案
那么有如下转移：
1,这行不放炮，add+=f[i-1][j][k];
2,放一个炮，并且放在没有炮的那列 add+=f[i-1][j-1][k] * (m - j - k + 1);,因为放了这个炮后，
一个炮的变多了，也就是上一行的j+1得到这一行的j，所以上一行的j就是j-1，
又因为有m - (j - 1) - k列没有炮的，所以有乘上m- j - k + 1种方案
3,放一个炮，并且放在原先有一个炮的那列，add+=f[i-1][j+1][k-1] * (j + 1);
放了这个炮后，一个炮的变少了一个，两个炮的变多了一个，所以还回去就是j+1,k-1，
又因为有j+1列一个炮的，所以有j+1种方案放置
4,放两个炮，都放在没有炮的列上面，add+=f[i-1][j-2][k] * (m - j - k + 2) * (m - j - k + 1) / 2;
那么放了炮后，一个炮的变多了2列，所以还回去是j-2,又因为有(m - j - k + 2)列空的，所以就是在这些里面选两个组合，所以组合数计算
5,放两个炮，分别放在有炮的和没有炮的，add+=f[i-1][j][k-1] * (m - j - k + 1) * j;
因为没有炮 --- > 1个炮 ---> j++
一个炮 ---> 2个炮 ---> j--，k++
相当于j没有变化，而k要还回去，所以是f[i-1][j][k-1]
又因为有(m - j - k + 1)列空的，j列一个炮的，所以相乘得到方案
6,放两个炮，都放在原来有炮的，add+=f[i-1][j+2][k-2] * (j + 2) * (j + 1) / 2;
放了炮后，j-=2,k+=2,所以还回去就是j+2,k-2,
又因为有j+2列一个炮，选两个组合，所以就是(j + 2) * (j + 1) / 2
#include<bits/stdc++.h>
using namespace std;
#define R register int
#define mod 9999973
#define AC 110
#define LL long long
int n,m,ans;
LL f[AC][AC][AC];
void work()
{
scanf("%d%d",&n,&m);
f[][][]=;
for(R i=;i<=n;i++)//枚举行
for(R j=;j<=m;j++)//枚举一个炮有多少列
{
int all=m-j;//因为要保证j+k<=m
for(R k=;k<=all;k++)//枚举两个炮有多少列
{
LL add=;//用一个变量存增量，避免多次访问3维数组，也许可以加速？
add+=f[i-][j][k];
if(j) add+=f[i-][j-][k] * (m - j - k + );
if(k && j + <= m) add+=f[i-][j+][k-] * (j + );//有j+1列一个炮可以选
if(j - >= ) add+=f[i-][j-][k] * (m - j - k + ) * (m - j - k + ) / ;
if(k - >= ) add+=f[i-][j][k-] * (m - j - k + ) * j;
if(j + <= m && k - >= ) add+=f[i-][j+][k-] * (j + ) * (j + ) / ;
if(add > mod) add%=mod;
f[i][j][k]=add;
}
}
for(R j=;j<=m;j++)//枚举最后的情况是怎么样的
{
int all=m-j;
for(R k=;k<=all;k++)
ans=(ans + f[n][j][k])%mod;
}
printf("%d\n",ans);
} int main()
{
freopen("in.in","r",stdin);
work();
fclose(stdin);
return ;
}