Codeforces

Luogu

CF 上评测 ID 是 #108009000，感觉非常的好看（

分析

为了方便，设 $a = \frac{1}{m}, b = 1 - \frac{1}{m}$。

枚举第一张是王牌的次数，答案为
$$
\sum_{i = 0}^n i ^ k {n \choose i} a ^ i b ^ {n - i}
$$
把 $i ^ k$ 用第二类斯特林数展开
$$
\sum_{i = 0}^n {n \choose i} a ^ i b ^ {n - i} \sum_{j = 0} ^ k {i \choose j} \begin{Bmatrix} k \\ j \end{Bmatrix} j!
$$
交换求和号
$$
\begin{aligned}
& \sum_{j = 0} ^ k \begin{Bmatrix} k \\ j \end{Bmatrix} j! \sum_{i = 0}^n {n \choose i} {i \choose j} a ^ i b ^ {n - i} \\
= & \sum_{j = 0} ^ k \begin{Bmatrix} k \\ j \end{Bmatrix} j! {n \choose j} \sum_{i = j}^n {n - j \choose i - j} a ^ i b ^ {n - i}
\end{aligned}
$$
提一个 $a^j$ 出来，并把 $i$ 减去 $j$
$$
\sum_{j = 0} ^ k \begin{Bmatrix} k \\ j \end{Bmatrix} j! {n \choose j} a ^ j\sum_{i = 0}^{n - j} {n - j \choose i} a ^ i b ^ {n - j - i}
$$
后面是二项式定理的形式，又 $a + b = 1$，所以后面的值为 $1$，因此答案为
$$
\sum_{j = 0} ^ k \begin{Bmatrix} k \\ j \end{Bmatrix} n^{\underline{j}} a ^ j
$$
预处理斯特林数计算即可。直接递推是 $\mathcal{O}(k ^ 2)$ 的，也可以用 NTT $\mathcal{O}(k \log k)$ 求。

代码

// ====================================
//   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 = 5000 + 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, k, S[N][N];

int main() {
    n = read(), m = qpow(read(), mod - 2), k = read();
    for (int i = S[0][0] = 1; i <= k; ++i)
        for (int j = 1; j <= i; ++j)
            S[i][j] = (S[i - 1][j - 1] + 1ll * j * S[i - 1][j]) % mod;
    int ans = 0;
    for (int i = 0, a = 1, b = 1; i <= k; ++i, a = 1ll * a * (n - i + 1) % mod, b = 1ll * b * m % mod)
        ans = (ans + 1ll * a * S[k][i] % mod * b) % mod;
    printf("%d\n", ans);
    return 0;
}