Luogu

分析

显然进的球数服从超几何分布，即
$$
P(X = c) = \frac{{m \choose c} {n - m \choose k - c}}{n \choose k}
$$
则答案为
$$
\frac{1}{n \choose k} \sum_{i = 0}^k {m \choose i} {n - m \choose k - i} i ^ L
$$
把 $i ^ L$ 用第二类斯特林数拆掉
$$
\frac{1}{n \choose k} \sum_{i = 0}^k {m \choose i} {n - m \choose k - i} \sum_{j = 0} ^ L {i \choose j} \begin{Bmatrix} L \\ j \end{Bmatrix} j!
$$
交换求和号
$$
\begin{aligned}
& \frac{1}{n \choose k} \sum_{j = 0}^L \begin{Bmatrix} L \\ j \end{Bmatrix} j! \sum_{i = 0}^k {i \choose j} {m \choose i} {n - m \choose k - i} \\
= & \frac{1}{n \choose k} \sum_{j = 0}^L \begin{Bmatrix} L \\ j \end{Bmatrix} j! {m \choose j} \sum_{i = 0}^k {m - j \choose i - j} {n - m \choose k - i}
\end{aligned}
$$
后面是范德蒙德卷积的形式，化简得到
$$
\frac{1}{n \choose k} \sum_{j = 0}^L \begin{Bmatrix} L \\ j \end{Bmatrix} j! {m \choose j} {n - j \choose i - j}
$$
$\mathcal{O}(L \log L)$ 预处理一行第二类斯特林数，然后 $\mathcal{O}(SL)$ 计算答案即可。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
    int X = 0, w = 1; char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') w = -1; c = getchar(); }
    while (c >= '0' && c <= '9') X = X * 10 + c - '0', c = getchar();
    return X * w;
}

const int N = 524288 + 10, N_ = 20000000 + 10;
const int mod = 998244353;
int qpow(int a, int b) {
    int c = 1;
    for (; b; b >>= 1, a = 1ll * a * a % mod)
        if (b & 1) c = 1ll * c * a % mod;
    return c;
}

int n, m, Q, L;
int fac[N_], ifac[N_], F[N], G[N], S[N];

int r[N];
void NTT(int *A, int n, int op) {
    for (int i = 0; i < n; ++i) if (i < r[i]) swap(A[i], A[r[i]]);
    for (int i = 1; i < n; i <<= 1) {
        int rot = qpow(op == 1 ? 3 : 332748118, (mod - 1) / (i << 1));
        for (int j = 0; j < n; j += i << 1)
            for (int k = 0, w = 1; k < i; ++k, w = 1ll * w * rot % mod) {
                int x = A[j + k], y = 1ll * w * A[j + k + i] % mod;
                A[j + k] = (x + y) % mod, A[j + k + i] = (x - y + mod) % mod;
            }
    }
    if (op == -1) {
        int inv = qpow(n, mod - 2);
        for (int i = 0; i < n; ++i) A[i] = 1ll * A[i] * inv % mod;
    }
}

int C(int n, int m) {
    if (n < 0 || m < 0 || n < m) return 0;
    return 1ll * fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}

void init_fac(int n) {
    fac[0] = 1;
    for (int i = 1; i <= n; ++i) fac[i] = 1ll * fac[i - 1] * i % mod;
    ifac[n] = qpow(fac[n], mod - 2);
    for (int i = n; i; --i) ifac[i - 1] = 1ll * ifac[i] * i % mod;
}
void init_stirling(int n) {
    for (int i = 0; i <= n; ++i) {
        F[i] = (i & 1) ? mod - ifac[i] : ifac[i];
        G[i] = 1ll * ifac[i] * qpow(i, n) % mod;
    }
    int lim = 1, l = 0;
    for (; lim <= n << 1; lim <<= 1, ++l);
    for (int i = 0; i < lim; ++i) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
    NTT(F, lim, 1), NTT(G, lim, 1);
    for (int i = 0; i < lim; ++i) F[i] = 1ll * F[i] * G[i] % mod;
    NTT(F, lim, -1);
    for (int i = 0; i <= L; ++i) S[i] = F[i];
}

int main() {
    n = read(), m = read(), Q = read(), L = read();
    init_fac(max({n, m, L})), init_stirling(L);
    while (Q--) {
        int n = read(), m = read(), k = read(), ans = 0;
        for (int i = 0; i <= L; ++i)
            ans = (ans + 1ll * S[i] * fac[i] % mod * C(m, i) % mod * C(n - i, k - i)) % mod;
        ans = 1ll * ans * qpow(C(n, k), mod - 2) % mod;
        printf("%d\n", ans);
    }
    return 0;
}