随便's Blog

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

 

一道DP 开始向一般的状态压缩DP ，结果数组开不下。。。

用两维分别表示有两个棋子的列数和一个棋子的列数，没有棋子的可以用总列数减去其余两种；

分了5种转移的情况：

1.一个棋子的加一个；

2.零个棋子的加一个；

3.两列一个棋子的分别加一；

4.两列零个棋子分别加一；

5.一列零个棋子一列一个棋子分别加一；

分情况转移就行了。

/**************************************************************
    Problem: 1801
    User: 1115825064
    Language: C++
    Result: Accepted
    Time:292 ms
    Memory:1444 kb
****************************************************************/
 
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
 
using namespace std;
 
long long f[2][105][105];
 
int n,m;
const int mod=9999973;
 
int main()
{
//  freopen("1.txt","r",stdin);
    scanf("%d%d",&n,&m);
    f[0][0][0]=1;
    for(int i=0;i<n;++i)
    {
        memset(f[~i&1],0,sizeof(f[i&1]));
        for(int j=0;j<=m;++j)
            for(int k=0;k+j<=m;++k)
            {
                int l=m-k-j;
                 
                f[~i&1][j][k]+=f[i&1][j][k],f[~i&1][j][k]%=mod;
                if(j>1)f[~i&1][j-2][k+2]+=(f[i&1][j][k]*j*(j-1))/2,f[~i&1][j-2][k+2]%=mod;
                if(j>0)f[~i&1][j-1][k+1]+=f[i&1][j][k]*j,f[~i&1][j-1][k+1]%=mod; 
                if(l>0)f[~i&1][j+1][k]+=f[i&1][j][k]*l,f[~i&1][j+1][k]%=mod;
                if(l>1)f[~i&1][j+2][k]+=(f[i&1][j][k]*l*(l-1))/2,f[~i&1][j+2][k]%=mod;
                if(l>0&&j>0)f[~i&1][j][k+1]+=f[i&1][j][k]*l*j,f[~i&1][j][k+1]%=mod;
            }
    }
    long long ans=0;
    for(int j=0;j<=m;++j)
        for(int k=0;k+j<=m;++k)
        {
            ans+=f[n&1][j][k];
            ans%=mod;
        }
    printf("%lld",ans);
    return 0;
}