Dp题
一开始的我是考虑状呀的。 然后发现。
voc，怎么n和m是100的。然后果断GG
想了许久。然后发现，这个炮只是对他所在的行与列产生影响，对于其他的行与列来说并没有什么影响。
而一行中的炮，我们可以一次把他干出来。
所以影响我们的决策的时候，只有列上的情况对我们有影响。
然后又因为不同列之间互不影响，然后我们只需要记录每种情况的个数就Ok了
我们考虑设计如下状态
(f[i],[j],[k])表示当前我们到了第i行，有(j)个列上有一个炮，有(k)个列上有两个炮。
考虑转移
第i行不放炮
(f[i][j][k]+=f[i-1][j][k])
第i行放一个炮
1.放在没有炮的列上
(f[i][j][k]+=f[i-1][j-1][k]*(m-j-k+1))
2.放在一个炮的列上
(f[i][j][k]+=f[i-1][j+1][k-1]*(j+1))
第i行放两个炮
1.都放在没有炮的列上
(f[i][j][k]+=f[i-1][j-2][k]*C^2_{m-j-k+2})
2.都放在一个炮的列上
(f[i][j][k]+=f[i-1][j+2][k-2]*C^2_{j+2})
3.一个放在一个炮的列上，另一个放在没有炮的列上
(f[i][j][k]+=f[i-1][j][k-1]*j*(m-j-k+1))
乘法原理和加原理搞一搞就可以了
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
const int maxn=110;
long long f[maxn][maxn][maxn];
long long mode(long long val)
{
return val%9999973;
}
long long C(int T)
{
return mode(T*(T-1)/2);
}
int main()
{
f[0][0][0]=1;
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=0;j<=m;j++)
for(int k=0;k+j<=m;k++)
{
f[i][j][k]=mode(f[i][j][k]+f[i-1][j][k]);//注意判断边界
if(j-1>=0) f[i][j][k]=mode(f[i][j][k]+f[i-1][j-1][k]*(m-j+1-k));
if(j-2>=0) f[i][j][k]=mode(f[i][j][k]+f[i-1][j-2][k]*C(m-j+2-k));
if(k-1>=0) f[i][j][k]=mode(f[i][j][k]+f[i-1][j][k-1]*j*(m-j-k+1));
if(k-1>=0&&j+1<=m) f[i][j][k]=mode(f[i][j][k]+f[i-1][j+1][k-1]*(j+1));
if(k-2>=0&&j+2<=m) f[i][j][k]=mode(f[i][j][k]+f[i-1][j+2][k-2]*C(j+2));
}
long long ans=0;
for(int i=0;i<=m;i++)
for(int j=0;i+j<=m;j++)
ans=mode(ans+f[n][i][j]);
printf("%lld",ans);
}