HDU4372-Count the Buildings【第一类Stirling数】+【组合数】

时间:2022-01-21 16:01:17

<题目链接>

<转载于 >>> >

题目大意:

N座高楼,高度均不同且为1~N中的数,从前向后看能看到F个,从后向前看能看到B个,问有多少种可能的排列数。

0 < N, F, B <= 2000

解题分析:

首先我们知道一个结论:n的环排列的个数与n-1个元素的排列的个数相等,因为P(n,n)/n=(n-1)!。

可以肯定,无论从最左边还是从最右边看,最高的那个楼一定是可以看到的.

假设最高的楼的位置固定,最高楼的编号为n,那么我们为了满足条件,可以在楼n的左边分x-1组,右边分y-1组,且用每

组最高的那个元素代表这一组,那么楼n的左边,从左到右,组与组之间最高的元素一定是单调递增的,且每组中的最高元

素一定排在该组的最左边,每组中的其它元素可以任意排列(相当于这个组中所有元素的环排列)。右边反之亦然。

然后,可以这样考虑这个问题,最高的那个楼左边一定有x-1个组,右边一定有y-1个组,且每组是一个环排列,这就引出

了第一类Stirling数(HDU4372-Count the Buildings【第一类Stirling数】+【组合数】个人分成HDU4372-Count the Buildings【第一类Stirling数】+【组合数】组,每组内再按特定顺序围圈的分组方法的数目)。

我们可以先把n-1个元素分成x-1+y-1组,然后每组内部做环排列。再在所有组中选取x-1组放到楼n的左边。所以答案是

ans(n, f, b) = C[f + b - 2][f - 1] * S[n - 1][f + b - 2];

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#define LL long long
using namespace std; #define mod 1000000007
const int maxn = + ;
LL c[maxn][maxn], s[maxn][maxn]; //第一类Stirling数s(p,k)的实际意义是:将p个物体排成k个非空循环排列的方法数
void init() { //第一类斯特灵数通项公式 : S[n][k]=(S[n-1][k-1]+(n-1)*S[n-1][k])
for(int i = ; i <= ; i++) {
s[i][] = ; s[i][i] = ;
for(int j = ; j < i; j++) {
s[i][j] = ((i-)*s[i-][j]+s[i-][j-]) % mod;
//考虑递推,把n个不同元素分成k个不同的环有两种转移。第一种,有可能是n−1个不同元素
//分成k−1个不同的环,当前的第n个独立成一个元素。第二种可能是n−1个不同元素已经分好了k个不同的环,当前这个可以加进去。
}
}
} void init2() { //初始化组合数
c[][] = ;
for(int i = ; i <= ; i++) {
c[i][] = ;
for(int j = ; j <= i; j++) {
c[i][j] = c[i-][j-]+c[i-][j]; //组合数可以用杨辉三角来表示,c[i][j]=它左上方的元素+它正上方的元素
if(c[i][j] >= mod) c[i][j] -= mod;
}
}
} int main() {
init();
init2();
int T; cin >> T;
while(T--) {
int n, f, b; scanf("%d%d%d", &n, &f, &b); LL ans = (f+b- <= n && f+b- >= )? c[f+b-][f-]*s[n-][f+b-]% mod : ;
//c[f+b-2][f-1]的作用就是,将已经排好顺序的(f-1)个环按从小到大的顺序挑出f-1栋楼放在左边
printf("%lld\n", ans);
}
return ;
}

2018-08-12

