WTRC's Memory

题目大意

给出一个N*M的棋盘，然后让你在上面放“炮”，使得炮两两之间不能打到（就是每行每列最多放2个），求方案种数。结果对9999973取模。

题解

这题其实就是一个三维的DP，亏我模拟赛的时候硬要刚二维DP，刚了两个小时，最后还是暴搜骗了30分，跪lnjlnjlnj大爷跪跪跪。

考虑一个数组F_i,j,k，表示当前在第i行，其中j列至少有1个炮，k列有2个炮。

那么一行有6种情况：

1、什么都不放

F_i+1,j,k+=F_i,j,k

2、放1个炮在没炮的一列

F_i+1,j,k+=F_i,j,k*(M-j)

3、放1个炮在有炮的一列

F_i+1,j,k+1+=F_i,j,k*(j-k)

4、放2个炮，都在没炮的列上

F_i+1,j+2,k+=F_i,j,k*(M-j)*(M-j-1)/2

5、放2个炮，一个在有1个炮的列上，一个在没炮的列上

F_i+1,j+1,k+1+=F_i,j,k*(M-j)*(j-k)

6、放2个炮，都在有炮的列上

F_i+1,j,k+2+=F_i,j,k*(j-k)*(j-k-1)/2

应该不难理解吧……哦对了，还有初始状态F_0,0,0=1，其他都是0。

 下面就是大家期待已久的代码啦~

//WTRC - Luogu2051 
#include<cstdio>   
#include<algorithm>    
#define MOD 9999973   
#define ll long long   
using namespace std;   
int n,m,Min;   
ll f[152][152][152],ans;   
int main(){ 
    scanf("%d%d",&n,&m); 
    if (n<m) n+=m,m=n-m,n-=m; 
    f[0][0][0]=1; 
    for (int i=0;i<n;++i){ 
        Min=min(i*2,m); 
        for (int j=0;j<=Min;++j) 
            for (int k=0;k<=j;++k){ 
                f[i+1][j][k]+=f[i][j][k]; 
                if (m>j) f[i+1][j+1][k]+=f[i][j][k]*(m-j)%MOD; 
                if (j>k) f[i+1][j][k+1]+=f[i][j][k]*(j-k)%MOD; 
                if (m-1>j) f[i+1][j+2][k]+=f[i][j][k]*(m-j)*(m-j-1)/2%MOD; 
                if ((m>j) && (j>k)) f[i+1][j+1][k+1]+=f[i][j][k]*(m-j)*(j-k)%MOD; 
                if (j-1>k) f[i+1][j][k+2]+=f[i][j][k]*(j-k)*(j-k-1)/2%MOD; 
            } 
    } 
    for (int i=0;i<=m;++i)  
        for (int j=0;j<=i;++j)  
            ans=(ans+f[n][i][j])%MOD;       
    printf("%d\n",ans);   
}