一个需要考虑比较多状态的dp

---

 

通过象棋规则可知，一列最多有两个炮

因为如果有三个炮他们就可以互相伤害了

 

设f[i][j][k]为前i行，有j列有一个棋子，有k列有两个棋子

容斥一下可得没有棋子的列数为m-j-k

我们枚举方棋子的状态

<1>只放一个棋子

(1) 把这个棋子放在一列没有棋子的列上

　当这个棋子放好之后，有一个棋子的列会+1，没有棋子的列会-1

　　f[i][j][k]=f[i][j][k]+f[i-1][j-1][k]*(m-j-k+1)

(2)把这个棋子放在一列有一个棋子的列上

　当这个棋子放好之后，有一个棋子的列会-1，有两个棋子的列会+1

　　f[i][j][k]=f[i][j][k]+f[i-1][j+1][k-1]*(j+1)

<2>放两个棋子

(1) 一个放在没棋子的列上，一个放在有一个棋子的列上

　当这两个棋子放好之后，有一个棋子的列会+1，有两个棋子的列会+1，没有棋子的列会-1

　　 f[i][j][k]=f[i][j][k]+f[i-1][j][k-1]*j*(m-j-k+1)

(2) 两个都放在有一个棋子的列上

　当这个棋子放好之后，有一个棋子的列会-2，有两个棋子的列会+2

　　f[i][j][k]=f[i][j][k]+f[i-1][j+2][k-2]*(j+2)*(j+1)/2

(3) 两个都放在没有棋子的列上

　当这个棋子放好之后，有一个棋子的列会+2，没有棋子的列会-2

　　f[i][j][k]=f[i][j][k]+f[i-1][j-2][k]*(m-j-k+2)*(m-j-k+1)/2

---

code

////  main.cpp//  bzoj////  Created by gengyf on 2019/7/18.//  Copyright © 2019 yifan Geng. All rights reserved.//#include 
     
      using namespace std;namespace gengyf{    inline int read(){        int f=1,x=0;char c=getchar();        while(c<'0'||c>'9'){
   if(c=='-') f=-1;c=getchar();}        while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}        return f*x;    }#define mod 9999973    int n,m,ans;    int f[105][105][105];    inline int C(int x){        return x*(x-1)/2%mod;    }    int main(){        n=read();m=read();        f[0][0][0]=1;        for(int i=1;i<=n;i++)            for(int j=0;j<=m;j++)                for(int k=0;k<=m-j;k++){                    f[i][j][k]=f[i-1][j][k];                    if(k>=1)f[i][j][k]+=f[i-1][j+1][k-1]*(j+1);//放有一个                    if(j>=1)f[i][j][k]+=f[i-1][j-1][k]*(m-j-k+1);//放没棋子                    if(k>=1)f[i][j][k]+=f[i-1][j][k-1]*j*(m-j-k+1);                    //放两个，一个在没棋子的，一个在有一个棋子的                    if(k>=2)f[i][j][k]+=f[i-1][j+2][k-2]*C(j+2);                    //放两个，都放在有一个棋子的                    if(j>=2)(f[i][j][k]+=f[i-1][j-2][k]*C(m-j-k+2));                    //放两个，都放在没棋子的                    f[i][j][k]%=mod;                }        for(int i=0;i<=m;i++)            for(int j=0;j<=m;j++){                ans+=f[n][i][j];                ans%=mod;            }        printf("%d",(ans+mod)%mod);        return 0;    }}int main() {    gengyf::main();    return 0;}