CF1278F

题意

[sourse](Problem - 1278F - Codeforces)

你有一副扑克牌，包含(m)张牌，其中只有1张鬼。每次操作会将牌打乱一次，然后查看最顶部的牌是否是鬼(打乱是完全随机打乱，即(m!)种排列中等概率选一种)。设(n)次操作后其中有(x)次是鬼，求(x^k)的期望，答案模998244353。

(1le n, m le 998244352)，(kle 5000)

题解

显然牌顶出现鬼的概率是(p=frac{1}{m})。

假设随机变量(X_i={0,1})代表第(i)次操作的结果。(X_i)是独立同分布的，满足概率为(p)的伯努利分布，有(E(X_i)=p)。故(x^k)期望为(E((X_1+X_2+...+X_n)^k))。展开后可得

[E(sum{X_1^{c_1}X_2^{c_2}...X_n^{c_n}})=sum{E(X_1^{c_1}X_2^{c_2}...X_n^{c_n})} ]

对于其中任一项(E(X_1^{c_1}X_2^{c_2}...X_n^{c_n})=prodlimits_{i=1}^n{E(X_i^{c_i})})。又因为(E(X_i^{c_i})=E(X_i^{[c_i>0]}))，故

[E((X_1+X_2+...+X_n)^k)=sum{E(X_{p_1}^{c_1}X_{p_2}^{c_2}...X_{p_t}^{c_t})}=sum{E(X_{p_1}X_{p_2}...X_{p_t})}\c_1,c_2,...,c_t>0 ]

设(f(j,i))代表从(1sim i)这(i)个数中取(j)次(有放回)，取出的(j)个数包括所有(i)个数的取法数，那么答案就是

[sum_{i=1}^{n}{p^i cdot C(n,i)cdot f(k,i)} ]

其中

[f(j,i)=(f(j-1，i)+f(j-1，i-1))cdot i ]

时间复杂度(O(k^2))

#include <bits/stdc++.h>

#define endl '
'
#define IOS std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define mp make_pair
#define seteps(N) fixed << setprecision(N) 
typedef long long ll;

using namespace std;
/*-----------------------------------------------------------------*/

ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
#define INF 0x3f3f3f3f

const int N = 5e3 + 10;
const int M = 998244353;
const double eps = 1e-5;

ll f[N][N], rfact[N];

inline ll qpow(ll a, ll b, ll m) {
	ll res = 1;
	while(b) {
		if(b & 1) res = (res * a) % m;
		a = (a * a) % m;
		b = b >> 1;
	}
	return res;
}

int main() {
	IOS;
	rfact[0] = 1;
	for(int i = 1; i < N; i++) rfact[i] = rfact[i - 1] * qpow(i, M - 2, M) % M;
	f[1][1] = 1;
	for(int i = 2; i < N; i++) {
		for(int j = 1; j <= i; j++) {
			f[i][j] = (f[i - 1][j] + f[i - 1][j - 1]) * j % M;
		}
	}
	int n, m, k;
	cin >> n >> m >> k;
	ll p = qpow(m, M - 2, M);
	ll ans = 0;
	ll pw = p;
	ll c = n;
	for(int i = 1; i <= k; i++) {
		ans = (ans + pw * c % M * rfact[i] % M * f[k][i] % M) % M;
		pw = pw * p % M;
		c = c * (n - i) % M;
	}
	cout << ans << endl;
}