【题解】[CTS2019] 珍珠

题目链接：[CTS2019] 珍珠

题意：

有 $n$ 个在范围 $[1,D]$ 内的整数均匀随机变量。

求至少能选出 $m$ 个瓶子，使得存在一种方案，选择一些变量，并把选出来的每一个变量放到一个瓶子中，满足每个瓶子都恰好装两个值相同的变量的概率。

$1\le D\le 10^5, 1\le n\le 10^9, 0\le m\le 10^9$。

大型人类填坑计划现场

怎么有人 1202 年了还做多项式啊

显然一个方案是否合法只和每种颜色的个数有关。因此设 $c_i$ 为颜色为 $i$ 的位置个数。则方案合法当且仅当：

$$ \sum_{i=1}^D \left\lfloor\dfrac{c_i}{2}\right\rfloor\ge m $$

左式转变一下形式：

$$ \sum_{i=1}^D \left\lfloor\dfrac{c_i}{2}\right\rfloor=\dfrac{n-\sum_{i=1}^D c_i\bmod 2}{2} $$

而 $\sum_{i=1}^D c_i\bmod 2$ 就是出现奇数次的颜色个数。设 $f_i$ 为恰好有 $i$ 种颜色出现奇数次的方案数，则答案应该是：

$$ \sum_{i=0}^{\min(D, n-2m)} f_i $$

恰好不好算，考虑反演一下，求钦定。设 $g_i$ 为钦定 $i$ 种颜色出现奇数次的方案数，那么有：

$$ g_i=\binom{D}{i}n![x^n]\Big(\dfrac{e^{x}-e^{-x}}{2}\Big)^i(e^x)^{D-i} $$

由于 $e^x=\sum_{i=0}^\infty \dfrac{x^i}{i!}$，$e^x=\sum_{i=0}^\infty \dfrac{(-1)^ix^i}{i!}$，所以 $\dfrac{e^{x}-e^{-x}}{2}=\sum_{i\bmod 2=1} \dfrac{x^i}{i!}$。也就是所有正奇数的 $\text{EGF}$。

化简一下：

$$ g_i=\binom{D}{i}\dfrac{n!}{2^i}[x^n]\sum_{j=0}^i\binom{i}{j}e^{x(i-j)-xj+x(D-i)}(-1)^j $$

$$ =\binom{D}{i}\dfrac{n!}{2^i}[x^n]\sum_{j=0}^i\binom{i}{j}e^{x(D-2j)}(-1)^j $$

$$ =\binom{D}{i}\dfrac{1}{2^i}\sum_{j=0}^i\binom{i}{j}(D-2j)^n(-1)^j $$

这明显是个卷积形式，直接套 $\text{NTT}$ 即可求出所有 $g_i$。同时：

$$ g_i=\sum_{j=i}^D \binom{j}{i} f_j $$

二项式反演：

$$ f_i=\sum_{j=i}^D\binom{j}{i}(-1)^{j-i} g_j $$

翻转 $f,g$ 得到 $f',g'$，那么可以得到：

$$ f_i=\sum_{j=i}^D\binom{j}{i}(-1)^{j-i} g'_{D-j} $$

$$ =\sum_{j=0}^{D-i}\binom{D-j}{i}(-1)^{D-j-i} g'_{j}=f'_{D-i} $$

因此：

$$ f'_i=\sum_{j=0}^i\binom{D-j}{D-i}(-1)^{i-j}g'_j $$

也是一遍 $\text{NTT}$。时间复杂度 $\mathcal{O}(D\log D)$。

//Code By CXY07
#include<bits/stdc++.h>
using namespace std;

//#define FILE
#define int long long
#define file(FILENAME) freopen(FILENAME".in", "r", stdin), freopen(FILENAME".out", "w", stdout)
#define randint(l, r) (rand() % ((r) - (l) + 1) + (l))
#define LINE() cout << "LINE = " << __LINE__ << endl
#define debug(x) cout << #x << " = " << x << endl
#define abs(x) ((x) < 0 ? (-(x)) : (x))
#define inv(x) qpow((x), mod - 2)
#define lowbit(x) ((x) & (-(x)))
#define ull unsigned long long
#define pii pair<int, int>
#define LL long long
#define mp make_pair
#define pb push_back
#define scd second
#define vec vector
#define fst first
#define endl '\n'

