天天看點

洛谷2501 BZOJ1801中國象棋題解

題目連結

BZ連結

其實dp隻要把狀态想好後轉移就很好寫了(flag*1)

f[i][j][k]表示到了第i行,有j列放了一個跑,有k列放了兩個跑的方案總數

然後大力讨論,轉移即可

# include<iostream>
# include<cstdio>
# include<algorithm>
# include<cmath>
# include<cstring>
const int mn = 105;
const int mod = 9999973;
int n,m,ans;
int f[mn][mn][mn];
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;k+j<=m;k++)
            {
                f[i+1][j][k]=(f[i+1][j][k]+f[i][j][k])%mod;
                //什麼都不放
                if(j>=1)
                    f[i+1][j-1][k+1]=(f[i+1][j-1][k+1]+1ll*f[i][j][k]*j%mod)%mod;
                //在有跑的一行放一個跑
                if((m-k-j)>=1)
                    f[i+1][j+1][k]=(f[i+1][j+1][k]+1ll*f[i][j][k]*(m-k-j)%mod)%mod;
                //在空地上放一個跑
                if(j>=2)
                    f[i+1][j-2][k+2]=(f[i+1][j-2][k+2]+1ll*f[i][j][k]*(j-1)*j/2%mod)%mod;
                if((m-k-j)>=2)
                    f[i+1][j+2][k]=(f[i+1][j+2][k]+1ll*f[i][j][k]*(m-k-j-1)*(m-k-j)/2%mod)%mod;
                if((m-k-j)>=1 && j>=1)
                    f[i+1][j][k+1]=(f[i+1][j][k+1]+1ll*f[i][j][k]*(m-k-j)*j%mod)%mod;
            }
    for(int i=0;i<=m;i++)
        for(int j=0;j+i<=m;j++)
        ans=(ans+f[n][i][j])%mod;
    printf("%d",ans);
    return 0;
}