[BZOJ1801/Luogu2051][Ahoi2009]chess 中国象棋(动态规划)

发布于 2018-02-16  108 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ1801/Luogu2051][Ahoi2009]chess 中国象棋(动态规划)

Description

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

Http

BZOJ
Luogu

Tag

动态规划

解决思路

考虑中国象棋中炮的攻击方式,发现其实就是要求任意一行或任意一列不能摆放超过两个炮。并且我们发现,每一个炮具体摆的位置不影响最后的结果,只贡献组合数。那么我们枚举行,考虑列。
设\(F[i][j][k]\)表示当前处理到第\(i\)行,前\(i\)行中,一个炮都没有的列有\(j\)个,只有一个炮的列有\(k\)个,分别转移。
首先,这一行可以什么也不摆,那就直接转移到\(F[i+1][j][k]\)。
可以选择摆一个炮,那么这个炮可以摆在原来一个炮都没有的某一列,转移到\(F[i+1][j-1]\[k+1]\),并乘上方案数\(j\);同理,这一个炮也可以摆在原来已经有一个炮的某一列上,转移到\(F[i+1][j][k-1]\),并乘上方案数\(k\)。
那么摆两个炮的也是同理,分为两个都摆在原来一个炮丢没有的列上、两个都摆在原来已经有一个的列上和一个在没有一个在已经有一个的列上,这三种情况讨论,乘上对应的系数。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=101;
const int Mod=9999973;
const int inf=2147483647;

int n,m;
ll F[maxN][maxN][maxN];

ll QPow(ll x,ll cnt);

int main()
{
    int inv2=QPow(2,Mod-2);
    scanf("%d%d",&n,&m);
    F[0][m][0]=1;
    for (ll i=0;i<n;i++)
        for (ll p1=0;p1<=m;p1++)
            for (ll p2=0;p1+p2<=m;p2++)
            {
                if (F[i][p1][p2]==0) continue;
                F[i+1][p1][p2]=(F[i+1][p1][p2]+F[i][p1][p2])%Mod;//什么都不放
                if (p1>=1) F[i+1][p1-1][p2+1]=(F[i+1][p1-1][p2+1]+F[i][p1][p2]*(ll)p1%Mod)%Mod;//在空的某一列摆上一个
                if (p2>=1) F[i+1][p1][p2-1]=(F[i+1][p1][p2-1]+F[i][p1][p2]*(ll)p2%Mod)%Mod;//在有一个的某一列摆上一个
                if (p1>=2) F[i+1][p1-2][p2+2]=(F[i+1][p1-2][p2+2]+1ll*F[i][p1][p2]*p1%Mod*(p1-1ll)%Mod*inv2%Mod)%Mod;//在两列空的上面分别摆上一个
                if (p2>=2) F[i+1][p1][p2-2]=(F[i+1][p1][p2-2]+1ll*F[i][p1][p2]*p2%Mod*(p2-1ll)%Mod*inv2%Mod)%Mod;//在两个已经摆了一个的上面再分别摆一个
                if ((p1>=1)&&(p2>=1)) F[i+1][p1-1][p2]=(F[i+1][p1-1][p2]+1ll*F[i][p1][p2]*p1%Mod*p2%Mod)%Mod;//在空列和摆了一个的一列摆上一个
            }
    int Ans=0;
    for (int p1=0;p1<=m;p1++)
        for (int p2=0;p1+p2<=m;p2++)
            Ans=(Ans+F[n][p1][p2])%Mod;
    printf("%d\n",Ans);
    return 0;
}

ll QPow(ll x,ll cnt)
{
    ll ret=1;
    while (cnt)
    {
        if (cnt&1) ret=ret*x%Mod;
        x=x*x%Mod;
        cnt=cnt>>1;
    }
    return ret;
}

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ1801/Luogu2051][Ahoi2009]chess 中国象棋(动态规划)


HNCJ OIer