首页 > 其他 > 详细

【JZOJ1667】【BZOJ1801】【luoguP2051】中国象棋

时间:2019-09-17 17:51:19      阅读:92      评论:0      收藏:0      [点我收藏+]

description

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


analysis

  • \(DP\),容易知道每行至多有两个炮,否则会互相打到

  • \(f[i][j][k]\)表示到放到第\(i\)行,有\(j\)列放了一个炮,\(k\)列放了两个炮的方案数

  • 该行不放炮,则直接继承上一行的答案

\[f[i][j][k]+=f[i-1][j][k]\]

  • 一个炮放在没有炮的列上,一个炮的列数\(+1\),且有\(m-k-(j-1)\)个没有炮的列可以放

\[f[i][j][k]+=f[i-1][j-1][k]*[m-k-(j-1)]\]

  • 一个炮放在一个炮的列上,一个炮的列数\(-1\),两个炮的列数\(+1\),且有\(j+1\)个一个炮的列可以放

\[f[i][j][k]+=f[i-1][j+1][k-1]*(j+1)\]

  • 一个炮放在一个炮的列上,一个炮放在没有炮的列上,两个炮的列数\(+1\),且分别有\(j\)列、\(m-(k-1)-j\)列可以放

\[f[i][j][k]+=f[i-1][j][k-1]*j*[m-(k-1)-j]\]

  • 两个炮放在没有炮的列上,一个炮的列数\(+2\),且有\(C^{2}_{m-(j-2)-k}\)种方案

\[f[i][j][k]+=f[i-1][j-2][k]*C^{2}_{m-(j-2)-k}\]

  • 两个炮放在一个炮的列上,一个炮的列数\(-2\),两个炮的列数\(+2\),且有\(C^{2}_{j+2}\)种方案

\[f[i][j][k]+=f[i-1][j+2][k-2]*C^{2}_{j+2}\]

  • 如此转移即可,注意判断边界

code

#pragma GCC optimize("O3")
#pragma G++ optimize("O3")
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define MAXN 105
#define ha 9999973
#define ll long long
#define reg register ll
#define fo(i,a,b) for (reg i=a;i<=b;++i)
#define fd(i,a,b) for (reg i=a;i>=b;--i)

using namespace std;

ll f[MAXN][MAXN][MAXN];
ll c[MAXN][MAXN];
ll n,m,ans;

inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while (ch<'0' || '9'<ch){if (ch=='-')f=-1;ch=getchar();}
    while ('0'<=ch && ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*f;
}
inline ll C(ll n){return n*(n-1)/2;}
int main()
{
    n=read(),m=read(),f[0][0][0]=1;
    fo(i,1,n)
    {
        fo(j,0,m)
        {
            fo(k,0,m-j)
            {
                f[i][j][k]=f[i-1][j][k];//不填
                if (k-1>=0)
                    (f[i][j][k]+=f[i-1][j+1][k-1]*(j+1)%ha)%=ha;//一颗填一个炮的列
                if (j-1>=0)         
                    (f[i][j][k]+=f[i-1][j-1][k]*(m-(j-1)-k))%=ha;//一颗填没有炮的列
                if (k-1>=0)
                    (f[i][j][k]+=f[i-1][j][k-1]*j%ha*(m-j-(k-1)))%=ha;//一颗填一个炮的列,一颗填没有炮的列
                if (j-2>=0)
                    (f[i][j][k]+=f[i-1][j-2][k]*C(m-(j-2)-k))%=ha;//两颗填没有炮的列
                if (k-2>=0)
                    (f[i][j][k]+=f[i-1][j+2][k-2]*C(j+2))%=ha;//两颗填一个炮的列
            }
        }
    }
    fo(i,0,m)fo(j,0,m-i)(ans+=f[n][i][j])%=ha;
    printf("%lld\n",ans);
    return 0;
}

【JZOJ1667】【BZOJ1801】【luoguP2051】中国象棋

原文:https://www.cnblogs.com/horizonwd/p/11535731.html

(1)
(1)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!