LUOGU P4609 [FJOI2016]建筑师(第一类斯特林数)-程序员宅基地

传送门

解题思路

　　好神仙的思路，首先一种排列中按照最高点将左右分开，那么就是要在左边选出\(a-1\)个，右边选出\(b-1\)一个，这个如何计算呢？考虑第一类斯特林数，第一类斯特林数是将\(n\)个数分成\(m\)个圆排列的方案数，在这道题中，假如划分成圆排列之后，将圆排列从最大值处断开可以造成\(1\)的贡献。那么答案就为\(s(n-1,a+b-2)*C(a+b-2,a-1)\)。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>

using namespace std;
const int N=50005;
const int A=205;
const int MOD=1e9+7;
typedef long long LL;

inline int rd(){
    int x=0,f=1; char ch=getchar();
    while(!isdigit(ch)) f=ch=='-'?0:1,ch=getchar();
    while(isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return f?x:-x;  
}

int n,m,s[N][A],C[A][A],a,b;

inline void prework(){
    C[0][0]=1;
    for(int i=1;i<=200;i++){
        C[i][0]=1;
        for(int j=1;j<=i;j++)
            C[i][j]=(C[i-1][j]+C[i-1][j-1])%MOD;    
    }
    s[0][0]=1; int Min;
    for(int i=1;i<=200;i++) s[i][i]=1;
    for(int i=1;i<=50000;i++){
        Min=min(i,200);
        for(int j=1;j<=Min;j++)
            s[i][j]=(1ll*(i-1)*s[i-1][j]%MOD+s[i-1][j-1])%MOD;
    }
}

int main(){
    prework();
    for(int T=rd();T;T--){
        n=rd(),a=rd(),b=rd();
        printf("%lld\n",1ll*C[a+b-2][a-1]*s[n-1][a+b-2]%MOD);
    }   
    return 0;   
}