传送门

BZOJ

洛谷


Description

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


Input

一行包含两个整数NM,中间用空格分开.

Output

输出所有的方案数,由于值比较大,输出其{\rm mod}~9999973


Sample Input

1 3

Sample Output

7

HINT

除了在3个格子中都放满炮的的情况外,其它的都可以.

100 \%的数据中N,M不超过100

50 \%的数据中,N,M至少有一个数不超过8

30 \%的数据中,N,M均不超过6


Solution

我们先考虑暴力分,裸的三进制状压\rm DP,设f_{i,j}表示到第i行,前面列的状态为j(0没有放,1放了一个,2放了两个)的方案数。

考虑满分做法,我们观察部分分做法的转移过程,发现每次仅会选择放的个数不超过一个的列去转移。那么实际上就是找01的位置,但是很显然我们不关系具体位置,我们只需要知道数量便可以转移了。

f_{i,j,k}表示到第i行,有j列只放了一个棋子,有k列放了两个棋子。转移很多,直接看代码吧…

Code

/*Program from Luvwgyx*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=110;
const int mod=9999973;
int f[maxn][maxn][maxn];
int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void print(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10);
    putchar(x%10+'0');
}
void write(int x){print(x);putchar('\n');}
int C(int x){return ((1ll*x*(x-1))/2)%mod;}
void add(int &x,int y){x=(x+y)%mod;}
signed main(){
    int n=read(),m=read(),ans=0;f[0][0][0]=1;
    for(int i=1;i<=n;i++)
        for(int j=0;j<=m;j++)
            for(int k=0;k<=m-j;k++){
                f[i][j][k]=f[i-1][j][k];
                if(k>=1)add(f[i][j][k],1ll*f[i-1][j+1][k-1]*(j+1)%mod);
                if(j>=1)add(f[i][j][k],1ll*f[i-1][j-1][k]*(m-k-j+1)%mod);
                if(j>=2)add(f[i][j][k],1ll*f[i-1][j-2][k]*C(m-j-k+2)%mod);
                if(k>=2)add(f[i][j][k],1ll*f[i-1][j+2][k-2]*C(j+2)%mod);
                if(k>=1)add(f[i][j][k],1ll*f[i-1][j][k-1]*j%mod*(m-j-k+1)%mod);
            }
    for(int j=0;j<=m;j++)for(int k=0;k<=m;k++)add(ans,f[n][j][k]);write(ans);
    return 0;
}

发表评论