【第一類斯特林數】【組合數學】2019雅禮集訓 permutation

題目：

求滿足以下條件的排列數：

剛好存在a個數，滿足 P a i > m a x { P 1 , P 2 , … … P a i − 1 } P_{a_i}>max\{P_1,P_2,……P_{a_i-1}\} Pai​​>max{P1​,P2​,……Pai​−1​}

剛好存在b個數，滿足 P b i > m a x { P n , P n − 1 , … … P b i + 1 } P_{b_i}>max\{P_n,P_{n-1},……P_{b_i+1}\} Pbi​​>max{Pn​,Pn−1​,……Pbi​+1​}

分析：

顯然，a個數必然是最大值以及最大值左邊。

b個數必然是最大值以及最大值的右邊。

是以可以定義 d p ( i , j ) dp(i,j) dp(i,j)表示i個數，其中j個數比它所在的位置之前的任何一個數都大。

答案就是 ∑ i = 1 i &lt; n d p ( i − 1 , a − 1 ) ∗ d p ( n − i , b − 1 ) ∗ ( n − 1 p − 1 ) \sum_{i=1}^{i&lt;n} dp(i-1,a-1)*dp(n-i,b-1)*{n-1 \choose p-1} i=1∑i<n​dp(i−1,a−1)∗dp(n−i,b−1)∗(p−1n−1​)

其實就是枚舉最大值的位置。

然後考慮其組合意義，可以看做：在最大值之前，将i-1個數放入a-1個圓排列中，最大值之後，将n-i個數放入b-1個圓排列中。

那麼可以換一種組合意義：把n-1個元素（去掉了最大值），放入a+b-2個圓排列中，其中a-1個放前面，b-1個放後面的方案數。

是以答案就是 [ n − 1 a + b − 2 ] ( a + b − 2 a − 1 ) {n-1\brack a+b-2}{a+b-2\choose a-1} [a+b−2n−1​](a−1a+b−2​)

#include<cstdio>
#include<algorithm>
#define SF scanf
#define PF printf
#define MAXN 800010
#define MOD 998244353
using namespace std;
const int G=3;
int tmp[MAXN];
int fsp(int x,int y){
	int res=1;
	while(y){
		if(y&1)
			res=1ll*res*x%MOD;
		x=1ll*x*x%MOD;
		y>>=1;
	}
	return res;
}
int W1[31],W2[31];
void NTT(int A[],int N,int flag){
	for(int i=1,j=0;i<N;i++){
		for(int d=N;j^=d>>=1,~j&d;);
		if(i<j)
			swap(A[i],A[j]);
	}
	for(int i=1,id=0;i<N;i<<=1,id++){
		int wn;
		if(flag==0) wn=W1[id];
		else wn=W2[id];	
		for(int j=0;j<N;j+=(i<<1)){
			int w=1;
			for(int k=0;k<i;k++,w=1ll*w*wn%MOD){
				int x=A[j+k],y=1ll*w*A[i+j+k]%MOD;
				A[j+k]=(x+y)%MOD;
				A[i+j+k]=(x-y+MOD)%MOD;
			}
		}
	}
	if(flag)
		for(int i=0,invN=fsp(N,MOD-2);i<N;i++) A[i]=1ll*A[i]*invN%MOD;
}
void mul(int A[],int B[],int N,int M,int res[]){
	static int A1[MAXN],B1[MAXN];
	for(int i=0;i<N;i++) A1[i]=A[i];
	for(int i=0;i<M;i++) B1[i]=B[i];
	int p=1;
	while(p<=N+M)
		p<<=1;
	NTT(A1,p,0);
	NTT(B1,p,0);
	for(int i=0;i<p;i++)
		A1[i]=1ll*A1[i]*B1[i]%MOD;
	NTT(A1,p,1);
	for(int i=0;i<N+M;i++)
		res[i]=A1[i];
	for(int i=0;i<p;i++) A1[i]=B1[i]=0;
}
int fac[MAXN],ifac[MAXN];
void calc(int n,int f[]){
	if(n==1){
		f[1]=1;
		return ;
	}
	int mid=(n>>1);
	calc(mid,f);
	static int tmp[MAXN],g[MAXN];
	for(int i=0;i<=mid;i++)
		g[i]=1ll*f[i]*fac[i]%MOD;
	for(int i=mid+1;i<=n;i++)
		g[i]=0;
	int n1=1;
	for(int i=0;i<=mid;i++,n1=1ll*n1*mid%MOD)
		tmp[i]=1ll*n1*ifac[i]%MOD;
	reverse(tmp,tmp+mid+1);
	mul(g,tmp,mid+1,mid+1,g);
	for(int i=0;i<=2*mid+1;i++)
		g[i]=g[i+mid];
	for(int i=0;i<=mid;i++)
		g[i]=1ll*g[i]*ifac[i]%MOD;
	mul(f,g,mid+1,mid+1,f);
	if(n&1){
		f[n]=0;
		for(int i=n;i>=0;i--)
			f[i]=(1ll*f[i]*(n-1)%MOD+f[i-1])%MOD;
	}
}
void init(){
	for(int i=0;i<22;i++){
		W1[i]=fsp(G,(MOD-1)/(1<<(i+1)));
		W2[i]=fsp(W1[i],MOD-2);
	}
	fac[0]=1;
	for(int i=1;i<=200000;i++)
		fac[i]=1ll*fac[i-1]*i%MOD;
	ifac[200000]=fsp(fac[200000],MOD-2);
	for(int i=200000;i>=1;i--)
		ifac[i-1]=1ll*ifac[i]*i%MOD;
}
int res[MAXN],n,a,b;
int C(int x,int y){
	return 1ll*fac[x]*ifac[y]%MOD*ifac[x-y]%MOD;	
}
int main(){
	init();
	SF("%d%d%d",&n,&a,&b);
	if(n==1){
		if(a==1&&b==1)
			PF("1");
		else
			PF("0");
		return 0;	
	}
	calc(n-1,res);
	PF("%lld\n",1ll*res[a+b-2]*C(a+b-2,a-1)%MOD);
}