【FJOI2016】建筑师

发布于 2017-01-03  664 次阅读


Description

小Z是一个很有名的建筑师,有一天他接到了一个很奇怪的任务:在数轴上建n个建筑,每个建筑的高度是1到n之间的一个整数。小Z有很严重的强迫症,他不喜欢有两个建筑的高度相同。另外小Z觉得如果从最左边(所有建筑都在右边)看能看到A个建筑,从最右边(所有建筑都在左边)看能看到B个建筑,这样的建筑群有着独特的美感。现在,小Z想知道满足上述所有条件的建筑方案有多少种?

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

Input Format

第一行一个整数 T,代表 T 组数据。 接下来T行,每行三个整数n,A,B。

Output Format

对于每组数据输出一行答案 mod (10^9+7)

Sample Input

2
3 2 2
3 1 2

Sample Output

2
1

Hint

【数据范围】

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


题目分析:对于当前合法的一种情况,考虑将最高的放在最左边,左边的全部移到右边并按照高度降序排列。将当前这个状态表示为f[i][j]:即对于高度i这个状态,从右向左看可以看见j个。

那么对于读入的n,a,b,则可以求得方案数为f[n][a+b-1]*c[a+b-2][a-1]。(即在f[n][a+b-1]这个状态下,不选最高的那个,于是从a+b-2个选出a-1个按照升序排在左边)

然后考虑处理f[i][j].

两种转移:1.不产生新的能看见的建筑物,有i-1个建筑物,便有i-2个位置可供填充。 对应转移f[i-1][j]*(i-2)

2.产生新的可供看见的位置。  对应转移f[i-1][j-1]。

方案数加法原理,同时取模。再预处理一下c[i][j]或者用求费马小求逆元。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<queue>
#include<cassert>
#include<climits>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define RepD(i,n) for(int i=n;i>=0;i--)
#define MEM(a) memset(a,0,sizeof(a))
#define MEMI(a) memset(a,127,sizeof(a))
#define MEMi(a) memset(a,128,sizeof(a))
#define INF (2139062143)
typedef long long LL;
const int mod=1e9+7;
LL f[50005][205];
int c[205][105],n,a,b;
inline void init(){
	Fork (i,0,200){
		c[i][0]=c[i][i]=1;
		for (int j=1;j<=i && j<=100;j++){
			c[i][j]=c[i-1][j-1]+c[i-1][j];
			if (c[i][j]>=mod) c[i][j]-=mod;
		} 
	}
	f[1][1]=1;
	Fork (i,2,50000){
		for (int j=1;j<=i && j<=200;j++)
		f[i][j]=(f[i-1][j]*(i-2)+f[i-1][j-1])%mod;
	}
}


int main(){
	init();
	int T;
	scanf("%d",&T);
	while (T--){
		scanf("%d%d%d",&n,&a,&b);
		printf("%lld\n",(f[n][a+b-1]*c[a+b-2][a-1])%mod);
	}
}

「知我罪我,其惟春秋」