Cf960g - bandit Blues (type I Stirling number +ogf)

The question ： Find how many are of length n Permutation , Meet the requirement of fetching data from left to right , obtain a Number , Take data from right to left , obtain b individual , The definition of fetching is ： If the latter is larger than the current number, replace the current number . Yes 998244353 modulus .

Ideas ： Change the meaning of the question , Is to be satisfied a Different prefix maximum 、b The number of permutations of the maximum values of different suffixes .
\qquad Think backwards , The last step must be to take n, therefore n There is a-1 Different prefix maximum , In the back b-1 Maximum suffixes . The two are essentially the same .

Ideas 1 : set up f[i][j] by i The arrangement of numbers is j The number of permutations with different prefix maxima , There's a transfer equation f[i][j] = f[i-1][j-1] + (i-1)*f[i-1][j],f[0][0]=1 It is found that the recurrence formula is the same as that of the first kind of Stirling number

$ans={\sum }_{i=0}^{n-1}f[i][a-1]\ast f[n-1-i][b-1]\ast C(n-1,i)$, In the sense of Stirling number of the first kind , The expression means , front i The number makes up a-1 Rotation , after n-1-i The number makes up b-1 Rotation , Number of permutation schemes .
Equivalent to n-1 The number makes up a+b-2 Number of rotation schemes ,

namely ans = f[n-1][a+b-2]*C(a+b-2,a-1)
The combination number will be found , The first kind of Stirling number needs to be solved quickly

Because the generating function of the first kind of Stirling number ${\sum }_{i=0}^n\left[\begin{array}{c}n\\ i\end{array}\right]x^i={\prod }_{i=0}^{n-1}(x+i)$, Divide and conquer NTT,O(nlog^n2) Find the Stirling number , Note that what is required here is $\left[\begin{array}{c}n-1\\ a+b-2\end{array}\right]$（ Convolution can be done by increasing or decreasing times nlogn seek , I can't compare dishes qaq

Ideas 2： The first equation is difficult to see as Stirling number , Think directly in the mathematical sense .
Yes a-1 Different prefix maximum ,b-1 Different suffix maximum , except a+b-2 The position is fixed , The value of other positions is limited to a certain range , You can take whatever you like , For example, requirements 4 The number provides a maximum of 4 The contribution of , Then the legal arrangement is [4,1,2,3],[4,1,3,2],[4,2,1,3],[4,2,3,1],[4,3,1,2],[4,3,2,1], If one is required 2 And 4 The contribution of , There is only one [2,1,4,3]. That is to say , Yes k Different prefix maximum , Equivalent to k Rotation ([4,1,2,3] <=>[1,2,3,4] After each arrangement is rotated, the maximum value must be placed first ), The problem turns into n-1 The number makes up a+b-2 Number of rotation schemes , Then I did it one by one with the idea .（ More abstract ）

Pay attention to the situation that must not exist .

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define IOS ios::sync_with_stdio(false),cin.tie(0) 
#define _for(i,a,b) for(int i=(a) ;i<=(b) ;i++)
#define _rep(i,a,b) for(int i=(a) ;i>=(b) ;i--)
#define mst(v,s) memset(v,s,sizeof(v))
#define pii pair<int ,int >
#define pb(v) push_back(v)
#define all(v) v.begin(),v.end()
#define int long long
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define endl "\n"
#define fi first
#define se second
#define ls p<<1
#define rs p<<1|1
#define lson p<<1,l,mid
#define rson p<<1|1,mid+1,r
#define AC return 0
#define ldb long double
const int maxn = 6e6+10;
const int p = 998244353;
int Pow(int x,int d){
    
    int tans = 1;
    if(d == 0)return 1%p;
    int a = Pow(x,d/2);
    tans = 1ll*a*a%p;
    if(d%2)tans = 1ll*tans*x%p;
    return tans%p;
}
typedef vector<int> Poly;// Polynomial definition 
int F1[maxn],F2[maxn];
int rev[maxn];
void NTT(int * A,int lim,int opt) {
    
    int i, j, k, m, gn, g, tmp;
    for(int i = 0; i < lim; ++i)rev[i] = (i & 1)*(lim >> 1) + (rev[i >> 1] >> 1);
    for(i = 0; i < lim; ++i)if (rev[i] < i) swap(A[i], A[rev[i]]);
    for(m = 2; m <= lim; m <<= 1) {
    
        k = m >> 1;
        gn = Pow(3,(p - 1) / m);
        for(i = 0; i < lim; i += m) {
    
            g = 1;
            for (j = 0; j < k; ++j, g = 1ll * g * gn % p) {
    
                tmp = 1ll * A[i + j + k] * g % p;
                A[i + j + k] = (A[i + j] - tmp + p) % p;
                A[i + j] = (A[i + j] + tmp) % p;
            }
        }
    }
    if(opt == -1){
    
        reverse(A+1,A+lim);
        int inv = Pow(lim,p-2);
        for(i = 0; i < lim; ++i) A[i] = 1ll * A[i] * inv % p;
    }
}
Poly mul(const Poly & A,const Poly & B){
    
    int n = A.size(),m = B.size();
    int siz = n + m - 1;
    Poly C(siz);
    if(siz < 64){
    // Less than or equal to 64 Direct violence counts 
        for(int i = 0;i < n;i++){
    
            for(int j = 0;j < m;j++)C[i+j] = (C[i+j] + 1LL*A[i]*B[j]%p)%p;
        }
        return C;
    }
    int fsiz = 1;
    while(fsiz <= siz)fsiz *= 2;
    for(int i = 0;i < fsiz;i++)F1[i] = F2[i] = 0;
    for(int i = 0;i < n;i++)F1[i] = A[i];
    for(int i = 0;i < m;i++)F2[i] = B[i];
    NTT(F1,fsiz,1);
    NTT(F2,fsiz,1);
    for(int i = 0;i < fsiz;i++)F1[i] = 1ll*F1[i]*F2[i]%p;
    NTT(F1,fsiz,-1);
    for(int i = 0;i < siz;i++){
    
        C[i] = F1[i];
    }
    return C;
}
int n,A,B;
int fac[100005],ni_f[100005];
Poly cal(int l ,int r){
    
    if( l==r ){
    
        Poly ans(2,0);
        ans[0] = l;
        ans[1] = 1;
        return ans;
    }
    int mid = (l+r)>>1;
    return mul(cal(l,mid),cal(mid+1,r));
}
ll qsm(int a,int b,int mod){
    
    a %= mod;
    int ans = 1,temp = a;
    while(b){
    
        if( b&1 ) ans = (ans * temp)%mod;
        temp = (temp * temp)%mod;
        b>>=1;
    }
    return ans;
}
ll C(int n,int m){
    
    return fac[n]*ni_f[n-m]%p*ni_f[m]%p;
}
signed main(){
    
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif 
    IOS;
    cin>>n>>A>>B;
    if( A==0 || B==0 || A+B-2>n-1){
    
        return cout<<0<<endl,0;
    }
    if( n==1 ){
            
        return cout<<1<<endl,0;
    }
    Poly f(n+1,0);
    f = cal(0,n-2);
    fac[0]=1;
    _for(i,1,100000) fac[i] = fac[i-1]*i%p;
    ni_f[100000] = qsm(fac[100000],p-2,p);
    _rep(i,100000-1,0) ni_f[i] = ni_f[i+1] * (i+1)%p;
    int ans = C(A+B-2,A-1) * f[A+B-2]%p;
    cout<<ans<<endl;
    AC; 
}