洛谷 - P2051 - 中国象棋

https://www.luogu.org/problemnew/show/P2051
一点都不简单的简单dp。
还是从旧行转移到新行，而不是考虑新行从哪些旧行转移吧。
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

namespace combinatorics{

    const ll MOD=9999973;

    //1. 快速幂 x^n %mod

    inline ll qpow(ll x,ll n,ll mod=MOD) {

        ll res=1%mod;

        while(n) {

            if(n&1)

                res=res*x%mod;

            x=x*x%mod;

            n>>=1;

        }

        return res;

    }

    //3. 乘法逆元 快速幂+费马小定理，要求p必须是质数 （依赖1. 快速幂）

    inline ll inv_p(ll n,ll p=MOD) {

        return qpow(n,p-2,p);

    }

};

using namespace combinatorics;

//注意需要init(),必要时修改常量

ll dp[101][101][101]={};

//前i行中，j列放了1个，k列放了2个的方法数

int main(){

    int n,m;

    scanf("%d%d",&n,&m);

    ll inv2=inv_p(2,MOD);

    dp[1][0][0]=1;

    //不放也是一种方法

    dp[1][1][0]=m;

    //只有1列放了1个

    if(m>=2)

        dp[1][2][0]=(ll)m*(m-1)%MOD*inv2%MOD;

    //只有2列放了1个

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

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

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

                //这一行不放

                dp[i+1][j][k]=(dp[i+1][j][k]+dp[i][j][k])%MOD;

                int v=m-j-k;

                //放一个在空列，有v种放法

                if(v-1>=0&&j+1<=m)

                    dp[i+1][j+1][k]=(dp[i+1][j+1][k]+dp[i][j][k]*v)%MOD;

                //放一个在原本有1个的列，有j种方法

                if(j-1>=0&&k+1<=m)

                    dp[i+1][j-1][k+1]=(dp[i+1][j-1][k+1]+dp[i][j][k]*j)%MOD;

                //放两个，两个都在空列

                if(v-2>=0&&j+2<=m)

                    dp[i+1][j+2][k]=(dp[i+1][j+2][k]+dp[i][j][k]*(v)*(v-1)*inv2)%MOD;

                //放两个，两个都在原本有1个的列

                if(j-2>=0&&k+2<=m)

                    dp[i+1][j-2][k+2]=(dp[i+1][j-2][k+2]+dp[i][j][k]*(j)*(j-1)*inv2)%MOD;

                //放两个，一个在空列，一个在原本有1个的列

                if(v-1>=0&&k+1<=m)

                    dp[i+1][j][k+1]=(dp[i+1][j][k+1]+dp[i][j][k]*v*j)%MOD;

                //printf("dp[%d][%d][%d]=%lld\n",i,j,k,dp[i%2][j][k]);

            }

        }

    }

    //puts("");

    ll ans=0;

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

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

            ans=(ans+dp[n][j][k])%MOD;

            //printf("dp[%d][%d][%d]=%lld\n",n,j,k,dp[n%2][j][k]);

        }

    }

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

}
巴特西

洛谷 - P2051 - 中国象棋 - 简单dp

最新文章

热门文章
