牛客

分析

设 $X$ 为小 C 的排名，$Y$ 为题目条件。

那么
$$
P(X = i) = \frac{1}{n}, P(Y | X = i) = \left(\frac{n - i}{n - 1}\right) ^ m
$$
根据全概率公式有
$$
P(Y) = \frac{1}{n} \sum_{i = 1}^n \left(\frac{n - i}{n - 1}\right) ^ m
$$
根据贝叶斯公式有
$$
P(X = i | Y) = \frac{\left(\frac{n - i}{n - 1}\right) ^ m}{\sum_{j = 1}^n \left(\frac{n - j}{n - 1}\right) ^ m}
$$
从而
$$
E(X | Y) = \frac{\sum_{i = 1}^n i \left(\frac{n - i}{n - 1}\right) ^ m}{\sum_{i = 1}^n \left(\frac{n - i}{n - 1}\right) ^ m}
$$
化简得到
$$
n - \frac{\sum_{i = 0}^{n - 1} i ^ {m + 1}}{\sum_{i = 0}^{n - 1} i ^ m}
$$
随便用什么方法算自然数幂和即可。

代码

// ====================================
//   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;

ll read() {
    ll 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 S[N][N], mfac[N];

int S_(ll n, int m) { // \sum_{i = 0}^n i ^ m
    for (int i = S[0][0] = 1; i <= m; ++i)
        for (int j = 1; j <= m; ++j)
            S[i][j] = (S[i - 1][j - 1] + 1ll * j * S[i - 1][j]) % mod;
    mfac[0] = 1;
    for (int i = 1; i <= m + 1; ++i) mfac[i] = (n - i + 2) % mod * mfac[i - 1] % mod;
    int ans = 0;
    for (int i = 0; i <= m; ++i)
        ans = (ans + 1ll * S[m][i] * mfac[i + 1] % mod * qpow(i + 1, mod - 2)) % mod;
    return ans;
}

int main() {
    ll n = read(); int m = read();
    int x = S_(n - 1, m + 1), y = S_(n - 1, m);
    int ans = (n - 1ll * x * qpow(y, mod - 2) % mod + mod) % mod;
    printf("%d\n", ans);
    return 0;
}