有n(<=2000)栋楼排成一排,高度恰好是1至n且两两不同。现在从左侧看能看到f栋,从右边看能看到b栋,问有多少种可能方案。
T组数据, (T<=100000)
自己只想出了用DP搞
发现最高的楼一定能看到,分成了左右两个问题
f[i][j]表示i栋楼从左面可以看到j栋方案数,转移枚举最高楼左面有几栋楼,乘上个组合数和剩下的排列
问题是DP完了求ans需要O(n)枚举最高楼在哪........
然后发现好多人用了第一类sirtling数
考虑一栋被看到的楼,它会挡住它右面的几栋楼,这几栋楼可以任意排列都不会被看到
我们把这样作为一组,然后发现去掉最高的楼后左面需要f-1组,右面需要b-1组
一个组的最高元素必须在最左面,发现这样意味着是循环同构的(一种循环只有最高在最左合法),就是第一类sirtling数啊
$ans={{f+b-2}\choose {f-1}}*s(n-1,f+b-2)$
然后本题G++迷之RE
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int N=,MOD=1e9+;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
int n,f,b;
int c[N][N],s[N][N];
void ini(int n){
c[][]=;
for(int i=;i<=n;i++){
c[i][]=c[i][i]=;
for(int j=;j<i;j++) c[i][j]=(c[i-][j]+c[i-][j-])%MOD;
}
s[][]=;
for(int i=;i<=n;i++){
s[i][i]=;
for(int j=;j<i;j++) s[i][j]=(s[i-][j-]+(ll)s[i-][j]*(i-)%MOD)%MOD;
}
} int main(){
freopen("in","r",stdin);
int T=read();
ini();
while(T--){
n=read();f=read();b=read();
printf("%lld\n",(ll)c[f+b-][f-]*s[n-][f+b-]%MOD);
}
}
HDU 4372 Count the Buildings [第一类斯特林数]的更多相关文章
-
HDU 4372 Count the Buildings——第一类斯特林数
题目大意:n幢楼,从左边能看见f幢楼,右边能看见b幢楼 楼高是1~n的排列. 问楼的可能情况 把握看到楼的本质! 最高的一定能看见! 计数问题要向组合数学或者dp靠拢.但是这个题询问又很多,难以dp ...
-
hdu 4372 Count the Buildings 轮换斯特林数
题目大意 n栋楼有n个不同的高度 现在限制从前面看有F个点,后面看有B个点 分析 最高那栋楼哪都可以看到 剩下的可以最高那栋楼前面分出F-1个组 后面分出B-1个组 每个组的权值定义为组内最高楼的高度 ...
-
【HDU 4372】 Count the Buildings (第一类斯特林数)
Count the Buildings Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Othe ...
-
[HDU 3625]Examining the Rooms (第一类斯特林数)
[HDU 3625]Examining the Rooms (第一类斯特林数) 题面 有n个房间,每个房间有一个钥匙,钥匙等概率的出现在n个房间内,每个房间中只会出现且仅出现一个钥匙.你能炸开门k次, ...
-
hdu 4372 Count the Buildings —— 思路+第一类斯特林数
题目:http://acm.hdu.edu.cn/showproblem.php?pid=4372 首先,最高的会被看见: 然后考虑剩下 \( x+y-2 \) 个被看见的,每个带了一群被它挡住的楼, ...
-
hdu 3625 Examining the Rooms —— 第一类斯特林数
题目:http://acm.hdu.edu.cn/showproblem.php?pid=3625 学习斯特林数:https://blog.csdn.net/qq_33229466/article/d ...
-
HDU 4372 Count the Buildings:第一类Stirling数
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4372 题意: 有n栋高楼横着排成一排,各自的高度为1到n的一个排列. 从左边看可以看到f栋楼,从右边看 ...
-
HDU 4372 Count the Buildings
Count the Buildings Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Othe ...
-
hdu 3625 Examining the Rooms——第一类斯特林数
题目:http://acm.hdu.edu.cn/showproblem.php?pid=3625 n^2 求斯特林数就行.要减去的就是1号钥匙在1号房间的方案,即 s[ n-1 ][ m-1] . ...
随机推荐
-
mysql 5.5多实例部署【图解】
mysql5.5数据库多实例部署,我们可以分以下几个步骤来完成. 1. mysql多实例的原理 2. mysql多实例的特点 3. mysql多实例应用场景 4. mysql5.5多实例部署方法 一. ...
-
IIS6.0部署asp.net网站步骤图解
IIS 发布步骤 1, 程序->运行->输入inetmgr,打开IIS管理器; 2, 展开左侧树形目录->右击“网站”->新建->网站,打开网站创建向导; 3, 点击“下 ...
-
两种数据传输的方式——get和post。
Form提供了两种数据传输的方式——get和post.虽然它们都是数据的提交方式,但是在实际传输时确有很大的不同,并且可能会对数据产生严重的影响.虽然为了方便的得到变量值,Web容器已经屏蔽了二者的一 ...
-
初识 .net core和vs code
定义:什么是.net core? .net core是一个跨各个不同操作系统运行的平台.时至今日,windows上.net framework已经发展成熟,可以用来开发windows平台下的几乎所有应 ...
-
空间数据可视化:1. 3D_Bar图表| 空间柱状图
1.Sublime的使用 中文版的配置 https://jingyan.baidu.com/article/ca2d939d1e83feeb6c31cefc.html (百度经验) sublime里边 ...
-
根据23423条件,截取字段‘abdecsdsadsadsad’,以ab/dec/sdsa/ds/ads 输出
create or replace procedure p_getString ( p_finalString out varchar2, p_rulestring in number, p_sour ...
-
【BZOJ】【2750】【HAOI2012】Road
最短路+拓扑序DP orz zyf & lyd 统计每条边在多少条最短路径上……其实可以统计 有多少条最短路径经过了x,以及y出发到达任意一个结束点有多少种走法(沿最短路) 我们可以用Dijk ...
-
Mysql 知识点总结
1.创建数据库 mysqladmin 下面是一个简单的例子,创建名为 yiibai_tutorials1 的数据库. D:\software\mysql--winx64\bin> mysq ...
-
${__BeanShell(${SCRIPT})}
通过将变量名称括在' $ { '和' } '中来引用测试元素中的变量. 函数以相同的方式引用,但按照惯例,函数名称以“ __ ” 开头,以避免与用户值名称冲突*.有些函数使用参数来配置它们,这些函数用 ...
-
MongoDB 创建集合
createCollection() 方法 MongoDB db.createCollection(name, options) 是用来创建集合. 语法: 基本的 createCollection() ...