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

Day2

 #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(){;}

最新文章

  1. spring mvc 中文参数乱码
  2. 数据持久化以及DAO模式的简单使用
  3. 實際案例: 獲取臨時票証 (JsApi Ticket)
  4. mysql sql_safe_updates 不支持子查询的更新。
  5. 点击div折叠
  6. C#的is和as操作符来进行强制类型转换&amp;&amp;值类型的拆箱、装箱
  7. express-17 持久化
  8. Linux下安装php加速器xcache
  9. 关于C#读取MySql数据时,返回DataTable中某字段数据是System.Array[]形式
  10. 制衡技术,从Adblock所想到的
  11. SSAS 聚合设计提升CUBE的查询性能(转载)
  12. spark streaming 实现接收网络传输数据进行WordCount功能
  13. hdu5443(2015长春赛区网络赛1007)暴力
  14. (转)RSA算法原理
  15. 4位bcd数转换为2进制数
  16. MyBatis映射文件的resultMap如何做表关联
  17. Java中对象的三种状态
  18. IronPython初体验和实战集合等类型转换和类型匹配
  19. app 转caf 音频 代码
  20. 清除在Windows下访问共享文件夹时的登录信息

热门文章

  1. struts2什么情况用#和EL表达示
  2. codevs1486愚蠢的矿工(树形dp)
  3. Django day30 自定义配置settings文件,分页器,版本控制
  4. C# 针对文件夹的操作
  5. 在chrome里模拟调试微信浏览器
  6. 327 Count of Range Sum 区间和计数
  7. 常用的Axure操作方法(1)
  8. 【深度学习笔记】(一)Mac下TensorFlow安装及环境搭建
  9. Moto P30(XT1943-1) 免解锁BL 免rec 保留数据 Magisk Xposed ROOT 救砖 ZUI 4.0.374
  10. html5——伸缩比例