题目概述

求有多少 $n$ 的排列满足从左边会更新 $A$ 次最大值，从右边会更新 $B$ 次最大值。

解题报告

第一类斯特林数：$s(n,k)$ 表示把 $n$ 个数分成 $k$ 个圆排列的方案数。

根据定义，讨论 $n$ 的位置，得到：$s(n,k)=s(n-1,k-1)+(n-1)s(n-1,k)$ 。

更新最大值肯定会停在最大的那个位置，所以左右实际上是分开的，我们可以先枚举最大值所在的位置，然后左边右边分别计算方案数，令 $f(n,a)$ 表示把 $n$ 个数排成从左边会更新 $a$ 次最大值的方案数（显然把序列反过来就适用于右边），那么答案为：

$$ \sum_{i=1}^{n}{n-1\choose i-1}f(i-1,A-1)f(n-i,B-1) $$

我们发现 $f$ 根据定义很难计算（无法得知 $n$ 插入进去产生的贡献），因此我们可以计算 $g(n,a)$ 表示把 $n$ 个数排成从左边会更新 $a$ 次最小值的方案数，显然 $f(n,a)=g(n,a)$（将 $i$ 换成 $n-i+1$ ），那么我们可以得出 $f$ 的递推式（有把 $n$ 加在最前面和把 $n​$ 加在其他数里面两种转移方法）：

$$ f(n,a)=f(n-1,a-1)+(n-1)f(n-1,a) $$

这东西有点诡异……怎么和第一类斯特林数长得一毛一样啊……实际上我们可以认为 $f(n,a)$ 是把 $n$ 个数分成了 $a$ 组，每组中最大的在最前面，其余在后面乱排，也就是圆排列（圆排列可以看做一个位置不动，其他位置乱排）。

但是 $s$ 的处理是 $O(n^2)$ 的，所以之前那个式子算不了……考虑把之前那个式子变得更简单一点，由于 $s(n,a)$ 表示 $n$ 个数分成 $a$ 组，所以我们并不需要枚举最大值的位置 $i$ ，只需要把剩下 $n-1$ 个数分成 $A+B-2$ 组，然后把最大值插进去就行了，方案数为：

$$ {A+B-2\choose A-1}s(n-1,A+B-2) $$

而 $s(n,0\sim n)$ 是有方法 $O(nlog_2n)$ 求出来的，考虑 $s(n,k)$ 的另外一个含义：每个数 $i$ 有 $1$ 种方法选，$i-1$ 种方法不选，选出 $k$ 个数方案数。因此：

$$ x^{\overline n}=\prod_{i=0}^{n-1}(x+i)=\sum_{i=0}^{n}s(n,i)x^i $$

所以只要求出 $\prod_{i=0}^{n-1}(x+i)$ 的所有系数就行啦，我们可以：

• 分治FFT：复杂度 $O(nlog_2^2n)$ 。

• 倍增，通过 $x^{\overline n}(x+n)^{\overline n}=x^{\overline{2n}}$ 来求：

  $$ x^{\overline n}=\sum_{i=0}^{n}a_ix^i\\ \begin{aligned} (x+n)^{\overline n}&=\sum_{i=0}^{n}a_i(x+n)^i\\ &=\sum_{i=0}^{n}a_i\sum_{j=0}^{i}{i\choose j}x^jn^{i-j}\\ &=\sum_{i=0}^{n}x^i\sum_{j=i}^{n}a_j{j\choose i}n^{j-i}\\ &=\sum_{i=0}^{n}x^i{1\over i!}\sum_{j=i}^{n}a_jj!{n^{j-i}\over(j-i)!}\\ \end{aligned} $$

  转化一下就是个卷积形式了，复杂度 $T(n)=T({n\over 2})+O(nlog_2n)=O(nlog_2n)$ 。

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=200000,maxt=1<<18,MOD=998244353;

int n,A,B,fac[maxn+5],INV[maxn+5],s[maxt+5],F[maxt+5],G[maxt+5],H[maxt+5];
int rev[maxt+5],pw[2][maxt+5];

inline void Make(int n){
    INV[0]=INV[1]=1;for (int i=2;i<=n;i++) INV[i]=(LL)(MOD-MOD/i)*INV[MOD%i]%MOD;
    fac[0]=1;for (int i=1;i<=n;i++) fac[i]=(LL)fac[i-1]*i%MOD,INV[i]=(LL)INV[i]*INV[i-1]%MOD;
}
inline int Pow(int w,int b) {int s;for (s=1;b;b>>=1,w=(LL)w*w%MOD) if (b&1) s=(LL)s*w%MOD;return s;}
inline void Pre(int n){
    for (int i=1;i<n;i++) rev[i]=(rev[i>>1]>>1)|((i&1)*(n>>1));
    for (int i=2;i<=n;i<<=1) pw[0][i]=Pow(3,(MOD-1)/i),pw[1][i]=Pow(pw[0][i],MOD-2);
}
inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
inline void NTT(int *a,int n,int f){
    for (int i=0;i<n;i++) if (i<rev[i]) swap(a[i],a[rev[i]]);
    for (int k=1;k<n;k<<=1){
        int gn=pw[f<0][k<<1],g=1,x,y;
        for (int i=0;i<n;i+=k<<1,g=1)
            for (int j=0;j<k;j++,g=(LL)g*gn%MOD)
                x=a[i+j],y=(LL)a[i+j+k]*g%MOD,AMOD(a[i+j]=x,y),AMOD(a[i+j+k]=x,MOD-y);
    }if (f<0) for (int i=0,INV=Pow(n,MOD-2);i<n;i++) a[i]=(LL)a[i]*INV%MOD;
}
void Solve(int *s,int n){
    if (n==0) {s[0]=1;return;}if (n==1) {s[0]=0;s[1]=1;return;}int m=n>>1;Solve(s,m);
    for (int i=0,pw=1;i<=m;i++,pw=(LL)pw*m%MOD) F[i]=(LL)s[m-i]*fac[m-i]%MOD,G[i]=(LL)pw*INV[i]%MOD;
    int t;for (t=1;t<=(m<<1);t<<=1);for (int i=m+1;i<t;i++) F[i]=G[i]=0;Pre(t);
    NTT(F,t,1);NTT(G,t,1);for (int i=0;i<t;i++) H[i]=(LL)F[i]*G[i]%MOD;NTT(H,t,-1);reverse(H,H+m+1);
    for (int i=0;i<=m;i++) H[i]=(LL)H[i]*INV[i]%MOD;for (int i=m+1;i<t;i++) H[i]=s[i]=0;
    NTT(H,t,1);NTT(s,t,1);for (int i=0;i<t;i++) s[i]=(LL)s[i]*H[i]%MOD;NTT(s,t,-1);
    if (n&1) for (int i=n;~i;i--) AMOD(s[i]=(LL)s[i]*(n-1)%MOD,i?s[i-1]:0);
}
#define C(x,y) ((x)<(y)?0:(LL)fac[x]*INV[y]%MOD*INV[(x)-(y)]%MOD)
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d%d",&n,&A,&B);Make(n);Solve(s,n-1);
    printf("%lld\n",(LL)C(A+B-2,A-1)*s[A+B-2]%MOD);return 0;
}