首页 > ACM题库 > HDU-杭电 > HDU 4372-Count the Buildings-组合数学-[解题报告]HOJ
2015
05-24

HDU 4372-Count the Buildings-组合数学-[解题报告]HOJ

Count the Buildings

问题描述 :

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.

输入:

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.

输出:

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.

样例输入:

2
3 2 2
3 2 1

样例输出:

2
1

题目:Count the Buildings

题意: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数(Count the Buildings个人分成Count the Buildings组,每组内再按特定顺序围圈的分组方法的数目)。


我们可以先把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 <iostream>
#include <string.h>
#include <stdio.h>

using namespace std;
typedef long long LL;

const int N=2005;
const LL MOD=1000000007;

LL C[N][N];
LL S[N][N];

void Init()
{
    int i,j;
    for(i=0;i<N;i++)
    {
        C[i][0]=1;
        C[i][i]=1;
        S[i][0]=0;
        S[i][i]=1;
        for(j=1;j<i;j++)
        {
            C[i][j]=(C[i-1][j]%MOD+C[i-1][j-1]%MOD)%MOD;
            S[i][j]=((i-1)%MOD*S[i-1][j]%MOD+S[i-1][j-1]%MOD);
        }
    }
}

int main()
{
    LL t,n,f,b,ans;
    Init();
    scanf("%I64d",&t);
    while(t--)
    {
        scanf("%I64d%I64d%I64d",&n,&f,&b);
        ans=C[f+b-2][f-1]%MOD*S[n-1][f+b-2]%MOD;
        printf("%I64d\n",ans);
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/acdreamers/article/details/9732431