当前位置:网站首页>P2051 [AHOI2009]中国象棋

P2051 [AHOI2009]中国象棋

2021-06-25 08:37:11 圩纥

题目描述

这次小可可想解决的难题和中国象棋有关,在一个N行M列的棋盘上,让你放若干个炮(可以是0个),使得没有一个炮可以***到另一个炮,请问有多少种放置方法。大家肯定很清楚,在中国象棋中炮的行走方式是:一个炮***到另一个炮,当且仅当它们在同一行或同一列中,且它们之间恰好 有一个棋子。你也来和小可可一起锻炼一下思维吧!

输入输出格式

输入格式:

一行包含两个整数N,M,之间由一个空格隔开。

输出格式:

总共的方案数,由于该值可能很大,只需给出方案数模9999973的结果。

输入输出样例

输入样例#1: 
1 3
输出样例#1: 
7

说明

样例说明

除了3个格子里都塞满了炮以外,其它方案都是可行的,所以一共有2*2*2-1=7种方案。

数据范围

100%的数据中N和M均不超过100

50%的数据中N和M至少有一个数不超过8

30%的数据中N和M均不超过6

 

Solution:

  本题DP,思路也是ZYYS。

  一个很显然的性质:同一行或者同一列最多只能放两个炮。

  那么根据该性质,考虑计数类DP,定义状态$f[i][j][k]$表示前$i$行有$j$列放一个炮有$k$列放两个炮的方案数。

  转移时考虑一下情况:

    1、当前行不放棋子;

    2、当前行放$1$个棋子在空的列上;

    3、当前行放$1$个棋子在已经放了$1$个棋子的列上;

    4、当前行放$2$个棋子在空的列上;

    5、当前行放$2$个棋子,一个在空的列上,一个在已经放了$1$个棋子的列上;

    6、当前行放$2$个棋子,都在已经放了$1$个棋子的列上。

  显然转移时还需用下简单组合,最后答案就是前$n$行所有状态的方案数之和。

代码:

/*Code by 520 -- 10.18*/
#include<bits/stdc++.h>
#define il inline
#define ll long long
#define RE register
#define For(i,a,b) for(RE int (i)=(a);(i)<=(b);(i)++)
#define Bor(i,a,b) for(RE int (i)=(b);(i)>=(a);(i)--)
using namespace std;
const int mod=9999973,N=105;
int n,m;
ll ans,f[N][N][N];
il ll calc(ll x){return x*(x-1)/2;}

int main(){
    ios::sync_with_stdio(0);
    cin>>n>>m; f[0][0][0]=1;
    For(i,1,n) For(j,0,m) for(RE int k=0;j+k<=m;k++)
    if(f[i-1][j][k]){
        (f[i][j][k]+=f[i-1][j][k])%=mod;
        if(m-j-k>=1) (f[i][j+1][k]+=f[i-1][j][k]*(m-j-k)%mod)%=mod;
        if(j>=1) (f[i][j-1][k+1]+=f[i-1][j][k]*j%mod)%=mod;
        if(m-j-k>=2) (f[i][j+2][k]+=f[i-1][j][k]*calc(m-j-k)%mod)%=mod;
        if(m-j-k>=1&&j>=1) (f[i][j][k+1]+=f[i-1][j][k]*(m-j-k)*j%mod)%=mod;
        if(j>=2) (f[i][j-2][k+2]+=f[i-1][j][k]*calc(j)%mod)%=mod;
    }
    For(i,0,m) for(RE int j=0;i+j<=m;j++) (ans+=f[n][i][j])%=mod;
    cout<<ans;
    return 0;
}    

 

 
 
 
 
 
 

版权声明
本文为[圩纥]所创,转载请带上原文链接,感谢
https://blog.51cto.com/u_15180869/2798645