luogu

description

一个\(1...n\)的排列，其前缀最大值有\(A\)个，后缀最大值有\(B\)个，求满足要求的排列数。

一个位置\(i\)满足前缀最大当且仅当不存在\(j<i\)使得\(a_j>a_i\)。后缀最大亦然。

\(T\le2\times10^5,n\le5\times10^4,A,B\le100\)

sol

考虑\(n\)这个数。它一定既是前缀最大又是后缀最大，所以它的前面还有\(A-1\)个前缀最大，\(B-1\)个后缀最大。

考虑每个前缀/后缀最大值，它一定挡住了若干个数（可能是零个）使得它们不能成为前缀最大。不妨将其视作一个整体，其中最大的那个数是前缀/后缀最大值，且位置在最左/右边，其余的数可以随意排列。

这等价于把除了\(n\)以外的\(n-1\)个数分成\(A+B-2\)个环排列。而这就是第一类斯特林数的定义。

所以答案就是\(s(n-1,A+B-2)\times\binom{A+B-2}{A-1}\)。

\(O(n(A+B))\)预处理，然后\(O(1)\)回答。

code

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

int gi(){

	int x=0,w=1;char ch=getchar();

	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();

	if (ch=='-') w=0,ch=getchar();

	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

	return w?x:-x;

}

const int N = 50005;

const int M = 205;

const int mod = 1e9+7;

int S[N][M],C[M][M];

int main(){

	S[0][0]=1;

	for (int i=1;i<N;++i)

		for (int j=1;j<=i&&j<M;++j)

			S[i][j]=(1ll*S[i-1][j]*(i-1)+S[i-1][j-1])%mod;

	C[0][0]=1;

	for (int i=1;i<M;++i){

		C[i][0]=1;

		for (int j=1;j<=i;++j)

			C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;

	}

	int Case=gi();while (Case--){

		int n=gi(),a=gi(),b=gi();

		printf("%lld\n",1ll*S[n-1][a+b-2]*C[a+b-2][a-1]%mod);

	}

	return 0;

}