首先对于高度为(n)的建筑,他的左边有(A-1)个建筑能被看到,右边有(B-1)个建筑能被看到,这两者类似,所以先来看左边。
一个建筑将会遮挡住它后面的高度比它矮的建筑,直到一个高度比他高的出现,所以我们不妨按这样分段看一下,例如下面这个排列
3 2 4 1 5 7 6
分段后会变成
[3 2][4 1][5][7 6]
我们要求的就是高度为(n)的建筑左边有(A-1)段,右边有(B-1)段的方案数。
不难想到讲每一段看成一个圆排列,然后讲最大的一个元素作为排列的第一个,然后从左到右形成一段。
例如这个圆排列((1,5,3)),将(5)提到第一个后会变成([5,3,1]),这样就对应了上面说的一段。
那么我们只要把(1...n-1)这(n-1)个数安排到(A+B-2)个圆排列里,然后在(n)的左边放(A-1)个圆排列,其中这(A-1)个 圆排列按排列中的最大数做关键字从小到大放就好了,右边(B-1)个排列按从大到小放。
这样答案就是(s(n-1,A+B-2) imes C(A+B-2,A-1))
其中(C(n,r))表示组合数,(s(n,k))表示第一类Stirling数,预处理出第一类斯特林数和组合数,(O(1))的回答就好了
(Code:)
#include <bits/stdc++.h>
using namespace std;
const int N=50010,P=1e9+7;
inline int add(int x,int y){return (x+=y)>=P?x-P:x;}
inline int sub(int x,int y){return (x-=y)<0?x+P:x;}
int s[N][310],C[310][310];
int main()
{
s[0][0]=1;
for(int i=1;i<=50000;i++)
for(int j=1;j<=min(i,200);j++)
s[i][j]=add(1ll*s[i-1][j]*(i-1)%P,s[i-1][j-1]);
C[0][0]=1;
for(int i=1;i<=200;i++)
{
C[i][0]=C[i][i]=1;
for(int j=1;j<i;j++)
C[i][j]=add(C[i-1][j],C[i-1][j-1]);
}
int _;scanf("%d",&_);while(_--)
{
int n,A,B; scanf("%d%d%d",&n,&A,&B);
printf("%d
",1ll*s[n-1][A+B-2]*C[A+B-2][A-1]%P);
}
return 0;
}