JZOJ 4.15 1667——【AHOI2009】中国象棋【dp】

Description

　　在N行M列的棋盘上，放若干个炮可以是0个，使得没有任何一个炮可以攻击另一个炮。请问有多少种放置方法？中国象棋中炮的行走方式大家应该很清楚吧.

Input

　　一行包含两个整数N，M，中间用空格分开.

Output

　　输出所有的方案数，由于值比较大，输出其mod 9999973

Sample Input

1 3

Sample Output

7
Hint

　　除了在3个格子中都放满炮的的情况外，其它的都可以.
　　100%的数据中N,M不超过100
　　50%的数据中，N,M至少有一个数不超过8
　　30%的数据中，N,M均不超过6
　　

---

题目中可见，每一行每一列最多只能放两个炮
可以设f[i][j][k]为前i行有j列放一个炮，k列放两个炮，然后分类讨论：
①不放
②在已经放过一个的放一个
③在没有放过的地方放一个
④在没有放过的地方放两个
⑤在放过一个和没有放过的地方放一个
（Tips：记住要取模）

---

代码如下:

#include<cstdio>  
#include<cstring>  
using namespace std;  
long long f[151][151][151];  
int main()  
{  
    int n,m;  
    scanf("%d%d",&n,&m);  
    memset(f,0,sizeof(f));  
    f[0][0][0]=1;  
    for (int i=0;i<n;i++)  
    {  
        for (int j=0;j<=m;j++)  
        {  
            for (int k=0;k<=j;k++)  
            {  
                if (f[i][j][k]>=9999973) f[i][j][k]%=9999973;  
                f[i+1][j][k]+=f[i][j][k];  
                if (j<m) f[i+1][j+1][k]+=f[i][j][k]*(m-j);  
                if (j<m-1) f[i+1][j+2][k]+=f[i][j][k]*(m-j)*(m-j-1)/2;  
                if (j>0&&k<j) f[i+1][j][k+1]+=f[i][j][k]*(j-k);  
                if (j>0&&k<j-1) f[i+1][j][k+2]+=f[i][j][k]*(j-k)*(j-k-1)/ 2;  
                if (j<m&&j>0&&k<j) f[i+1][j+1][k+1]+=f[i][j][k]*(m-j)*(j-k);  
            }  
        }  
    }  
    long long ans=0;  
    for (int i=0;i<=m;i++)  
    {  
        for (int j=0;j<=i;j++)  
        {  
            ans+=f[n][i][j];  
            if (ans>=9999973) ans%=9999973;  
        }  
    }  
    printf("%d",(int)ans);  
    return 0;  
}