【FJOI2016】建筑师
问题描述
小 Z 是一个很有名的建筑师，有一天他接到了一个很奇怪的任务：在数轴上建 n 个建筑，每个建筑的高度是 1 到 n 之间的一个整数。
小 Z 有很严重的强迫症，他不喜欢有两个建筑的高度相同。另外小 Z 觉得如果从最左边（所有建筑都在右边）看能看到 A个建筑，从最右边（所有建筑都在左边）看能看到 B 个建筑，这样的建筑群有着独特的美感。现在，小 Z 想知道满足上述所有条件的建筑方案有多少种？
如果建筑 i 的左(右)边没有任何建造比它高，则建筑 i 可以从左(右)边看到。两种方案不同，当且仅当存在某个建筑在两种方案下的高度不同。
输入格式
第一行一个整数 T，代表 T 组数据。
接下来 T 行，每行三个整数 n,A,B输出格式
对于每组数据输出一行答案 mod10^9+7。
样例输入 1
2
3 2 2
3 1 2样例输出 1
2
1样例输入 2
5
1 1 1
2 1 1
4 3 1
10 2 2
8 6 4样例输出 2
1
0
3
219168
0提示
对于 10% 的数据 ： 1≤n≤10
对于 20% 的数据 ： 1≤n≤100
对于 40% 的数据 ： 1≤n≤50000, 1≤T≤5
对于 100%的数据 ：1≤n≤50000, 1≤A,B≤100, 1≤T≤200000
显然最高的那个一定看得见放在哪里都一样，我们不管它。
然后考虑最高的杆子左边的部分（右边同理）
每 两个看得见的杆子之间都可能会有被挡住的杆子，我们把一个看得见的杆子和它挡住的杆子看成一个集合，假设这个集合大小为C，那么在确定集合元素的情况下， 这个集合的排列的方案数实际上就是C个元素圆排列的方案数。因为一个圆排列都对应且仅对应一个合法排列（因为最高的杆子肯定在最左边所以肯定是从最高的杆 子这里断开），所以问题就变成了把n-1个杆子分成a+b-2个圆排列的方案数（因为最高的杆子左边有a-1个这样的集合，右边有b-1个），就 是$S(n-1,a+b-2)$。当然对于每种分法我们要确定这个圆排列是在左边还是在右边，所以要乘上$C(a+b-2,a-1)$。
答案就是$S(n-1,a+b-2)*C(a+b-2,a-1)$，预处理一下$O(1)$回答就好了。
1 #include<cstdio>
2 #include<algorithm>
3 #define rep(i,l,r) for (int i=l; i<=r; i++)
4 using namespace std;
5
6 const int MOD=1000000007,M=210,N=50010;
7 int s[N][M],C[M][M],T,n,a,b;
8
9 void init(int n,int a) {
10 rep(i,0,n){
11 s[i][0]=0;
12 if(i<=a) s[i][i]=1;
13 rep(j,1,min(i,a)) s[i][j]=(0ll+s[i-1][j-1]+1ll*(i-1)*s[i-1][j]%MOD)%MOD;
14 }
15 rep(i,0,a){
16 C[i][0]=1;
17 rep(j,1,i) C[i][j]=(0ll+C[i-1][j]+C[i-1][j-1])%MOD;
18 }
19 }
20
21 int main() {
22 init(50000,200);
23 for (scanf("%d",&T); T--; )
24 scanf("%d%d%d",&n,&a,&b),printf("%lld
",(1ll*s[n-1][a+b-2]*C[a+b-2][a-1])%MOD);
25 return 0;
26 }