luogu 2051 中国象棋

时间：2023-03-08 16:16:24

非常好的dp，锻炼思维

f[i][j][k] 前i行有j列放1，k列放2

#include<bits/stdc++.h>

#define int long long

#define rep(i,x,y) for(register int i=x;i<=y;i++)

#define dec(i,x,y) for(register int i=x;i>=y;i--)

using namespace std;

const int mod=;

const int N=;

inline int read(){

    int x=,f=;char ch=getchar();

    while(!isdigit(ch)){if(ch=='-')f=-;ch=getchar();}

    while(isdigit(ch)){x=(x<<)+(x<<)+(ch^);ch=getchar();}

    return x*f;}

int f[N][N][N],n,m;

inline int C(int x){return x*(x-)/;}

signed main(){

    freopen("count.in","r",stdin);

    freopen("count.out","w",stdout);

    n=read();m=read();

    f[][][]=;

    for(int i=;i<n;i++)

    for(int j=;j<=m;j++)

    for(int k=;j+k<=m;k++){

        //不放

        f[i+][j][k]=(f[i+][j][k]+f[i][j][k])%mod;

        //放1在0

        if(m-j-k>=) f[i+][j+][k]=(f[i+][j+][k]+f[i][j][k]*(m-j-k))%mod;

        //放1在1

        if(j>=) f[i+][j-][k+]=(f[i+][j-][k+]+f[i][j][k]*j)%mod;

        //放2在0在0

        if(m-j-k>=) f[i+][j+][k]=(f[i+][j+][k]+f[i][j][k]*C(m-j-k))%mod;

        //放2在0在1

        if(m-j-k>=&&j>=) f[i+][j][k+]=(f[i+][j][k+]+f[i][j][k]*(m-j-k)*j)%mod;

        //放2在1在1

        if(j>=) f[i+][j-][k+]=(f[i+][j-][k+]+f[i][j][k]*C(j))%mod;}

    int ans=;

    for(int i=;i<=m;i++)

    for(int j=;i+j<=m;j++)

        ans=(ans+f[n][i][j])%mod;

    printf("%lld\n",ans);return ;

}

相关文章