hdu 4372 Count the Buildings

发表于 | 更新于

Link

Solution

圆排列

对一个环形序列，在某个点固定一个数字，其它元素的任意排列，称为圆排列。可以看出，圆排列的方案数f(n)=n!n=(n−1)!f(n)=\dfrac {n!}n=(n-1)!

编号为nn的最高，一定能看到 要在nn的位置左侧放置一个长度恰为f−1f-1的递增序列FF，在右侧放置一个长度恰为b−1b-1的递减序列BB。 对于存在于序列FF中的每个元素FiF_i，FiF_i与Fi+1F_{i+1}之间的元素可以随便摆放，这就成了一个圆排列的形式。 再考虑到要分配固定长度的递增序列，也就相当于构造固定个数的圆排列，于是就转化为第一类 数。 答案就是Cf+b−2f−1Sn−1f+b−2C_{f+b-2}^{f-1}S_{n-1}^{f+b-2}

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
#define put64(x) printf("%lld",x)
typedef long long ll;
const int N=2000,MAXN=N+11,P=1000000007;
struct Combine
{
	ll C[MAXN][MAXN];
	Combine()
	{
		C[0][0]=1;
		for(int i=1;i<=N;++i)
		{
			C[i][0]=1;
			for(int j=1;j<=i;++j)
				C[i][j]=(C[i-1][j-1]+C[i-1][j])%P;
		}
	}
	ll operator ()(int n,int m){return n>=m?C[n][m]:0;}
}C;
struct Stir
{
	ll S[MAXN][MAXN];
	Stir()
	{
		S[0][0]=1;
		for(int i=1;i<=N;++i)
		{
			S[i][0]=0;
			for(int j=1;j<=i;++j)
				S[i][j]=(S[i-1][j]*(i-1)%P+S[i-1][j-1])%P;
		}
	}
	ll operator ()(int n,int k){return n>=k?S[n][k]:0;}
}S;
int main()
{
	freopen("input","r",stdin);
	int T;get(T);
	while(T--)
	{
		int n,f,b;get(n),get(f),get(b);
		ll Ans=f+b-2<=n?C(f+b-2,f-1)*S(n-1,f+b-2)%P:0;
		put64(Ans),putchar('\n');
	}
	return 0;
}
/* AC Record(Bugs)

*/