https://codeforces.com/problemset/problem/1278/F/

题解

显然，洗一次牌，第一张是鬼牌的概率是 \(\dfrac{1}{m}\)，记 \(P=\dfrac{1}{m}\)

设 \(x_i=0/1\) 表示第 \(i\) 次洗牌之后第一张是不是鬼牌

不妨先考虑一下 \(n=2,k=2\) 的情况：

\[\begin{align*} E((x_1+x_2)^2) &=E(x_1^2+x_2^2+2*x_1*x_2) \\ & =E(x_1^2)+E(x_2^2)+2*E(x_1*x_2) \\ & =P+P+P^2 \\ & =P^2+2*P \end{align*} \]

类似的，一般情况下答案式子应该形如

\[E((x_1+x_2+\dots+x_n)^k)=\sum\limits_{i=1}^k a_i*P^i \]

考虑 \(a_i\) 的组合意义，即为构造一个长为 \(k\) 的，每个数都在 \(1\sim n\) 之间的序列，有多少种序列满足其中恰有 \(i\) 个不同的数

记 \(S(n,m)\) 为第二类斯特林数，合法的方案相当于将 \(k\) 个元素放入 \(i\) 个集合中使每个集合都非空，方案数 \(a_i=\binom{n}{i}*S(k,i)*i!\)

答案即为 \(\sum\limits_{i=1}^k \binom{n}{i}*S(k,i)*i!*P^i\)

\(O(k^2)\) 预处理第二类斯特林数(或 \(O(k\log k)\) 多项式预处理)后即可 \(O(k)\) 计算

代码

#include <bits/stdc++.h>
#define N 5005
using namespace std;

const int mod = 998244353;
inline int qmod(int x) { return x<mod?x:x-mod; }
inline int fpow(int x, int t) { int r=1;for(;t;t>>=1,x=1ll*x*x%mod)if(t&1)r=1ll*r*x%mod;return r; }
int n, m, k, s[N][N], fac[N], finv[N];

int main() {
	scanf("%d %d %d", &n, &m, &k);
	int P = fpow(m, mod-2);
	fac[0] = s[0][0] = 1;
	for (int i = 1; i <= k; i++) for (int j = 1; j <= i; j++) 
		s[i][j] = qmod(1ll*j*s[i-1][j]%mod+s[i-1][j-1]);
	for (int i = 1; i <= k; i++) fac[i] = 1ll*fac[i-1]*i%mod;
	finv[k] = fpow(fac[k], mod-2);
	for (int i = k-1; i; i--) finv[i] = 1ll*finv[i+1]*(i+1)%mod;
	int P2 = P, ans = 0, Fac = n;
	for (int i = 1; i <= k; i++) {
		ans = qmod(ans+1ll*P2*s[k][i]%mod*Fac%mod);
		Fac = 1ll*Fac*(n-i)%mod;
		P2 = 1ll*P2*P%mod;
	}
	printf("%d\n", ans);
	return 0;
}