HDU4372-Count the Buildings【第一类Stirling数】+【组合数】的更多相关文章

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

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

  2. HDU 4372 Count the Buildings &lbrack;第一类斯特林数&rsqb;

    有n(<=2000)栋楼排成一排,高度恰好是1至n且两两不同.现在从左侧看能看到f栋,从右边看能看到b栋,问有多少种可能方案. T组数据, (T<=100000) 自己只想出了用DP搞 发 ...

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

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

  4. HDU4372 Count the Buildings —— 组合数 &plus; 第一类斯特林数

    题目链接:https://vjudge.net/problem/HDU-4372 Count the Buildings Time Limit: 2000/1000 MS (Java/Others)  ...

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

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

  6. &lbrack;Hdu4372&rsqb; Count the Buildings

    [Hdu4372] Count the Buildings Description There are N buildings standing in a straight line in the C ...

  7. 自然数幂和——第一类Stirling数和第二类Stirling数

    第一类Stirling数 首先设 $$S_k(n)=\sum_{i=0}^ni^k$$ 根据第一类斯特林数的定义(P是排列数,C是组合数,s是Stirling) $$C_n^k={P_n^k\over ...

  8. hdu 4372 第一类stirling数的应用&sol;。。。好题

    /** 大意: 给定一系列楼房,都在一条水平线上,高度从1到n,从左侧看能看到f个, 从右侧看,能看到b个,问有多少种这样的序列.. 思路: 因为肯定能看到最高的,,那我们先假定最高的楼房位置确定,那 ...

  9. HDU 3625 Examining the Rooms:第一类stirling数

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3625 题意: 有n个房间,每个房间里放着一把钥匙,对应能开1到n号房间的门. 除了1号门,你可以踹开任 ...

随机推荐

  1. java封装性之private

    public class TestDemo{ public static void main(String args[]){ Person perA= new Person(); perA.setNa ...

  2. 连接MySQL数据库&lpar;android、php、MySQL&rpar;

    管理MySQL数据库最简单和最便利的方式是PHP脚本.运行PHP脚本使用HTTP协议和android系统连接.我们以JSON格式编码数据,因为Android和PHP都有现成的处理JSON函数. 下面示 ...

  3. 记一次Web应用CPU偏高

    LZ开发的一个公司内部应用供查询HIVE数据使用.部署上线后总是会出现CPU偏高的情况,而且本地测试很难重现.之前出现几次都是通过直接重启后继续使用,因为是内部使用,重启一下也没有很大影响(当然,每次 ...

  4. ContentProvider官方教程&lpar;9&rpar;定义一个provider完整示例:实现方法,定义权限等

    Creating a Content Provider In this document Designing Data Storage Designing Content URIs Implement ...

  5. ASP&period;NET MVC5学习笔记之Controller同步执行架构分析

    在开始之前,声明一下,由于ASP.NET MVC5正式发布了,后面的分析将基于ASP.NET MVC5最新的源代码.在前面的内容我们分析了怎样根据路由信息来确定Controller的类型,并最终生成C ...

  6. Top Android App使用的组件 2

    微信_355 SQLCipher:info.guardianproject.database:Android数据库加密 微博_650 点信传媒:cn.dx:广告平台 Apache HttpClient ...

  7. POJ 3299 Humidex(简单的问题)

    [简要题意]:什么是温度,湿度--,之间的转换.. [分析]:式已被赋予. // 252k 0Ms /* 当中exp表示的是求e的x次幂 解法就直接依据题目中的公式解决就好!! */ #include ...

  8. eclipse和tomcat整合之后每次发布server&period;xml被修改(转)

    eclipse每次发布,server.xml和context.xml总是被还原 直接找到eclispse工程下的server工程,把里面的相应的server.xml和context.xml修改了即可, ...

  9. Vxworks驱动程序的结构

    驱动程序的结构包括三个部分:初始化部分,函数功能部分和中断服务程序ISR.初始化部分初始化硬件,分配设备所需的资源,完成所有与系统相关的设置.如果是字符设备,首先调用iosDrvlnstall()来安 ...

  10. Android中对已安装应用的管理实现

    获取.管理手机中已安装的所有应用信息 1.创建应用的实体类AppInfo,属性有应用的名称.包名.图标.第一次安装时间和版本名称 public class AppInfo { private Stri ...