题解 P4609 【[FJOI2016]建筑师】

newbiechd · 2018-10-02 19:25:08 · 题解

Blog
早期作品，不喜轻喷。
这应该是斯特林数和组合数的基本应用
我一开始写的题解没有关于斯特林数和组合数的介绍，结果没通过审核，现在加上：

组合数：

大家应该都熟悉它的表达式，但我们这里使用它的递推式会更加方便，下面推导组合数的递推式。设\binom{n}{m}表示在n个元素中取m个的方案数，那么如果我们考虑第n个元素取或不取：取的情况就要在剩下的n-1个元素中取m-1个；不取的情况就要在剩下的n-1个元素中取m个。由此得到递推式：

斯特林数：

准确地说是第一类斯特林数，通常用中括号表示，形如[^{\,n}_{m}]，表示n个人坐m张圆桌（没有空桌）的方案个数，我们也只需要考虑递推式。考虑第n个人单独坐一张桌子或坐到已经有人的桌子上：如果单独坐一张桌子，前面的n-1就要坐m-1张桌子；如果坐到已经有人的桌子上，就先让n-1个人坐m张桌子，第n个人可以坐到之前n-1个人中任意一个人的左边（其实说右边也无所谓，因为人们坐的是圆桌，这样考虑是为了不重不漏地包含所有的情况）
这样我们就可以得到递推式：

下面进入正题：

首先，高度为n的建筑是肯定不会被挡住的，可以把它作为一个分水岭，在它左边的被左边的建筑挡住，在它右边的被右边的建筑挡住。
由此我们可以把所有的建筑分成A+B-1个部分，每个部分由这个部分最高的建筑和被他所挡住的建筑组成，高n的建筑单独构成一个部分。
那么我们就可以把除了n以外的n-1个建筑放到A+B-2个圆桌上（n独坐一个桌），这时就是一个斯特林数。
对于每个圆桌上的建筑，构成了一个圆排列，但由于必须有一个最高的建筑挡住其他的建筑，这个圆排列的起始端就确定了，可以不重不漏地代表一个之前提到的部分。
对于每一个这样的部分，我们只需考虑它是放在n的左边还是右边，因此答案再乘上一个组合数就可以了。
答案就是：

（中括号表示斯特林数）
我们只需要利用递推式，就可以O(A*n)的求出我们所需的斯特林数，O(A^2)的求出需要的组合数。 上代码：

#include<cstdio>
#define R register
#define L long long
#define S 50000
#define N 200
using namespace std;
const int mod=1e9+7;
L s[S+10][N+10],c[N+10][N+10];
inline int read(){
    R int f=0;  R char ch=getchar();
    while(ch<48||ch>57) ch=getchar();
    while(ch>47&&ch<58) f=(f<<3)+(f<<1)+(ch^48),ch=getchar();
    return f;
}
int main(){
    R int t=read(),n,a,b,i,j;
    s[0][0]=s[1][1]=1;
    for(i=2;i<=S;++i) s[i][1]=s[i-1][1]*(i-1);
    for(i=0;i<=N;++i) c[i][0]=1;
    for(i=2;i<=S;++i)
        for(j=1;j<=N&&j<=i;++j)
            s[i][j]=(s[i-1][j-1]+s[i-1][j]*(i-1))%mod;//斯特林数递推式
    for(i=1;i<=N;++i)
        for(j=1;j<=N>>1&&j<=i;++j)
            c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;//组合数递推式
    while(t--){
        n=read(),a=read(),b=read();
        printf("%lld\n",s[n-1][a+b-2]*c[a+b-2][a-1]%mod);
    }
    return 0;
}

我在文中用的斯特林数（中括号）是靠上标下标表示的，效果可能不太好，如果有哪位大佬知道怎么打这种中括号，请在评论区里留言，谢谢！