【刷题】【dp】中国象棋

这次小可可想解决的难题和中国象棋有关，

在一个N行M列的棋盘上，让你放若干个炮（可以是0个），

使得没有一个炮可以攻击到另一个炮，请问有多少种放置方法。

大家肯定很清楚，在中国象棋中炮的行走方式是：一个炮攻击到另一个炮，当且仅当它们在同一行或同一列中，且它们之间恰好 有一个棋子。

转换题目：

每行最多只能放两个棋子，求方案数

进一步发现：

找到无关量，减少重复子问题的计算

每一行的摆放其实无所谓，我把各行各列，交换，都无所谓

于是设计出神奇的状态：

f[n][i][j]：n行，有i列有1个炮，j列有2个炮

#include<cstdio>
#include<cstdlib>
#define ll long long 
using namespace std;
int n,m;
const int N=103,mod=9999973;
ll f[N][N][N],ans;

int main()
{
    scanf("%d%d",&n,&m);
    
    f[0][0][0]=1;
     for(int i=0;i<n;i++)
        for(int j=0;j<=m;j++)
            for(int k=0;j+k<=m;k++)
            {
                if(!f[i][j][k]) continue;
                
                if(j+1<=m)
                    f[i+1][j+1][k]=( f[i+1][j+1][k] + f[i][j][k]*(m-j-k)%mod )%mod ;
                if(j+2<=m)    
                    f[i+1][j+2][k]=( f[i+1][j+2][k] + f[i][j][k]*(m-j-k)*(m-j-k-1)/2%mod )%mod ;
                
                if(j>=1 && k+1<=m )
                    f[i+1][j-1][k+1]=( f[i+1][j-1][k+1] + f[i][j][k]*j %mod )%mod ;
                if(j>=2 && k+2<=m )
                    f[i+1][j-2][k+2]=( f[i+1][j-2][k+2] + f[i][j][k]*j*(j-1)/2 %mod )%mod ;
                
                if(j>=1 && k+1<=m ) 
                    f[i+1][j][k+1]=( f[i+1][j][k+1] + f[i][j][k]*(m-j-k)*j%mod )%mod;
                f[i+1][j][k]=( f[i+1][j][k] + f[i][j][k] )%mod ;
            }
    for(int j=0;j<=m;j++)
        for(int k=0;k+j<=m;k++)
            ans=(ans+f[n][j][k])%mod;
    printf("%lld
",ans);
    return 0;
}