「CF1287F」Cards

题目链接：https://codeforces.com/problemset/problem/1278/F。

这么无聊的题居然能放到F。。。

假设每次成功的概率为$p$，显然$p=1/m$。

答案就是：

$$\sum_{x=0}^{n}\binom{n}{x}p^x(1-p)^{n-x}x^k$$

套一下斯特林数：

$$\sum_{x=0}^{n}\binom{n}{x}p^x(1-p)^{n-x}\sum_{i=0}^{k}s_2(k,i)x^{\underline i}$$

变一下：

$$\begin{align} &\sum_{i=0}^{k}s_2(k,i)\sum_{x=0}^{n}\binom{n}{x}p^x(1-p)^{n-x}x^{\underline i}\\ =&\sum_{i=0}^{k}s_2(k,i)\sum_{x=i}^{n}\frac{n!}{(n-x)!(x-i)!}p^x(1-p)^{n-x}\\ =&\sum_{i=0}^{k}s_2(k,i)n^{\underline i}\sum_{x=i}^{n}\frac{(n-i)!}{(n-x)!(x-i)!}p^x(1-p)^{n-x}\\ =&\sum_{i=0}^{k}s_2(k,i)n^{\underline i}\sum_{x=i}^{n}\binom{n-i}{x-i}p^x(1-p)^{n-x}\\ =&\sum_{i=0}^{k}s_2(k,i)n^{\underline i}\sum_{x=0}^{n-i}\binom{n-i}{x}p^{x+i}(1-p)^{n-x-i}\\ =&\sum_{i=0}^{k}s_2(k,i)n^{\underline i}p^i \end{align}$$

复杂度$O(k^2)$。

#include<bits/stdc++.h>
using namespace std;
 
void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
 
void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}
 
#define lf double
#define ll long long 
 
#define pii pair<int,int >
#define vec vector<int >
 
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
 
#define data asd09123jdf02i3h
 
#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)
 
const int maxn = 1e6+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 998244353;
 
int n,m,k,s[5002][5002];
 
int qpow(int a,int x) {
    int res=1;
    for(;x;x>>=1,a=1ll*a*a%mod) if(x&1) res=1ll*res*a%mod;
    return res;
}
 
int main() {
    read(n),read(m),read(k);
    s[0][0]=1;
    for(int i=1;i<=k;i++) 
        for(int j=1;j<=i;j++)
            s[i][j]=(1ll*s[i-1][j]*j%mod+s[i-1][j-1])%mod;
    int ans=0,a=1,b=1,p=qpow(m,mod-2);
    for(int i=1;i<=k;i++) {
        a=1ll*a*n%mod,n--;
        b=1ll*b*p%mod;
        ans=(ans+1ll*s[k][i]*a%mod*b%mod)%mod;
    }write(ans);
    return 0;
}