斯特林数与放球问题

This blog post is only available in Simplified Chinse.

你有 n 个不同的小球，现在你想用这些小球拼成 k 个环，一共有多少种拼法？
你有 n 个不同的小球，现在你想将这些小球分成 k 个非空的集合，一共有多少种分法？

这两个问题就是最典型的斯特林数（Stirling Number）了。

第一类斯特林数

第一类斯特林数就对应了刚才的第一个问题：

你有 n 个不同的小球，现在你想用这些小球拼成 k 个环，一共有多少种拼法？

显然，这个问题可以用 DP 解决：定义 $s(i,j)$ 表示前 i 个小球拼成了 j 个环，那么当前的这个小球要么在之前找个环加入，也就是之前随便找个物品并且插入其右边，方案数为 $(i-1) \ast s(i-1,j)$ ；要么自成一环，方案数是 $s(i-1,j-1)$ 。状态转移就是：

\displaystyle s(i,j)=s(i-1,j-1)+(i-1)\ast s(i-1,j)

这就是经典的斯特林数模型了。通常 $s(i,j)$ 表示第一类斯特林数，另一种表示方法是 $\begin{bmatrix} i \\\\ j \end{bmatrix}$ 。

第二类斯特林数

第二类斯特林数似乎更简单，是刚才的第二个问题：

你有 n 个不同的小球，现在你想将这些小球分成 k 个非空的集合，一共有多少种分法？

显然也是 DP， $S(i,j)$ 表示前 i 个小球分成了 j 个非空集合，每个小球要么在之前随便选一组放入（注意和第一类斯特林数的不同点），方案数： $j\ast S(i-1,j)$ ；要么就新形成一组。方案数： $S(i-1,j-1)$ 。转移方程：

\displaystyle S(i,j)=S(i-1,j-1)+j\ast S(i-1,j)

$S(i,j)$ 的其他表示方法是 $S_i^{(j)}$ 或者 $\begin{Bmatrix} i \\\\ j \end{Bmatrix}$ 。

例题：HDU 4372：Count the Buildings

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

Solution

这题一看到很难下手：从左边看到的建筑物的集合，和从右边看到的建筑物的集合，究竟存在什么关系呢？仔细思考可以发现：存在一座最高的建筑，从左边看到的最右边的建筑是它，从右边看到的最左边的建筑也是它。（因为题目里说了建筑高度没有重复（“The heights of all the buildings are distinct”），为我们考虑提供了很多方便）那么可以看成这座最高的建筑物把所有建筑一分为二了。

接下来我们可以考虑：题目里问我们的是各种楼之间高度的方案数，如果我们只看最高的楼左边，不难发现题目其实就是要求我们把最高的楼左边的房屋分成 a-1 组（ a 是题中的 F ），每一组都只有一座楼房能看见，那么每一组可以看成环排列。这就是第一类斯特林数了。剩下我们还要在所有组里面选择 a-1 组放到左边，所以方案数要乘以 $C_{a-1+b-1}^{a-1}$ ，最终答案就是：

\displaystyle s(n-1,a-1+b-1)\ast C_{a-1+b-1}^{a-1}

Code

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=2005,tt=1e9+7;
int T,n,a,b,f[maxn][maxn],c[maxn][maxn];
inline int read(){
    int ret=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
inline void MakeDP(){
    f[1][1]=1;
    for (int i=2;i<=2000;i++)
        for (int j=1;j<=i;j++)
            f[i][j]=((long long)f[i-1][j-1]+(long long)(i-1)*f[i-1][j]%tt)%tt;
    for (int i=0;i<=2000;i++) c[i][0]=1;
    for (int i=1;i<=2000;i++){
        c[i][0]=c[i][i]=1;
        for (int j=1;j<i;j++) c[i][j]=(c[i-1][j]+c[i-1][j-1])%tt;
    }
}
int main(){
    T=read();
    MakeDP();
    while (T--){
        n=read();a=read();b=read();
        if (a+b-2>2000){printf("0\n");continue;}
        printf("%lld\n",(long long)f[n-1][a-1+b-1]*c[a-1+b-1][a-1]%tt);
    }
    return 0;
}

7/27/2018