const int MAXN = 5e5 + 10;
const int INF = 2e9;
const double eps = 1e-6;
const double PI = acos(-1);
//const int mod = 1e9 + 7;
const int mod = 998244353;
const int GG = 3;
//const int base = 131;

int n, m, D, iv2 = (mod + 1) >> 1, Ans;
int lim = 1, l, ilim, rev[MAXN];
int Gs[MAXN], iGs[MAXN], A[MAXN], B[MAXN], F[MAXN], G[MAXN];
int fac[MAXN], ifac[MAXN];

template<typename T> inline bool read(T &a) {
    a = 0; char c = getchar(); int f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') {a = a * 10 + (c ^ 48); c = getchar();}
    return a *= f, true;
}

template<typename A, typename ...B>
inline bool read(A &x, B &...y) {return read(x) && read(y...);}

inline int qpow(int x, int b) {
    int res = 1;
    for(; b; b >>= 1, (x *= x) %= mod) if(b & 1) (res *= x) %= mod;
    return res;
}

void format(int x) {
    lim = 1, l = 0;
    while(lim <= x) lim <<= 1, ++l;
    for(int i = 0; i < lim; ++i) rev[i] = ((rev[i >> 1] >> 1) | ((i & 1) << (l - 1)));
    ilim = inv(lim); Gs[0] = iGs[0] = 1;
    Gs[1] = qpow(GG, (mod - 1) / lim); iGs[1] = inv(Gs[1]);
    for(int i = 2; i < lim; ++i) {
        Gs[i] = Gs[i - 1] * Gs[1] % mod;
        iGs[i] = iGs[i - 1] * iGs[1] % mod;
    }
}

void NTT(int *A2, int opt) {
    static ull A[MAXN];
    for(int i = 0; i < lim; ++i) A[i] = A2[i];
    for(int i = 0; i < lim; ++i)
        if(rev[i] < i) swap(A[rev[i]], A[i]);
    for(int mid = 1, len = (lim >> 1); mid < lim; mid <<= 1, len >>= 1) {
        for(int i = 0, x, y; i < lim; i += (mid << 1)) {
            int *o = (opt == 1) ? Gs : iGs;
            for(int j = 0; j < mid; ++j) {
                x = A[i + j], y = A[i + j + mid] * (*o) % mod;
                A[i + j] = x + y, A[i + j + mid] = x + mod - y;
                o += len;
            }
        }
    }
    for(int i = 0; i < lim; ++i) A2[i] = A[i] % mod;
    if(opt == 1) return;
    for(int i = 0; i < lim; ++i) A2[i] = A2[i] * ilim % mod;
}

signed main () {
#ifdef FILE
    freopen(".in", "r", stdin);
    freopen(".out", "w", stdout);
#endif
    read(D), read(n), read(m); format((D + 2) << 1);
    fac[0] = ifac[0] = 1;
    for(int i = 1; i <= D; ++i) fac[i] = fac[i - 1] * i % mod;
    ifac[D] = inv(fac[D]);
    for(int i = D - 1; i; --i) ifac[i] = ifac[i + 1] * (i + 1) % mod;
    for(int i = 0, opt = 1; i <= D; ++i) {
        A[i] = opt * qpow((D - 2 * i + mod) % mod, n) % mod * ifac[i] % mod;
        B[i] = ifac[i]; opt = (mod - opt) % mod;
    }
    NTT(A, 1), NTT(B, 1);
    for(int i = 0; i < lim; ++i) G[i] = A[i] * B[i] % mod;
    NTT(G, -1);
    for(int i = 0, p2 = 1; i <= D; ++i) {
        G[i] = G[i] * fac[D] % mod * ifac[D - i] % mod * p2 % mod;
        p2 = p2 * iv2 % mod;
    }
    for(int i = D + 1; i < lim; ++i) G[i] = 0;
    reverse(G, G + D + 1);
    for(int i = 0, opt = 1; i <= D; ++i) {
        G[i] = G[i] * fac[D - i] % mod;
        F[i] = opt * ifac[i] % mod; opt = (mod - opt) % mod;
    }
    NTT(F, 1), NTT(G, 1);
    for(int i = 0; i < lim; ++i) F[i] = F[i] * G[i] % mod;
    NTT(F, -1);
    for(int i = 0; i <= D; ++i) F[i] = F[i] * ifac[D - i] % mod;
    reverse(F, F + D + 1);
    for(int i = 0; i <= min(D, n - 2 * m); ++i) (Ans += F[i]) %= mod;
    printf("%lld\n", Ans);
    return 0;
}