【HDU 4372】 Count the Buildings (第一类斯特林数)

Count the Buildings

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1249    Accepted Submission(s): 408

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

【分析】

　　假设最高的楼的位置固定，最高楼的编号为n，

那么我们为了满足条件，可以在楼n的左边分x-1组，右边分y-1组，且用每组最高的那个元素代表这一组，那么楼n的左边，从左到右，组与组之间最高的元素一定是单调递增的，且每组中的最高元素一定排在该组的最左边，每组中的其它元素可以任意排列（相当于这个组中所有元素的环排列）。右边反之亦然。

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

　　（n个人分成k组，每组内再按特定顺序围圈的分组方法的数目）。[(n-1)!]

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

所以答案是Stirling[n-1][x-1+y-1]*C[x-1+y-1][x-1](组合数);

转自：http://blog.csdn.net/hyogahyoga/article/details/7878871

---

对于斯特林数：

第一类Stirling数 s(p,k)

　　  

s(p,k)的一个的组合学解释是：将p个物体排成k个非空循环排列的方法数。

s(p,k)的递推公式： s(p,k)=(p-1)*s(p-1,k)+s(p-1,k-1) ,1<=k<=p-1

边界条件：s(p,0)=0 ,p>=1  s(p,p)=1  ,p>=0

 

递推关系的说明：

考虑第p个物品，p可以单独构成一个非空循环排列，这样前p-1种物品构成k-1个非空循环排列，方法数为s(p-1,k-1)；

也可以前p-1种物品构成k个非空循环排列，而第p个物品插入第i个物品的左边，这有(p-1)*s(p-1,k)种方法。

 

第二类Stirling数 S(p,k)

　　 

S(p,k)的一个组合学解释是：将p个物体划分成k个非空的不可辨别的（可以理解为盒子没有编号）集合的方法数。

k!S(p,k)是把p个人分进k间有差别(如：被标有房号）的房间(无空房）的方法数。

　　 

S(p,k)的递推公式是：S(p,k)=k*S(p-1,k)+S(p-1,k-1) ,1<= k<=p-1

边界条件：S(p,p)=1 ,p>=0    S(p,0)=0 ,p>=1

　　

递推关系的说明：

考虑第p个物品，p可以单独构成一个非空集合，此时前p-1个物品构成k-1个非空的不可辨别的集合，方法数为S(p-1,k-1)；

也可以前p-1种物品构成k个非空的不可辨别的集合，第p个物品放入任意一个中，这样有k*S(p-1,k)种方法。

　　

第一类斯特林数和第二类斯特林数有相同的初始条件，但递推关系不同。

转自：http://blog.csdn.net/acdreamers/article/details/8521134

　　第一类斯特林数和第二类斯特林数的分组都不是排列，就是说组是没有编号的，如果加上编号，乘上k！即可，或者在递推公式里面乘。

　　比如：  s(p,k)=(p-1)*s(p-1,k)+s(p-1,k-1)*k (表示如果有一个新的组，要考虑它的位置对答案影响) 

　　第一类斯特林数的n个物品循环排列方案事实上等于n-1个物品的排列方案，因为n!/n=(n-1)!

　　所以如果你要分组，组内一个元素位置要固定，那么就等于循环排列。（如本题）

　　

　　斯特林数长这样：

　　

　　第一类斯特林数有以下性质：

　　

 

---

代码如下：

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cmath>
using namespace std;
#define Mod 1000000007
#define LL long long
#define Maxn 2010

LL s[Maxn][Maxn],c[Maxn][Maxn];

void init()
{
    memset(s,0,sizeof(s));
    memset(c,0,sizeof(c));
    s[0][0]=1;
    for(int i=0;i<=Maxn-10;i++) c[i][0]=1;
    for(int i=1;i<=Maxn-10;i++)
      for(int j=1;j<=Maxn-10;j++)
      {
          s[i][j]=(s[i-1][j-1]+(i-1)*s[i-1][j])%Mod;
          c[i][j]=(c[i-1][j]+c[i-1][j-1])%Mod;
      }
}

int main()
{
    init();
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n,x,y;
        scanf("%d%d%d",&n,&x,&y);
        printf("%lld
",(s[n-1][x+y-2]*c[x+y-2][x-1])%Mod);
    }
    return 0;
}

2016-09-22 13:50:59