【题解】Bandit Blues 第一类斯特林数 分治 NTT CF960G

#include <bits/stdc++.h>

#define NS (262144)
#define LGS (18)
#define MOD (998244353)
#define G (3)

#define pls(a, b) ((a) + (b) < MOD ? (a) + (b) : (a) + (b) - MOD)
#define mns(a, b) ((a) - (b) < 0 ? (a) - (b) + MOD : (a) - (b))
#define mul(a, b) (1ll * (a) * (b) % MOD)
#define Inv(a) (qpow((a), MOD - 2))

using namespace std;

template<typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

int qpow(int a, int b)
{
    int res = 1;
    while (b)
    {
        if (b & 1) res = mul(res, a);
        a = mul(a, a), b >>= 1;
    }
    return res;
}

int n, A, B;

int rev[NS];

struct poly
{
    int d[NS], N, bs;
    int& operator [] (const int a) {return d[a];}
    void resize(int s)
    {
        int tmp = N;
        N = 1, bs = 0;
        while (N < s) N <<= 1, bs++;
        for (int i = tmp; i < N; i += 1) d[i] = 0;
    }
    void ntt(int t)
    {
        for (int i = 1; i < N; i += 1)
        {
            rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bs - 1));
            if (i < rev[i]) swap(d[i], d[rev[i]]);
        }
        for (int l = 1; l < N; l <<= 1)
        {
            int dt = qpow(G, (MOD - 1) / (l << 1));
            if (t == -1) dt = Inv(dt);
            for (int i = 0; i < N; i += (l << 1))
            {
                int g = 1, t1, t2;
                for (int j = i; j < i + l; j += 1, g = mul(g, dt))
                {
                    t1 = d[j], t2 = mul(g, d[j + l]);
                    d[j] = pls(t1, t2), d[j + l] = mns(t1, t2);
                }
            }
        }
        if (t == -1)
        {
            int inv = Inv(N);
            for (int i = 0; i < N; i += 1) d[i] = mul(d[i], inv);
        }
    }
    void operator *= (poly &oth)
    {
        for (int i = 0; i < N; i += 1) d[i] = mul(d[i], oth[i]);
    }
} P[LGS];

stack<int> rub;

int Binary(int l, int r)
{
    if (l == r)
    {
        int a = rub.top(); rub.pop();
        P[a].resize(2), P[a][0] = l, P[a][1] = 1;
        return a;
    }
    int mid = (l + r) >> 1;
    int a = Binary(l, mid), b = Binary(mid + 1, r);
    P[a].resize(r - l + 2), P[b].resize(r - l + 2);
    P[a].ntt(1), P[b].ntt(1), P[a] *= P[b], P[a].ntt(-1), rub.push(b);
    return a;
}

int C(int a, int b)
{
    int x = 1, y = 1;
    for (int i = a - b + 1; i <= a; i += 1) x = mul(x, i);
    for (int i = 1; i <= b; i += 1) y = mul(y, i);
    return mul(x, Inv(y));
}

int main(int argc, char const* argv[])
{
    IN(n), IN(A), IN(B), n--;
    if (!A || !B || A + B - 2 > n) puts("0"), exit(0);
    if (!n) puts("1"), exit(0);
    for (int i = 0; i < LGS; i += 1) rub.push(i);
    int a = Binary(0, n - 1);
    printf("%lld\n", mul(P[a][A + B - 2], C(A + B - 2, B - 1)));
    return 0;
}