Description：

求长为 $n$ 的排列中是前缀最大值的位置有 $a$ 个，是后缀最大值的位置有 $b$ 个的排列个数模 $998244353$ 。

$1\leqslant n\leqslant 10^5$

Solution：

首先先考虑 $DP$ ，设 $f[i][j]$ 表示 $i$ 个数的排列是前缀最大值的位置有 $j$ 个，不难发现前后是对称的，转移枚举最小值的位置，如果它放在开头前缀最大值的位置就会加一，否则不产生贡献。 $$ f[i][j]=f[i-1][j-1]+(i-1)\times f[i-1][j] $$ 发现这个就是第一类斯特林数，用分治 $+NTT$ 就可以 $O(n\log n)$ 求。

最大值所在的位置一定是前缀最大值也是后缀最大值，枚举这个位置： $$ ans=\sum_{i=1}^nS[i-1][a-1]S[n-i][b-1]C[n-1][i-1] $$ 设 $N=n-1,A=a-1,B=b-1$ ： $$ ans=\sum_{i=0}^NS[i][A]S[N-i][B]C[N][i] $$ 就相当于是先用 $i$ 个拼成 $A$ 个环，然后再用剩下的 $N-i$ 个拼成 $B$ 个环，那么就相当于拼成 $A+B$ 个环，然后从中选 $A/B$ 个，所以： $$ ans=S[N][A+B]C[A+B][A]=S[n-1][a+b-2]C[a+b-2][a-1] $$

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,a,b;

#define MAXN 400010

int S[1000][1000];

#define P 998244353

int rev[MAXN];

typedef long long ll;

ll ww[MAXN << 1],*g = ww + MAXN;

ll S1[18][MAXN];

ll power(ll a,ll b)

{

	ll res = 1;

	while(b > 0)

	{

		if(b & 1)res = res * a % P;

		a = a * a % P;

		b = b >> 1;

	}

	return res;

}

void NTT(ll f[],int l,int type)

{

	for(int i = 0;i < l;++i)

	{

		if(i < rev[i])swap(f[i],f[rev[i]]);

	}

	for(int i = 2;i <= l;i = i << 1)

	{

		ll wn = g[type * l / i];

		for(int j = 0;j < l;j += i)

		{

			ll w = 1;

			for(int k = j;k < j + i / 2;++k)

			{

				ll u = f[k],t = w * f[k + i / 2] % P;

				f[k] = (u + t) % P;

				f[k + i / 2] = (u - t + P) % P;

				w = w * wn % P;

			}

		}

	}

	if(type == -1)

	{

		ll ni = power(l,P - 2);

		for(int i = 0;i < l;++i)f[i] = f[i] * ni % P;

	}

	return;

}

void mul(ll a[],ll b[],ll res[],int n)

{

	int l = 0,len = 1;

	for(;len <= (n << 1);len = len << 1)++l;

	for(int i = 0;i < len;++i)rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (l - 1));

	g[0] = g[-len] = 1;g[1] = g[1 - len] = power(3,(P - 1) / len);

	for(int i = 2;i < len;++i)g[i] = g[i - len] = g[i - 1] * g[1] % P;

	NTT(a,len,1);NTT(b,len,1);

	for(int i = 0;i < len;++i)res[i] = a[i] * b[i] % P;

	NTT(res,len,-1);

	for(int i = 0;i < len;++i)a[i] = b[i] = 0;

	return;

}

ll tmp[MAXN];

void solve(int depth,int l,int r)

{

	if(l == r)

	{

		S1[depth][0] = l;S1[depth][1] = 1;

		return;

	}

	int mid = (l + r) / 2;

	int len = 1;

	while(len <= ((r - l + 1) << 1))len = len << 1;

	solve(depth + 1,l,mid);

	for(int i = 0;i <= r - l + 1;++i)S1[depth][i] = S1[depth + 1][i];

	for(int i = 0;i <= r - l + 1;++i)S1[depth + 1][i] = 0;

	solve(depth + 1,mid + 1,r);

	mul(S1[depth],S1[depth + 1],tmp,r - l + 1);

	for(int i = 0;i <= r - l + 1;++i)S1[depth][i] = tmp[i];

	return;

}

int main()

{

	scanf("%d%d%d",&n,&a,&b);

	if(a == 0 || b == 0){puts("0");return 0;}

	if(a + b - 1 > n){puts("0");return 0;}

	if(a + b - 1 == n){puts("1");return 0;}

	if(n == 1){puts("0");return 0;}

	solve(0,0,(n - 1) - 1);

	ll ans = S1[0][a + b - 2];

	for(int i = 1;i <= a + b - 2;++i)ans = ans * i % P;

	for(int i = 1;i <= a - 1;++i)ans = ans * power(i,P - 2) % P;

	for(int i = 1;i <= b - 1;++i)ans = ans * power(i,P - 2) % P;

	cout << ans << endl;

	return 0;

}