HDU 4372 Count the Buildings [第一类斯特林数]

时间:2023-02-12 15:04:10

有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 [第一类斯特林数]的更多相关文章

  1. HDU 4372 Count the Buildings——第一类斯特林数

    题目大意:n幢楼,从左边能看见f幢楼,右边能看见b幢楼 楼高是1~n的排列. 问楼的可能情况 把握看到楼的本质! 最高的一定能看见! 计数问题要向组合数学或者dp靠拢.但是这个题询问又很多,难以dp ...

  2. hdu 4372 Count the Buildings 轮换斯特林数

    题目大意 n栋楼有n个不同的高度 现在限制从前面看有F个点,后面看有B个点 分析 最高那栋楼哪都可以看到 剩下的可以最高那栋楼前面分出F-1个组 后面分出B-1个组 每个组的权值定义为组内最高楼的高度 ...

  3. 【HDU 4372】 Count the Buildings &lpar;第一类斯特林数&rpar;

    Count the Buildings Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Othe ...

  4. &lbrack;HDU 3625&rsqb;Examining the Rooms &lpar;第一类斯特林数&rpar;

    [HDU 3625]Examining the Rooms (第一类斯特林数) 题面 有n个房间,每个房间有一个钥匙,钥匙等概率的出现在n个房间内,每个房间中只会出现且仅出现一个钥匙.你能炸开门k次, ...

  5. hdu 4372 Count the Buildings —— 思路&plus;第一类斯特林数

    题目:http://acm.hdu.edu.cn/showproblem.php?pid=4372 首先,最高的会被看见: 然后考虑剩下 \( x+y-2 \) 个被看见的,每个带了一群被它挡住的楼, ...

  6. hdu 3625 Examining the Rooms —— 第一类斯特林数

    题目:http://acm.hdu.edu.cn/showproblem.php?pid=3625 学习斯特林数:https://blog.csdn.net/qq_33229466/article/d ...

  7. HDU 4372 Count the Buildings:第一类Stirling数

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4372 题意: 有n栋高楼横着排成一排,各自的高度为1到n的一个排列. 从左边看可以看到f栋楼,从右边看 ...

  8. HDU 4372 Count the Buildings

    Count the Buildings Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Othe ...

  9. hdu 3625 Examining the Rooms——第一类斯特林数

    题目:http://acm.hdu.edu.cn/showproblem.php?pid=3625 n^2 求斯特林数就行.要减去的就是1号钥匙在1号房间的方案,即 s[ n-1 ][ m-1] . ...

随机推荐

  1. mysql 5&period;5多实例部署【图解】

    mysql5.5数据库多实例部署,我们可以分以下几个步骤来完成. 1. mysql多实例的原理 2. mysql多实例的特点 3. mysql多实例应用场景 4. mysql5.5多实例部署方法 一. ...

  2. IIS6&period;0部署asp&period;net网站步骤图解

    IIS 发布步骤 1, 程序->运行->输入inetmgr,打开IIS管理器; 2, 展开左侧树形目录->右击“网站”->新建->网站,打开网站创建向导; 3, 点击“下 ...

  3. 两种数据传输的方式——get和post。

    Form提供了两种数据传输的方式——get和post.虽然它们都是数据的提交方式,但是在实际传输时确有很大的不同,并且可能会对数据产生严重的影响.虽然为了方便的得到变量值,Web容器已经屏蔽了二者的一 ...

  4. 初识 &period;net core和vs code

    定义:什么是.net core? .net core是一个跨各个不同操作系统运行的平台.时至今日,windows上.net framework已经发展成熟,可以用来开发windows平台下的几乎所有应 ...

  5. 空间数据可视化:1&period; 3D&lowbar;Bar图表&vert; 空间柱状图

    1.Sublime的使用 中文版的配置 https://jingyan.baidu.com/article/ca2d939d1e83feeb6c31cefc.html (百度经验) sublime里边 ...

  6. 根据23423条件,截取字段&OpenCurlyQuote;abdecsdsadsadsad’,以ab&sol;dec&sol;sdsa&sol;ds&sol;ads 输出

    create or replace procedure p_getString ( p_finalString out varchar2, p_rulestring in number, p_sour ...

  7. 【BZOJ】【2750】【HAOI2012】Road

    最短路+拓扑序DP orz zyf & lyd 统计每条边在多少条最短路径上……其实可以统计 有多少条最短路径经过了x,以及y出发到达任意一个结束点有多少种走法(沿最短路) 我们可以用Dijk ...

  8. Mysql 知识点总结

    1.创建数据库    mysqladmin 下面是一个简单的例子,创建名为 yiibai_tutorials1 的数据库. D:\software\mysql--winx64\bin> mysq ...

  9. &dollar;&lbrace;&lowbar;&lowbar;BeanShell&lpar;&dollar;&lbrace;SCRIPT&rcub;&rpar;&rcub;

    通过将变量名称括在' $ { '和' } '中来引用测试元素中的变量. 函数以相同的方式引用,但按照惯例,函数名称以“ __ ” 开头,以避免与用户值名称冲突*.有些函数使用参数来配置它们,这些函数用 ...

  10. MongoDB 创建集合

    createCollection() 方法 MongoDB db.createCollection(name, options) 是用来创建集合. 语法: 基本的 createCollection() ...