如果这篇博客帮助到你，可以请我喝一杯咖啡~
CC BY-NC-SA 4.0 （除特别声明或转载文章外）
设 $p=\frac{1}{m}$。
\[\begin{aligned} &\sum\limits_{i=0}^n{n\choose i}i^kp^{i}(1-p)^{n-i}\\ =&\sum\limits_{i=0}^n{n\choose i}\sum\limits_{j=0}^k{k\brace j}i^{\underline j}p^i(1-p)^{n-i}\\ =&\sum\limits_{i=0}^n{n\choose i}\sum\limits_{j=0}^k{k\brace j}{i\choose j}j!p^i(1-p)^{n-i}\\ =&\sum\limits_{j=0}^k{k\brace j}j!\sum\limits_{i=0}^n{n\choose i}{i\choose j}p^i(1-p)^{n-i}\\ =&\sum\limits_{j=0}^k{k\brace j}j!\sum\limits_{i=0}^n{n\choose j}{n-j\choose i-j}p^i(1-p)^{n-i}\\ =&\sum\limits_{j=0}^k{k\brace j}j!{n\choose j}\sum\limits_{i=0}^n{n-j\choose i-j}p^i(1-p)^{n-i}\\ =&\sum\limits_{j=0}^kp^j{k\brace j}j!{n\choose j}\sum\limits_{i=0}^{n-j}{n-j\choose i}p^i(1-p)^{n-j-i}\\ =&\sum\limits_{j=0}^kp^j{k\brace j}n^{\underline j}(p+1-p)^{n-j}\\ =&\sum\limits_{j=0}^kp^j{k\brace j}n^{\underline j} \end{aligned}\]到这里就可以 $\mathrm O(k\log k)$ 计算了，瓶颈在于第二类斯特林数 · 行。
不过要想过加强版，我们要继续推到 $\mathrm O(k)$ 的式子才行。
\[\begin{aligned} &\sum\limits_{j=0}^kp^j{k\brace j}{n\choose j}j!\\ =&\sum\limits_{j=0}^kp^j{n\choose j}j!\sum\limits_{i=0}^j\frac{(-1)^{j-i}i^k}{(j-i)!i!}\\ =&\sum\limits_{i=0}^k\sum\limits_{j=i}^ki^k{n\choose j}{j\choose i}(-1)^i(-p)^j\\ =&\sum\limits_{i=0}^k(-1)^ii^k\sum\limits_{j=i}^k\frac{n!j!}{j!i!(n-j)!(j-i)!}(-p)^j\\ =&\sum\limits_{i=0}^k(-1)^ii^k\sum\limits_{j=i}^k\frac{n!(n-i)!}{(n-i)!i!(n-j)!(j-i)!}(-p)^j\\ =&\sum\limits_{i=0}^k(-1)^ii^k{n\choose i}\sum\limits_{j=i}^k{n-i\choose j-i}(-p)^j\\ =&\sum\limits_{i=0}^kp^ii^k\frac{n^{\underline i}}{i!}\sum\limits_{j=0}^{k-i}{n-i\choose j}(-p)^j\\ \end{aligned}\]设 $S(i)=\sum\limits_{j=0}^{k-i}{n-i\choose j}(-p)^j$，我们现在要解决的问题就是在 $\mathrm O(k)$ 内求出 $S(i)(0\le i\le k)$。
\[\begin{aligned} S(i)=&\sum\limits_{j=0}^{k-i}{n-i\choose j}(-p)^j\\ =&\sum\limits_{j=0}^{k-i}\left({n-i-1\choose j}+{n-i-1\choose j-1}\right)(-p)^j\\ =&\sum\limits_{j=0}^{k-i}{n-i-1\choose j}(-p)^j+\sum\limits_{j=0}^{k-i}{n-i-1\choose j-1}(-p)^j\\ =&\sum\limits_{j=0}^{k-i-1}{n-i-1\choose j}(-p)^j+{n-i-1\choose k-i}(-p)^{k-i}+(-p)\sum\limits_{j=0}^{k-i-1}{n-i-1\choose j}(-p)^{j}\\ =&(-p+1)S(i+1)+{n-i-1\choose k-i}(-p)^{k-i}\\ S(k)=&1 \end{aligned}\]有公式 $\frac{n-i-1}{k-i}{n-i-1\choose k-i}={n-(i+1)-1\choose k-(i+1)}$，那么这个东西就可以线性递推了。
$\text{原式}=\sum\limits_{i=0}^kp^ii^kn^{\underline i}\frac{1}{i!}S(i)$。
#include<cstdio>
int const mod=998244353;
int pow(int x,int y){
int res=1;
while(y){
if(y&1) res=1ll*res*x%mod;
x=1ll*x*x%mod;
y>>=1;
}
return res;
}
int s[10000010],id[10000010],pr[1000010],cnt,inv[10000010],n,p,k;
bool np[10000010];
int main(){
scanf("%d%d%d",&n,&p,&k);
if(p==1) return printf("%d\n",pow(n,k)),0;
p=pow(p,mod-2),id[1]=inv[1]=1;
for(int i=2;i<=k;i++){
if(!np[i])pr[++cnt]=i,inv[i]=pow(i,mod-2),id[i]=pow(i,k);
for(int j=1;j<=cnt&&i*pr[j]<=k;j++){
inv[i*pr[j]]=1ll*inv[i]*inv[pr[j]]%mod;
id[i*pr[j]]=1ll*id[i]*id[pr[j]]%mod;
if(i%pr[j]==0)break;
}
}
int ans=0;
if(n<=k){
int q=mod+1-p,C=1,x1=1,x2=pow(q,n);
q=pow(q,mod-2);
for(int i=1;i<=k;i++){
x1=1ll*x1*p%mod;
x2=1ll*x2*q%mod;
C=1ll*C*(n-i+1)%mod*inv[i]%mod;
ans=(ans+1ll*x1*x2%mod*C%mod*id[i])%mod;
}
printf("%d\n",ans);
return 0;
}
s[k]=1;
for(int C=1,x=1,i=k-1;i;i--){
C=1ll*C*(n-i-1)%mod*inv[k-i]%mod;
x=1ll*x*(mod-p)%mod;
s[i]=(1ll*s[i+1]*(mod+1-p)+1ll*C*x)%mod;
}
for(int i=1,fac=p,ifac=1,dpow=n;i<=k;dpow=1ll*dpow*(n-i)%mod,i++,fac=1ll*fac*p%mod,ifac=1ll*ifac*inv[i]%mod)
ans=(ans+1ll*fac*id[i]%mod*dpow%mod*ifac%mod*s[i])%mod;
printf("%d\n",ans);
return 0;
}