HDU 4372 Count the Buildings
2024-08-31 13:36:17
Count the Buildings
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 2521 Accepted Submission(s):
817
Problem Description
There are N buildings standing in a straight line in
the City, numbered from 1 to N. The heights of all the buildings are distinct
and between 1 and N. You can see F buildings when you standing in front of the
first building and looking forward, and B buildings when you are behind the last
building and looking backward. A building can be seen if the building is higher
than any building between you and it.
Now, given N, F, B, your task is to
figure out how many ways all the buildings can be.
the City, numbered from 1 to N. The heights of all the buildings are distinct
and between 1 and N. You can see F buildings when you standing in front of the
first building and looking forward, and B buildings when you are behind the last
building and looking backward. A building can be seen if the building is higher
than any building between you and it.
Now, given N, F, B, your task is to
figure out how many ways all the buildings can be.
Input
First line of the input is a single integer T
(T<=100000), indicating there are T test cases followed.
Next T lines,
each line consists of three integer N, F, B, (0<N, F, B<=2000) described
above.
(T<=100000), indicating there are T test cases followed.
Next T lines,
each line consists of three integer N, F, B, (0<N, F, B<=2000) described
above.
Output
For each case, you should output the number of ways mod
1000000007(1e9+7).
1000000007(1e9+7).
Sample Input
2
3 2 2
3 2 1
3 2 2
3 2 1
Sample Output
2
1
1
Source
Recommend
zhuyuanchen520 | We have carefully selected several
similar problems for you: 4059 2819 1730 2176 1850
similar problems for you: 4059 2819 1730 2176 1850
实在搞不懂HDU的脾气啊。
为什么交G++会RE????
这道题的话。
不管是从左边看还是从右边看,视线总是会被中间最高的给挡住
所以我们把左边和右边分组来看。
对于某一边,我们确定出能够看见的楼房,那么不能够看见的楼房就可以任意排列
我们把能看见的楼房,与下一个能看到的楼房(不包括下一个楼房)之间的楼看为一组
那么组内的元素就可以任意排,假设一组有$n$个楼房,那么它们自由排列的方案数就是$(n-1)!$
这会让你联想的到什么?
哈哈没错,第一类斯特灵数(神TM能想到)
这样我们就可以首先对所有的楼房进行分组,然后再让他们自由排列
一共有$F-1+B-1$组
#include<iostream>
#include<cstdio>
#define LL long long
using namespace std;
const LL MAXN=*1e6+;
LL T,N,F,B;
LL mod=;
LL c[][],s[][];
int main()
{
for(LL i=;i<=;i++)
{
c[i][]=;
c[i][i]=;
s[i][]=;//无法频出环
s[i][i]=;//只能拼出一个环
for(LL j=;j<i;j++)
c[i][j]=(c[i-][j-]%mod+c[i-][j]%mod)%mod,
s[i][j]=(s[i-][j-]%mod+(i-)%mod*s[i-][j]%mod)%mod;
}
scanf("%I64d",&T);
while(T--)
{
scanf("%I64d%I64d%I64d",&N,&F,&B);
printf("%I64d\n",(c[F-+B-][F-]%mod*s[N-][F-+B-]%mod)%mod);
}
return ;
}
最新文章
- Linux 进程间通讯详解七
- c# 获取某日期所在周的第一天和最后一天
- JavaScript中使用typeof运算符需要注意的几个坑
- 网站CSS选择器性能讨论
- eclipse如何修改dynamic web module version
- poj1266Cover an Arc(三角形外接圆)
- 转:打造DropDownList,TreeView,ListBox无限极分类目录树
- Esper系列(六)子查询、Exists、In/not in、Any/Some、Join
- owncloud乱码问题
- MVC和传统的以模板为中心的web架构比较
- gridview回顾
- 断开/删除 SVN 链接(.svn)的几种方法
- 初学 Python(十五)——装饰器
- Kotlin——最详细的数据类型介绍
- Spring事务不回滚原因分析
- 织梦默认编辑器 按下回车生成br标签改为生成p标签
- filebeat 收集的进度日志查看
- JDK8 新增的日期时间API
- spring源码分析系列
- 第 3 章 镜像 - 017 - RUN vs CMD vs ENTRYPOINT