大致题意： 让你在一张\(N*M\)的棋盘上摆放炮，使其无法互相攻击，问有多少种摆法。

辟谣

听某大佬说这是一道状压\(DP\)题，于是兴冲冲地去做，看完数据范围彻底懵了：\(N≤100\)！这么大的数据范围压死你！

好吧，其实这就是一道普通的\(DP\)，与状压没有任何关系。

其实状压可以用来骗分，能得50。

考虑性质

对于这种题目，第一步肯定是考虑有没有什么比较重要的性质。

考虑炮的攻击方法，应该不难发现，每一行、每一列放的炮的数量不能超过\(2\)。

保证每行不超过\(2\)，应该很简单。

那么如何处理每列不超过\(2\)呢？这时就不难想到用\(f_{i,j,k}\)来表示当前处理到第\(i\)行，有\(j\)列有\(1\)个炮，\(k\)列有\(2\)个炮时的方案数。

这样一来，应该就有一个比较清晰的思路了。

接下来，就是无比烦人的分类讨论。

分类讨论

不难发现，这题的状态有很多转移方式，因此就需要用到分类讨论。

• 第一种情况： 这一行什么棋子也不放。

  直接将\(f_{i,j,k}\)加上\(f_{i-1,j,k}\)即可。

• 第二种情况： 在没有放过炮的一列上放一个炮。

  比较显然应从状态\((i-1,j-1,k)\)转移过来。

  \(∵\)在转移之前有\((m-i-j+1)\)列是没有放过炮的，

  \(∴\)放炮的方式共有\((m-i-j+1)\)种，

  \(∴\)将\(f_{i,j,k}\)加上\((m-i-j+1)*f_{i-1,j-1,k}\)。

• 第三种情况： 在没有放过炮的两列上各放一个炮。

  此时的状态应从状态\((i-1,j-2,k)\)转移过来。

  \(∵\)在转移之前有\((m-i-j+2)\)列是没有放过炮的，

  \(∴\)放炮的方式共有\(C_{m-j-k+2}^2\)种，即\(\frac{(m-j-k+1)*(m-j-k+2)}2\)种，

  \(∴\)将\(f_{i,j,k}\)加上\(\frac{(m-j-k+1)*(m-j-k+2)}2*f_{i-1,j-2,k}\)。

• 第四种情况： 在放过一个炮的一列上放一个炮。

  此时的状态应从状态\((i-1,j+1,k-1)\)转移过来。

  \(∵\)在转移之前有\((j+1)\)列是放过一个炮的，

  \(∴\)放炮的方式共有\((j+1)\)种，

  \(∴\)将\(f_{i,j,k}\)加上\((j+1)*f_{i-1,j+1,k-1}\)。

• 第五种情况： 在放过一个炮的两列上各放一个炮。

  此时的状态应从状态\((i-1,j+2,k-2)\)转移过来。

  \(∵\)在转移之前有\((j+2)\)列是放过一个炮的，

  \(∴\)放炮的方式共有\(C_{j+2}^2\)种，即\(\frac{(j+1)*(j+2)}2\)种，

  \(∴\)将\(f_{i,j,k}\)加上\(\frac{(j+1)*(j+2)}2*f_{i-1,j+2,k-2}\)。

• 第六种情况： 在没有放过炮的一列和放过一个炮的一列上各放一个炮。

  此时的状态应从状态\((i-1,j,k-1)\)转移过来。

  \(∵\)在转移之前有\((m-j-k+1)\)列是没有放过炮的，有\(j\)列是放过一个炮的，

  \(∴\)放炮的方式共有\((m-j-k+1)*j\)种，

  \(∴\)将\(f_{i,j,k}\)加上\((m-j-k+1)*j*f_{i-1,j,k-1}\)。

大致就是这\(6\)种情况了，不过取模之类的细节还是需要自己注意一下。

代码

#include
    
     #define max(x,y) ((x)>(y)?(x):(y))#define min(x,y) ((x)<(y)?(x):(y))#define uint unsigned int#define LL long long#define ull unsigned long long#define swap(x,y) (x^=y,y^=x,x^=y)#define abs(x) ((x)<0?-(x):(x))#define INF 1e9#define Inc(x,y) ((x+=(y))>=MOD&&(x-=MOD))#define ten(x) (((x)<<3)+((x)<<1)) #define MOD 9999973#define N 100using namespace std;int n,m; class FIO{    private:        #define Fsize 100000        #define tc() (FinNow==FinEnd&&(FinEnd=(FinNow=Fin)+fread(Fin,1,Fsize,stdin),FinNow==FinEnd)?EOF:*FinNow++)        #define pc(ch) (FoutSize
     
      =1) Inc(f[i][j][k],1LL*f[i-1][j-1][k]*(m-j-k+1)%MOD);//第二种情况                    if(j>=2) Inc(f[i][j][k],1LL*f[i-1][j-2][k]*((m-j-k+1)*(m-j-k+2)>>1)%MOD);//第三种情况                    if(k>=1) Inc(f[i][j][k],1LL*f[i-1][j+1][k-1]*(j+1)%MOD);//第四种情况                    if(k>=2) Inc(f[i][j][k],1LL*f[i-1][j+2][k-2]*((j+1)*(j+2)>>1)%MOD);//第五种情况                    if(j>=1&&k>=1) Inc(f[i][j][k],1LL*f[i-1][j][k-1]*(m-j-k+1)%MOD*j%MOD);//第六种情况                }            }            for(i=lim=min(n<<1,m);~i;--i) for(j=lim-i;~j;--j) Inc(ans,f[n][i][j]);//统计答案            return ans;        } }DP;int main(){    F.read(n),F.read(m),F.write(DP.GetAns());    return F.end(),0;}