【第一类斯特林数】【组合数学】2019雅礼集训 permutation_综合

题目：

求满足以下条件的排列数：
刚好存在a个数，满足 $P_{a_i}>max\{P_1,P_2,……P_{a_i-1}\}$
刚好存在b个数，满足 $P_{b_i}>max\{P_n,P_{n-1},……P_{b_i+1}\}$

分析：

显然，a个数必然是最大值以及最大值左边。
b个数必然是最大值以及最大值的右边。
所以可以定义 $d p (i, j)$ 表示i个数，其中j个数比它所在的位置之前的任何一个数都大。

答案就是 $∑i=1i<ndp(i?1,a?1)?dp(n?i,b?1)?(n?1p?1)\sum_{i=1}^{i<n} dp(i-1,a-1)*dp(n-i,b-1)*{n-1 \choose p-1}$

其实就是枚举最大值的位置。

然后考虑其组合意义，可以看做：在最大值之前，将i-1个数放入a-1个圆排列中，最大值之后，将n-i个数放入b-1个圆排列中。

那么可以换一种组合意义：把n-1个元素（去掉了最大值），放入a+b-2个圆排列中，其中a-1个放前面，b-1个放后面的方案数。

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

#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");elsePF("0");return 0;	}calc(n-1,res);PF("%lld\n",1ll*res[a+b-2]*C(a+b-2,a-1)%MOD);
}