Codeforces 1278F: Cards

题目传送门：CF1278F。

题意简述：

有 \(n\) 个独立随机变量 \(x_i\)，每个随机变量都有 \(p = 1/m\) 的概率取 \(1\)，有 \((1-p)\) 的概率取 \(0\)。

令 \(\displaystyle \Sigma x = \sum_{i=1}^{n} x_i\)，求 \(E({(\Sigma x)}^k)\)。

题解：

\[\begin{aligned} \mathbf{Ans} &= \sum_{i=0}^{n} \binom{n}{i} p^i (1-p)^{n-i} i^k \\ &= \sum_{i=0}^{n} \binom{n}{i} p^i (1-p)^{n-i} \sum_{j=0}^{k} {k \brace j} i^{\underline{j}} \\ &= \sum_{j=0}^{k} {k \brace j} \sum_{i=0}^{n} \binom{n}{i} p^i (1-p)^{n-i} i^{\underline{j}} \\ &= \sum_{j=0}^{k} {k \brace j} n^{\underline{j}} \sum_{i=0}^{n} \binom{n-j}{i-j} p^i (1-p)^{n-i} \\ &= \sum_{j=0}^{k} {k \brace j} n^{\underline{j}} p^j \sum_{i=0}^{n-j} \binom{n-j}{i} p^i (1-p)^{n-j-i} \\ &= \sum_{j=0}^{k} {k \brace j} n^{\underline{j}} p^j \end{aligned}
\]

通常幂转下降幂是常用套路。注意这个恒等式：\(\displaystyle \binom{n}{i} i^{\underline{j}} = \binom{n-j}{i-j} n^{\underline{j}}\)。

下面是代码，时间复杂度为 \(\mathcal O (k^2)\)：

#include <cstdio>

typedef long long LL;

const int Mod = 998244353;

const int MK = 5005;

inline int qPow(int b, int e) {

	int a = 1;

	for (; e; e >>= 1, b = (LL)b * b % Mod)

		if (e & 1) a = (LL)a * b % Mod;

	return a;

}

int N, M, K;

int S[MK][MK], Ans;

int main() {

	scanf("%d%d%d", &N, &M, &K);

	M = qPow(M, Mod - 2);

	S[0][0] = 1;

	for (int i = 1; i <= K; ++i)

		for (int j = 1; j <= i; ++j)

			S[i][j] = (S[i - 1][j - 1] + (LL)j * S[i - 1][j]) % Mod;

	for (int i = 1, C = 1; i <= K; ++i)

		C = (LL)C * (N - i + 1) % Mod * M % Mod,

		Ans = (Ans + (LL)S[K][i] * C) % Mod;

	printf("%d\n", Ans);

	return 0;

}