前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >HDU 4372 Count the Buildings

HDU 4372 Count the Buildings

作者头像
attack
发布2018-04-11 11:37:15
5340
发布2018-04-11 11:37:15
举报

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.

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.

Output

For each case, you should output the number of ways mod 1000000007(1e9+7).

Sample Input

2 3 2 2 3 2 1

Sample Output

2 1

Source

2012 Multi-University Training Contest 8

Recommend

zhuyuanchen520   |   We have carefully selected several similar problems for you:  4059 2819 1730 2176 1850

实在搞不懂HDU的脾气啊。

为什么交G++会RE????

这道题的话。

不管是从左边看还是从右边看,视线总是会被中间最高的给挡住

所以我们把左边和右边分组来看。

对于某一边,我们确定出能够看见的楼房,那么不能够看见的楼房就可以任意排列

我们把能看见的楼房,与下一个能看到的楼房(不包括下一个楼房)之间的楼看为一组

那么组内的元素就可以任意排,假设一组有$n$个楼房,那么它们自由排列的方案数就是$(n-1)!$

这会让你联想的到什么?

哈哈没错,第一类斯特灵数(神TM能想到)

这样我们就可以首先对所有的楼房进行分组,然后再让他们自由排列

一共有$F-1+B-1$组

代码语言:javascript
复制
#include<iostream>
#include<cstdio>
#define LL long long 
using namespace std;
const LL MAXN=2*1e6+10;
LL T,N,F,B;
LL mod=1000000007;
LL c[2011][2011],s[2011][2011];
int main()
{
    for(LL i=0;i<=2010;i++)
    {
        c[i][0]=1;
        c[i][i]=1;
        s[i][0]=0;//无法频出环 
        s[i][i]=1;//只能拼出一个环 
        for(LL j=1;j<i;j++)
            c[i][j]=(c[i-1][j-1]%mod+c[i-1][j]%mod)%mod,
            s[i][j]=(s[i-1][j-1]%mod+(i-1)%mod*s[i-1][j]%mod)%mod;
    }
    scanf("%I64d",&T);
    while(T--)
    {
        scanf("%I64d%I64d%I64d",&N,&F,&B);
        printf("%I64d\n",(c[F-1+B-1][F-1]%mod*s[N-1][F-1+B-1]%mod)%mod);
    }
    return 0;
}
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2018-02-07 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档