10.10T6 计数DP（神奇的状态）

Description

　　这次小可可想解决的难题和中国象棋有关，在一个N行M列的棋盘上，让你放若干个炮（可以是0个），使得没有一个炮可以攻击到另一个炮，请问有多少种放置方法。大家肯定很清楚，在中国象棋中炮的行走方式是：一个炮攻击到另一个炮，当且仅当它们在同一行或同一列中，且它们之间恰好 有一个棋子。你也来和小可可一起锻炼一下思维吧！

Input

　　一行包含两个整数N，M，之间由一个空格隔开。

Output

　　总共的方案数，由于该值可能很大，只需给出方案数模9999973的结果。

Sample Input

1 3

Sample Output

7

Hint

【样例说明】
　　除了3个格子里都塞满了炮以外，其它方案都是可行的，所以一共有2*2*2-1=7种方案。
【数据规模】
　　100%的数据中N和M不超过100
　　50%的数据中N和M至少有一个数不超过8
　　30%的数据中N和M均不超过6

 

 

 

 

 

神奇的状态f[i][j][k]代表前 i 行中 j 列没放棋子，k列放1个棋子，m-j-k列放了两个棋子

然后分类讨论1个2个的情况，具体在代码里面，不再赘述

为什么只讨论到两个。。。。因为一行最多放两个。。。

太神奇了

code：

#include<iostream>
#include<cstdio>
using namespace std;
long long f[101][300][301],ans;
int main(){
    long long n,m;
    cin>>n>>m;
    f[0][m][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=m;j++){
            for(int k=0;k+j<=m;k++){
                f[i][j][k]+=f[i-1][j][k];//不放
                if(k)f[i][j][k]+=f[i-1][j+1][k-1]*(j+1);//一个放在原来没有的地方，0个减少，1个增多 
                if(m-k-j)f[i][j][k]+=f[i-1][j][k+1]*(k+1);// 放在原来有1个的上面，1个减少，2个增加 
                if(k&&(m-k-j))f[i][j][k]+=f[i-1][j+1][k]*(j+1)*k;//一个放在没有的地方，一个放在1个的地方 
                if(m-j-k>=2)f[i][j][k]+=f[i-1][j][k+2]*(k+2)*(k+1)/2;//两个都放在1的地方 
                if(k>=2)f[i][j][k]+=f[i-1][j+2][k-2]*(j+2)*(j+1)/2;//两个都放在没有的地方 
                f[i][j][k]%=9999973;
            }
        }
    }
    for(int j=0;j<=m;j++){
        for(int k=0;j+k<=m;k++){
            ans+=f[n][j][k];
            ans%=9999973;
        }
    }
    cout<<ans<<endl;
}

over