题目简介
n*m的棋盘，对每行放炮，要求每行每列炮数<=2，求方案数%9999973 N,M<=100
题目分析
算法考虑
考虑到N,M范围较小，每一行状态只与前面的行状态有关，考虑状压Dp
算法分析
设dp[i][j][k]表示放了前i行，j列有1个棋子，k列有两个棋子
那么0个棋子就是m-j-k
然后就可以分类讨论了
情况一
第i行不放棋子：直接继承上一行状态，有：f[i][j][k]=f[i-1][j][k]
情况二
第i行只放一个棋子：
1、该棋放在只有一个棋的列上
有f[i][j][k]=f[i-1][j+1][k-1]*(j+1) 因为对于前i-1行，有一个棋子的一列少了1，而因为放置棋子，有两个的棋子又多了一列，又因为该棋子可以随便放在只有一个棋的列上，所以要乘(j+1)
有:f[i][j][k]=f[i-1][j+1][k-1]*(j+1)
2、该棋放在没有棋子的列上
同理，即f[i-1][j-1][k]可以转移到f[i][j][k]
又因为我在空列中的任何一列放置这个棋子.
所以要×(m-j-k+1)
有：f[i][j][k]=f[i][j][k]+f[i-1][j-1][k]*(m-j-k+1);
情况三
第i行放两个棋子
1、放在一列一个的，一列没有棋子的列上
一个没有棋子的列会变成一个有一个棋子的列,而一个有一个棋子的列会变成一个有两个棋子的列。
此时我们发现,
有一个棋子的列的数量不会变,因此第二维依旧为j，
又因为我们会新增一个有两个棋子的列,所以我们需要从k-1转移过来.
有：f[i][j][k]=f[i][j][k]+f[i-1][j][k-1]*j*(m-j-k+1)
2、放在两个没有棋子的列上
会增加两个新的有一个棋子的列.
因此我们需要从j-2转移过来.
而两个棋子的列的数量并不会改变,所以依旧为k
最后乘C(2,m-k-j+2)，因为从没有棋子的列中任选两个
有：f[i][j][k]=f[i][j][k]+f[i-1][j-2][k]*C(2,m-k-j+2)
3、放在两个有一个棋子的列上
这两个有一个棋子的列都会变成有两个子的列.
即j+2变成j，从k-2变成k
最后乘C(2,j+2)因为从有一个棋子的列中任选两个
有：f[i][j][k]=f[i][j][k]+f[i-1][j+2][k-2]*C(2,j+2)
代码
#include<bits/stdc++.h>
#define re register
#define ll long long
using namespace std;
inline int read()
{
int k=1,sum=0;
char c=getchar();
for(;c<'0' || c>'9';c=getchar()) if(c=='-') k=-1;
for(;c>='0' && c<='9';c=getchar()) sum=sum*10+c-'0';
return sum*k;
}
int n,m;
const int MOD=9999973,N=1e2+10;
ll f[N][N][N];
inline int C(int x){
return ((x*(x-1))/2)%MOD;
}
int main()
{
n=read();m=read();f[0][0][0]=1;
for(re int i=1;i<=n;++i){
for(re int j=0;j<=m;++j){
for(re int k=0;k<=m-j;++k){
f[i][j][k]=f[i-1][j][k];
if(k>0 && j+1<=m) f[i][j][k]=(f[i][j][k]+f[i-1][j+1][k-1]*(j+1))%MOD;
if(j>0) f[i][j][k]=(f[i][j][k]+f[i-1][j-1][k]*(m-j-k+1))%MOD;
if(k>0) f[i][j][k]=(f[i][j][k]+f[i-1][j][k-1]*j*(m-j-k+1))%MOD;
if(k>1) f[i][j][k]=(f[i][j][k]+f[i-1][j+2][k-2]*C(j+2))%MOD;
if(j>1) f[i][j][k]=(f[i][j][k]+f[i-1][j-2][k]*C(m-k-j+2))%MOD;
f[i][j][k]%=MOD;
}
}
}
int ans=0;
for(re int j=0;j<=m;++j)
for(re int k=0;k<=m-j;++k)
ans=(ans+f[n][j][k])%MOD;
cout<<ans;
return 0;
}