Description
有 $n$ 个人参加比赛，最终的排名恰好不重复。马老师想要知道自己的排名，于是他询问了 $m$ 个人，结果都比他排名靠后。马老师觉得他rank1稳了，求马老师真实排名的期望。
Sol
马老师事件$B_i$为随机一个排名在第$i$名， $P(B_i)=\frac{1}{n}$
设事件$A$为连续$m$次抽排名都没抽中$i$，$P(A) = (\frac{i}{n-1})^m$
那么
$$ P(A|B_i) = (\frac{n-i}{n-1}) ^ m $$
那么根据全概率公式：
$$ P(A|B) = \frac{1}{n} \sum_{i=1}^{n} (\frac{n-i}{n-1}) ^ m $$
再按照贝叶斯公式有：
$$ P(B|A) = \frac{P(A|B)P(B)}{\sum_{i} P(A|B_j)P(B_j)} $$
现在来计算$E(P(B|A))$，我们已经知道$E(P(B)) = i$
$$ E=\frac{\frac{1}{n} \sum_{i=1}^{n} (\frac{n-i}{n-1}) ^ m \times i}{\frac{1}{n} \sum_{i=1}^{n}(\frac{n-i}{n-1}) ^ m} $$
可以约掉$\frac{1}{n}$ ，$(\frac{n-i}{n-1}) ^ m$ 注意该项仅仅可以约掉分母
$$ E = \frac{\sum_{i=1}^{n} (n-i)^m \times i}{\sum_{i=1}^{n} (n-i)^m } $$
对$n-i$这种项的求和倒过来就是$i$了吧，注意换一下后面的乘$i$要变成$n-i$
$$ E = \frac{\sum_{i=1}^{n} i^m \times (n-i)}{\sum_{i=1}^{n} i^m } $$
把$n$放在外面乘，现在就是
$$ E = n - \frac{\sum_{i=1}^{n} i^{m+1}}{\sum_{i=1}^{n} i^m } $$
只要进行自然数幂求和就可以了，现在来推倒自然数幂求和公式。题目仅仅要求在$O(m^2)$级别的时间内做到
我们要计算
$$ \sum_{i=0}^{n} i^m $$
把幂转成第二类斯特林数和下降幂（非常套路
$$ \sum_{i=0}^{n}\sum_{j=0}^{m} \begin{Bmatrix}m\\j\end{Bmatrix} i^{\underline j} $$
把下降幂拆了，约掉分母中的$j!$ 。再把斯特林数提到前面去算
$$ \sum_{j=0}^{m} \begin{Bmatrix}m\\j\end{Bmatrix} \sum_{i=0}^{n} \frac{i!}{(i-j)!} $$
然后不会算了，改变思路。如果不约掉分母中的$j!$的话
$$ \sum_{j=0}^{m} \begin{Bmatrix} m\\ j\end{Bmatrix} j! \sum_{i=0}^{n} \binom{i}{j} $$
这是在上指标求和吧，变成了
$$ \sum_{j=0}^{m} \begin{Bmatrix}m\\j\end{Bmatrix}j!\binom{n+1}{j+1} $$
直接$O(m^2)$预处理第二类斯特林数，注意到$n$的范围很大所以递推顺便算一下就好了
Code
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int SIZE = 5e3 + 20;
const int mod = 998244353;
int n, m;
int inv[SIZE], fac[SIZE], s[SIZE][SIZE];
namespace ae86 {
const int bufl = 1 << 15;
char buf[bufl], *s = buf, *t = buf;
inline int fetch() {
if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
return *s++;
}
inline int read() {
int a = 0, b = 1, c = fetch();
while (!isdigit(c))b ^= c == '-', c = fetch();
while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
return b ? a : -a;
}
}
using ae86::read;
int qPow(int a, int b) {
int ans = 1;
for ( ; b; b >>= 1, a = a * a % mod) {
if (b & 1) ans = ans * a % mod;
}
return ans % mod;
}
void init() {
fac[0] = 1;
for (int i = 1; i <= m + 2; ++ i) fac[i] = fac[i - 1] * i % mod;
inv[m + 2] = qPow(fac[m + 2], mod - 2) % mod;
for (int i = m + 1; ~i; -- i) inv[i] = inv[i + 1] * (i + 1) % mod;
s[0][0] = 1;
for (int i = 1; i <= m + 2; ++ i) {
for (int j = 0; j <= i; ++ j) s[i][j] = ((j > 0 ? s[i - 1][j - 1] : 0) + s[i - 1][j] * j) % mod;
}
}
int sol(int n, int m) {
int ans = 0, c = n + 1;
for (int i = 0; i <= m; ++ i) {
ans = (ans + s[m][i] * fac[i] % mod * c % mod) % mod;
c = (c * qPow(i + 2, mod - 2) % mod * (n - i) % mod) % mod;
}
return ans % mod;
}
signed main() {
// freopen("code.in", "r", stdin);
n = read() % mod, m = read(); init();
int sum1 = 0, sum2 = 0;
sum1 = sol(n - 1, m + 1), sum2 = qPow(sol(n - 1, m) % mod, mod - 2) % mod;
(sum1 *= sum2) %= mod; printf("%lld\n", (n - sum1 + mod) % mod);
return 0;
}