BZOJ——T 1801: [Ahoi2009]chess 中国象棋
2024-09-06 02:29:54
http://www.lydsy.com/JudgeOnline/problem.php?id=1801
Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 1936 Solved: 1120
[Submit][Status][Discuss]
Description
在N行M列的棋盘上,放若干个炮可以是0个,使得没有任何一个炮可以攻击另一个炮。 请问有多少种放置方法,中国像棋中炮的行走方式大家应该很清楚吧.
Input
一行包含两个整数N,M,中间用空格分开.
Output
输出所有的方案数,由于值比较大,输出其mod 9999973
Sample Input
1 3
Sample Output
7
HINT
除了在3个格子中都放满炮的的情况外,其它的都可以.
100%的数据中N,M不超过100
50%的数据中,N,M至少有一个数不超过8
30%的数据中,N,M均不超过6
Source
#include <cstdlib>
#include <cstdio> const int mod();
const int N();
inline void read(int &x)
{
x=; register char ch=getchar();
for(; ch>''||ch<''; ) ch=getchar();
for(; ch>=''&&ch<=''; ch=getchar()) x=x*+ch-'';
}
int n,m,map[N][N];
long long f[N][N][N];
inline long long C(long long x)
{
return x*(x-)>>;
} int Presist()
{
read(n),read(m);
f[][][]=;
for(int i=; i<=n; ++i)
for(int j=; j<=m; ++j)
for(int k=; k+j<=m; ++k)
{
f[i][j][k]=f[i-][j][k]; f[i][j][k]%=mod; //此行不放炮
if(j) f[i][j][k]=(f[i][j][k]+f[i-][j-][k]* (m-j+-k))%mod; //该行没有炮的一列放一炮
if(k) f[i][j][k]=(f[i][j][k]+f[i-][j+][k-]* (j+))%mod; //该行有一个炮的一列放一炮
if(j>) f[i][j][k]=(f[i][j][k]+f[i-][j-][k]* C(m-j+-k))%mod; //没有炮的两列各方一个炮
if(k>) f[i][j][k]=(f[i][j][k]+f[i-][j+][k-]* C(j+))%mod; //该行在有一个炮的两列各放一个炮
if(k) f[i][j][k]=(f[i][j][k]+f[i-][j][k-]* j*(m-j-k+))%mod; //该行在无炮的位置放一个炮,在有一个炮的一列再放一个跑
}
long long ans=;
for(int i=; i<=m; ++i)
for(int j=; i+j<=m; ++j)
ans+=f[n][i][j],ans%=mod;
printf("%lld\n",ans);
return ;
} int Aptal=Presist();
int main(){;}
最新文章
- spring mvc 中文参数乱码
- 数据持久化以及DAO模式的简单使用
- 實際案例: 獲取臨時票証 (JsApi Ticket)
- mysql sql_safe_updates 不支持子查询的更新。
- 点击div折叠
- C#的is和as操作符来进行强制类型转换&;&;值类型的拆箱、装箱
- express-17 持久化
- Linux下安装php加速器xcache
- 关于C#读取MySql数据时,返回DataTable中某字段数据是System.Array[]形式
- 制衡技术,从Adblock所想到的
- SSAS 聚合设计提升CUBE的查询性能(转载)
- spark streaming 实现接收网络传输数据进行WordCount功能
- hdu5443(2015长春赛区网络赛1007)暴力
- (转)RSA算法原理
- 4位bcd数转换为2进制数
- MyBatis映射文件的resultMap如何做表关联
- Java中对象的三种状态
- IronPython初体验和实战集合等类型转换和类型匹配
- app 转caf 音频 代码
- 清除在Windows下访问共享文件夹时的登录信息
热门文章
- struts2什么情况用#和EL表达示
- codevs1486愚蠢的矿工(树形dp)
- Django day30 自定义配置settings文件,分页器,版本控制
- C# 针对文件夹的操作
- 在chrome里模拟调试微信浏览器
- 327 Count of Range Sum 区间和计数
- 常用的Axure操作方法(1)
- 【深度学习笔记】(一)Mac下TensorFlow安装及环境搭建
- Moto P30(XT1943-1) 免解锁BL 免rec 保留数据 Magisk Xposed ROOT 救砖 ZUI 4.0.374
- html5——伸缩比例