首先我们考虑$n$的情况,显然以$n$为分界线可以将整个序列分成两部分,就像这样:
、
那么我们考虑:在这个东西前面才会有前缀最大的统计,在这个东西后面才会有后缀最大的统计
这样就剩下了$n-1$个元素,而我们需要把这$n-1$个元素分成$A+B-2$个集合,然后把每个集合的最大的一个放在一端,然后剩余部分全排列
设一个集合中有$k$个元素,那么剩余元素全排列的方案数就是$(k-1)!$
考虑这也是对$k$个元素放在一个圆排列上的方案数,因此我们能搞出一个第一类斯特林数的表达式:
$S_{1}(n-1,A+B-2)$
然后考虑这几个集合在左右的分布,有:$C_{A+B-2}^{A-1}$
因此最终答案即为$S_{1}(n-1,A+B-2)C_{A+B-2}^{A-1}$
然后第一类斯特林数可以倍增$O(nlog_{2}n)$求解,因此能通过这题:
// luogu-judger-enable-o2 #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> #define ll unsigned long long #define uint unsigned int using namespace std; const uint mode=998244353; uint pow_mul(uint x,uint y) { uint ret=1; while(y) { if(y&1)ret=1ll*ret*x%mode; x=1ll*x*x%mode,y>>=1; } return ret; } uint inv[300005],minv[300005],mul[300005]; void init() { inv[0]=inv[1]=minv[0]=minv[1]=mul[0]=mul[1]=1; for(uint i=2;i<=300000;i++) { inv[i]=1ll*(mode-mode/i)*inv[mode%i]%mode; minv[i]=1ll*minv[i-1]*inv[i]%mode; mul[i]=1ll*mul[i-1]*i%mode; } } uint MOD(uint x,uint y) { return x+y>=mode?x+y-mode:x+y; } uint to[(1<<20)+5]; uint n,a,b; void NTT(uint *a,uint len,int k) { for(uint i=0;i<len;i++)if(i<to[i])swap(a[i],a[to[i]]); for(uint i=1;i<len;i<<=1) { uint w0=pow_mul(3,(mode-1)/(i<<1)); for(uint j=0;j<len;j+=(i<<1)) { uint w=1; for(uint o=0;o<i;o++,w=1ll*w*w0%mode) { ll w1=a[j+o],w2=1ll*a[j+o+i]*w%mode; a[j+o]=MOD(w1,w2)%mode,a[j+o+i]=MOD(mode-w2,w1); } } } if(k==-1) { uint inv=pow_mul(len,mode-2); for(uint i=1;i<(len>>1);i++)swap(a[i],a[len-i]); for(uint i=0;i<len;i++)a[i]=1ll*a[i]*inv%mode; } } uint A[(1<<20)+5],B[(1<<20)+5],C[(1<<20)+5]; uint tempt[(1<<20)+5],tempf[(1<<20)+5],tempg[(1<<20)+5],tempG[(1<<20)+5],tempF[(1<<20)+5]; uint ret[(1<<20)+5]; void mult(uint *f,uint *g,uint len) { uint lim=1,l=0; while(lim<=2*(len+1))lim<<=1,l++; for(uint i=0;i<lim;i++)to[i]=((to[i>>1]>>1)|((i&1)<<(l-1))); for(uint i=0;i<lim;i++)A[i]=B[i]=0; for(uint i=0;i<=len;i++)A[i]=f[i],B[i]=g[i]; for(uint i=0;i<lim;i++)C[i]=0; NTT(A,lim,1),NTT(B,lim,1); for(uint i=0;i<lim;i++)C[i]=1ll*A[i]*B[i]%mode; NTT(C,lim,-1); } void solve(uint *g,uint dep) { if(!dep){g[0]=1;return;} if(dep==1) { g[0]=0,g[1]=1; return; } if(dep&1) { solve(g,dep-1); for(uint i=1;i<=dep;i++)tempG[i]=C[i-1]; for(uint i=0;i<dep;i++)tempG[i]=MOD(tempG[i],1ll*C[i]*(dep-1)%mode); for(uint i=0;i<=dep;i++)g[i]=tempG[i]; }else { uint mid=(dep>>1); solve(g,mid); uint temp=1; for(uint i=0;i<=mid;i++,temp=1ll*temp*mid%mode)tempg[i]=1ll*g[mid-i]*mul[mid-i]%mode,tempf[i]=1ll*temp*minv[i]%mode; mult(tempg,tempf,mid); for(uint i=0;i<=mid;i++)tempF[i]=1ll*C[mid-i]*minv[i]%mode; mult(tempF,g,mid); for(uint i=0;i<=dep;i++)g[i]=C[i]; } } uint get_C(uint x,uint y) { if(x<y)return 0; return 1ll*mul[x]*minv[y]%mode*minv[x-y]%mode; } int main() { scanf("%u%u%u",&n,&a,&b);init(); solve(ret,n-1); printf("%u\n",1ll*ret[a+b-2]*get_C(a+b-2,a-1)%mode); return 0; }