\(\text{Solution}\)
推式子
有答案为
\[\begin{aligned}
Ans
&=\sum_{i=0}^n i^k\dbinom n i (\frac 1 m)^i (1-\frac 1 m)^{n-i}
\end{aligned}
\]
\(i\) 的上限为 \(n\)，交换求和顺序不好优化，看到 \(i^k\)，试试第二类斯特林数
\[\sum_{i=0}^n i^k\dbinom n i (\frac 1 m)^i (1-\frac 1 m)^{n-i} =
\sum_{i=0}^n \dbinom n i (\frac 1 m)^i (1-\frac 1 m)^{n-i} \sum_{j=0}^k \begin{Bmatrix}k\\j \end{Bmatrix}j! \dbinom i j
\]
第二个求和符号后面只有 \(\dbinom i j\) 受 \(i\) 限制，而前面有 \(\dbinom n i\)，考虑恒等式（组合意义即可）
\[\dbinom n i \dbinom i j = \dbinom n j \dbinom{n-j}{i-j} =\dbinom n j \dbinom{n-j}{n-i}
\]
代回原式即可把后一部分提前
\[\begin{aligned}
\sum_{i=0}^n \dbinom n i (\frac 1 m)^i (1-\frac 1 m)^{n-i} \sum_{j=0}^k \begin{Bmatrix}k\\j \end{Bmatrix}j! \dbinom i j
&= \sum_{j=0}^k \begin{Bmatrix}k\\j \end{Bmatrix}j! \dbinom n j\sum_{i=j}^n \dbinom{n-j}{i-j} (\frac 1 m)^i (1-\frac 1 m)^{n-i} \\
&= \sum_{j=0}^k \begin{Bmatrix}k\\j \end{Bmatrix}j! \dbinom n j\sum_{i=0}^{n-j} \dbinom{n-j}i (\frac 1 m)^{i+j} (1-\frac 1 m)^{n-j-i} \\
&= \sum_{j=0}^k \begin{Bmatrix}k\\j \end{Bmatrix}j! \dbinom n j m^{-j}
\end{aligned}
\]
第二行把 \((i-j) \rightarrow i\)，然后二项式定理合并了第二个求和式子
此时已经有了 \(O(k\log k)\) 的做法了，多项式卷积直接弄出 \(S_k\)
不过可以更优，上式瓶颈在 \(S_k\) 中，考虑用容斥把 \(S_k\) 拆开
\[\begin{Bmatrix}k\\j \end{Bmatrix}=\frac1{j!}\sum_{i=0}^j {(-1)}^j\dbinom j i (j-i)^k
\]
那么
\[\begin{aligned}
\sum_{j=0}^k \begin{Bmatrix}k\\j \end{Bmatrix}j! \dbinom n j m^{-j}
&= \sum_{j=0}^k \dbinom n j m^{-j} \sum_{i=0}^j {(-1)}^j\dbinom j i (j-i)^k \\
&= \sum_{j=0}^k \dbinom n j m^{-j} \sum_{i=0}^j {(-1)}^{j-i}\dbinom j i i^k \\
&= \sum_{i=0}^k i^k (-1)^i \dbinom n i \sum_{j=i}^k \dbinom{n-i}{n-j} ({\frac 1 m})^j (-1)^j
\end{aligned}
\]
第二行同样是把 \((j-i)\rightarrow i\)，然后出现的 \(\dbinom n j \dbinom j i\) 同样处理，并提前枚举 \(i\)
前一个求和可以线筛预处理 \(i^k\)
考虑后面的求和式子，记为 \(f(i)\)，找到一种递推关系 \(O(k)\) 预处理
处理手段是把组合数按帕斯卡公式展开
那么
\[\begin{aligned}
f(i)=\sum_{j=i}^k \dbinom{n-i}{n-j} ({\frac 1 m})^j (-1)^j
&= f(i+1)+\sum_{j=i}^k \dbinom{n-i-1}{n-j-1} ({\frac 1 m})^j (-1)^j \\
&= f(i+1)+\sum_{j=i+1}^{k+1} \dbinom{n-i-1}{n-j} ({\frac 1 m})^{j-1} (-1)^{j-1}\\
&= (1-m)f(i+1) + \dbinom{n-i-1}{n-k-1} ({\frac 1 m})^k (-1)^k\\
\end{aligned}
\]
第二行把 \((j+1)\rightarrow j\)，然后单独提出 \(j=k+1\) 的式子，发现又出现了个 \(f(i+1)\)
于是可以 \(O(k)\) 递推了
恰当处理组合数即可
写到累死
\(\text{Code}\)
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int P = 998244353, N = 1e7 + 5;
LL n, m, K;
int sgn[2] = {1, P - 1};
int f[N], idk[N], inv[N], vis[N], pr[N / 5], tot;
void Add(int &x, int y){((x += y) >= P) && (x -= P);}
int fpow(int x, int y) {
int s = 1;
for(; y; y >>= 1, x = (LL)x * x % P) if (y & 1) s = (LL)s * x % P;
return s;
}
void init() {
inv[0] = inv[1] = idk[1] = 1;
for(int i = 2; i <= K + 1; ++i) inv[i] = (LL)(P - P / i) * inv[P % i] % P;
for(int i = 2; i <= K + 1; ++i) {
if (!vis[i]) pr[++tot] = i, idk[i] = fpow(i, K);
for(int j = 1; j <= tot && i * pr[j] <= N - 5; ++j) {
vis[i * pr[j]] = 1, idk[i * pr[j]] = (LL)idk[i] * idk[pr[j]] % P;
if (!(i % pr[j])) break;
}
}
}
int main() {
scanf("%lld%lld%lld", &n, &m, &K), init();
int invm = fpow(m, P - 2), c = 1;
f[K] = (LL)fpow(invm, K) * sgn[K & 1] % P;
for(int i = K - 1; i; --i) {
c = (LL)c * (n - i - 1 + P) % P * inv[K - i] % P;
f[i] = (LL)f[i + 1] * (1LL - m + P) % P;
Add(f[i], (LL)f[K] * c % P);
}
c = 1; int ans = 0;
for(int i = 1; i <= K; ++i) {
c = (LL)c * (n - i + 1) % P * inv[i] % P;
Add(ans, (LL)idk[i] * sgn[i & 1] % P * c % P * f[i] % P);
}
printf("%d\n", ans);
}