题目描述

小 Z 是一个很有名的建筑师，有一天他接到了一个很奇怪的任务：在数轴上建 n 个建筑，每个建筑的高度是 1 到 n 之间的一个整数。

小 Z 有很严重的强迫症，他不喜欢有两个建筑的高度相同。另外小 Z 觉得如果从最左边（所有建筑都在右边）看能看到 A个建筑，从最右边（所有建筑都在左边）看能看到 B 个建筑，这样的建筑群有着独特的美感。现在，小 Z 想知道满足上述所有条件的建筑方案有多少种？

如果建筑 i的左(右)边没有任何建造比它高，则建筑 i可以从左(右)边看到。两种方案不同，当且仅当存在某个建筑在两种方案下的高度不同。

题解

这个人可以从左边看到A栋楼，从右边看到B栋楼，其实是可以看到A+B-1栋楼，是一个单峰的，中间最高的肯定是高度为n的。

那么我们刨掉n的不管，其实是把这个序列分成了A+B-2个集合，每个集合必须且只能出一个代表元素作为能看到的那个，剩下的随便排。

那就是对于有k个元素的集合来说方案数是(k-1)!正好是k个元素的圆排列。

所以最后的方案就是S(n-1,A+B-2),然后我们还要从A+B-2中选A-1个放左边，其余放右边，所以再乘上个C(A+B-2,A-1)。

代码

#include
     
      #include
      
       #define N 50009#define M 209 using namespace std;typedef long long ll;const int mod=1e9+7;const int maxn=50000;const int maxm=200;ll c[N][M],s[N][M];int T,n,A,B;inline ll rd(){    ll x=0;char c=getchar();bool f=0;    while(!isdigit(c)){
   if(c=='-')f=1;c=getchar();}    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}    return f?-x:x;} int main(){    T=rd();     s[0][0]=1;    for(int i=0;i<=maxn;++i){      for(int j=1;j<=min(i,maxm);++j)s[i][j]=(s[i-1][j-1]+s[i-1][j]*(i-1)%mod)%mod;    }    for(int i=0;i<=maxn;++i){      c[i][0]=1;      for(int j=1;j<=min(i,maxm);++j)c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;    }     while(T--){        n=rd();A=rd();B=rd();        printf("%lld\n",c[A+B-2][A-1]*s[n-1][A+B-2]%mod);    }    return 0;}