<题目链接>
<转载于 >>> >
题目大意:
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数(个人分成组,每组内再按特定顺序围圈的分组方法的数目)。
我们可以先把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数】+【组合数】的更多相关文章
-
【HDU 4372】 Count the Buildings (第一类斯特林数)
Count the Buildings Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Othe ...
-
HDU 4372 Count the Buildings [第一类斯特林数]
有n(<=2000)栋楼排成一排,高度恰好是1至n且两两不同.现在从左侧看能看到f栋,从右边看能看到b栋,问有多少种可能方案. T组数据, (T<=100000) 自己只想出了用DP搞 发 ...
-
HDU 4372 Count the Buildings——第一类斯特林数
题目大意:n幢楼,从左边能看见f幢楼,右边能看见b幢楼 楼高是1~n的排列. 问楼的可能情况 把握看到楼的本质! 最高的一定能看见! 计数问题要向组合数学或者dp靠拢.但是这个题询问又很多,难以dp ...
-
HDU4372 Count the Buildings —— 组合数 + 第一类斯特林数
题目链接:https://vjudge.net/problem/HDU-4372 Count the Buildings Time Limit: 2000/1000 MS (Java/Others) ...
-
HDU 4372 Count the Buildings:第一类Stirling数
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4372 题意: 有n栋高楼横着排成一排,各自的高度为1到n的一个排列. 从左边看可以看到f栋楼,从右边看 ...
-
[Hdu4372] Count the Buildings
[Hdu4372] Count the Buildings Description There are N buildings standing in a straight line in the C ...
-
自然数幂和——第一类Stirling数和第二类Stirling数
第一类Stirling数 首先设 $$S_k(n)=\sum_{i=0}^ni^k$$ 根据第一类斯特林数的定义(P是排列数,C是组合数,s是Stirling) $$C_n^k={P_n^k\over ...
-
hdu 4372 第一类stirling数的应用/。。。好题
/** 大意: 给定一系列楼房,都在一条水平线上,高度从1到n,从左侧看能看到f个, 从右侧看,能看到b个,问有多少种这样的序列.. 思路: 因为肯定能看到最高的,,那我们先假定最高的楼房位置确定,那 ...
-
HDU 3625 Examining the Rooms:第一类stirling数
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3625 题意: 有n个房间,每个房间里放着一把钥匙,对应能开1到n号房间的门. 除了1号门,你可以踹开任 ...
随机推荐
-
java封装性之private
public class TestDemo{ public static void main(String args[]){ Person perA= new Person(); perA.setNa ...
-
连接MySQL数据库(android、php、MySQL)
管理MySQL数据库最简单和最便利的方式是PHP脚本.运行PHP脚本使用HTTP协议和android系统连接.我们以JSON格式编码数据,因为Android和PHP都有现成的处理JSON函数. 下面示 ...
-
记一次Web应用CPU偏高
LZ开发的一个公司内部应用供查询HIVE数据使用.部署上线后总是会出现CPU偏高的情况,而且本地测试很难重现.之前出现几次都是通过直接重启后继续使用,因为是内部使用,重启一下也没有很大影响(当然,每次 ...
-
ContentProvider官方教程(9)定义一个provider完整示例:实现方法,定义权限等
Creating a Content Provider In this document Designing Data Storage Designing Content URIs Implement ...
-
ASP.NET MVC5学习笔记之Controller同步执行架构分析
在开始之前,声明一下,由于ASP.NET MVC5正式发布了,后面的分析将基于ASP.NET MVC5最新的源代码.在前面的内容我们分析了怎样根据路由信息来确定Controller的类型,并最终生成C ...
-
Top Android App使用的组件 2
微信_355 SQLCipher:info.guardianproject.database:Android数据库加密 微博_650 点信传媒:cn.dx:广告平台 Apache HttpClient ...
-
POJ 3299 Humidex(简单的问题)
[简要题意]:什么是温度,湿度--,之间的转换.. [分析]:式已被赋予. // 252k 0Ms /* 当中exp表示的是求e的x次幂 解法就直接依据题目中的公式解决就好!! */ #include ...
-
eclipse和tomcat整合之后每次发布server.xml被修改(转)
eclipse每次发布,server.xml和context.xml总是被还原 直接找到eclispse工程下的server工程,把里面的相应的server.xml和context.xml修改了即可, ...
-
Vxworks驱动程序的结构
驱动程序的结构包括三个部分:初始化部分,函数功能部分和中断服务程序ISR.初始化部分初始化硬件,分配设备所需的资源,完成所有与系统相关的设置.如果是字符设备,首先调用iosDrvlnstall()来安 ...
-
Android中对已安装应用的管理实现
获取.管理手机中已安装的所有应用信息 1.创建应用的实体类AppInfo,属性有应用的名称.包名.图标.第一次安装时间和版本名称 public class AppInfo { private Stri ...