HDU - 6114 2017百度之星初赛B Chess
Chess
車是中国象棋中的一种棋子,它能攻击同一行或同一列中没有其他棋子阻隔的棋子。一天,小度在棋盘上摆起了许多車……他想知道,在一共N×M个点的矩形棋盘中摆最多个数的車使其互不攻击的方案数。他经过思考,得出了答案。但他仍不满足,想增加一个条件:对于任何一个車A,如果有其他一个車B在它的上方(車B行号小于車A),那么車A必须在車B的右边(車A列号大于車B)。
现在要问问你,满足要求的方案数是多少。
第一行一个正整数T,表示数据组数。
对于每组数据:一行,两个正整数N和M(N<=1000,M<=1000)。
对于每组数据输出一行,代表方案数模1000000007(1e9+7)。
1
1 1
1
这题第一反应是搜索,不过看到方案数的范围就知道肯定超时。因为每种方案都是一种排列组合,于是直觉就想到了杨辉三角,索性手写了几个样例,把较小的几种方案列出来,果然找到了规律。
规律:(n,m)方案数 ps:n,m满足对称性
(1,1) (1,2) (1,3) (1,4) (1,5) (1,6)
1 2 3 4 5 6
(2,2) (2,3) (2,4) (2,5) (2,6)
1 3 6 10 15
(3,3) (3,4) (3,5) (3,6)
1 4 10 20
(4,4) (4,5) (4,6)
1 5 15
(5,5) (5,6)
1 6
(6,6)
1
很显然,方案数就是一个倒置的杨辉三角。a[i][j]=a[i-1][j-1]+a[i][j-1]
#include<stdio.h>
#include<stdlib.h> long long a[][]; int main()
{
int t,n,m,i,j;
for(i=;i<=;i++){
a[][i]=;
}
for(i=;i<=;i++){
for(j=i;j<=;j++){
a[i][j]=a[i-][j-]+a[i][j-];
if(a[i][j]>=) a[i][j]%=;
}
}
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
if(n<m) printf("%lld\n",a[n][m]);
else printf("%lld\n",a[m][n]);
}
return ;
}
最新文章
- raw转qcow2
- 《Linux内核设计与实现》课本第十八章自学笔记——20135203齐岳
- Android复习资料
- 点击repeater的一个修改事件触发全部repeater每一行的修改事件
- Activity 的启动模式
- [译]Java 设计模式 之模板方法
- 文本输入框和下拉菜单特效-用正则表达式验证E-mail格式
- Variation of e.touches, e.targetTouches and e.changedTouches
- Django之Model世界
- linux在线安装mysql
- HTML学习笔记01(标签)
- 升级mac自带的python
- html留言功能
- 转载:HBuilder常用快捷键
- Confluence 6 协同编辑问题解决
- Netty 核心组件 Pipeline 源码分析(一)之剖析 pipeline 三巨头
- Digest Authentication 摘要认证
- php webshell常见函数
- 【转载】Eclipse 任务栏锁定问题
- OpenPAI大规模人工智能平台安装部署文档