CF1278F Cards

博主： tony102
发布时间：2021 年 02 月 25 日
2055 次浏览
暂无评论
2122字数
分类：题解

[Link](https://www.luogu.com.cn/problem/CF1278F)

## Sol

现在要求的是

$$E((\sum_{i=0}^{k} x_i)^k)$$

现在设$p = \frac{1}{m}$ ，表示一次性抽中王牌的概率。现在枚举$i$次王牌，那么抽中$i$次王牌的概率为$p^i$，其余$n-i$轮抽中的都不是王牌的概率为$(1-p)^{n-i}$。 那么题目条件中的$x^k$就是$i^k$ 。可以暴力计算把原式化为

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

把$i^k$拆成斯特林数的形式。看见这种样子的式子，就要想到类似联合省选组合数问题的把次幂形式的东西转成第二类斯特林数处理。那么有

$$\sum_{i=0}^{n}  \binom{n}{i} p^i (1-p)^{n-i} \sum_{j=0}^{k} \begin{Bmatrix} j \\ k \end{Bmatrix} i^{\underline j} $$

斯特林数预处理计算完成，现在斯特林数没什么要做的了，提前面去。下降幂形式的东西拆开看才会比较有发现。

$$\sum_{j=0}^{k} \begin{Bmatrix} j \\ k \end{Bmatrix} \sum_{i=0}^{n} \binom{n}{i} p^i (1-p)^{n-i} \binom{i}{j} j! $$

看见了吧，$\binom{i}{j} \cdot \binom{n}{i} = \binom{n-j}{i-j} \cdot\binom{n}{j} = \binom{n-j}{n-i} \cdot \binom{n}{j}$ 。为什么这么做？看见$(1-p)^{n-i}$这一项的指数是$n-i$ 现在出了一个组合数$\binom{n-j}{n-i}$ 。怎么搞，二项式定理搞。此外，$\binom{n}{j} \cdot j! = n^{\underline j}$先看下现在的式子

$$\sum_{j=0}^{k} \begin{Bmatrix}j \\ k \end{Bmatrix} n^{\underline j} \sum_{i=0}^{n} \binom{n-j}{n-i} p^i (1-p)^{n-i}$$

实际上枚举$i$的效果和枚举$n-i$效果是一样的嘛，求和上界改成$n-j$ , 因为当$i' > n -j$ 是组合已经无意义

$$\sum_{j=0}^{k} \begin{Bmatrix}j \\ k \end{Bmatrix} n^{\underline j} \sum_{i=0}^{n-j} \binom{n-j}{i} p^{n-j-i} (1-p)^{i}$$

现在的愣头小青年都喜欢OGF，说我不喜欢组合意义，我永远只喜欢生成函数

试试二项式定理，为了方便，设$x=p, y = 1-p$ 。有$x+y = 1$

$$(x+y)^{n-j} = \sum_{i=0}^{n-j} \binom{n-j}{i} x^{n-j-i} y^{i}$$

这玩意就等于 $1$ 吧，所以后面那个和式已经是$1$了。我们要求只有前面那一个和式，也就是

$$\sum_{j=0}^{k} \begin{Bmatrix}j \\ k \end{Bmatrix} n^{\underline j}$$

$k \leq 5 \times 10^3$  所以直接 $O(n^2)$ 预处理组合数，和 $n^{\underline j} = \binom{n}{j} j! = \frac{n!}{(n-j)!}$

## Code
```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int SIZE = 5e3 + 5;
const int mod = 998244353;

int n, m, k;
int pw[SIZE], des[SIZE], s[SIZE][SIZE];

namespace ae86 {
	const int bufl = 1 << 15;
	char buf[bufl], *s = buf, *t = buf;
	inline int fetch() {
		if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
		return *s++;
	}
	inline int read() {
		int a = 0, b = 1, c = fetch();
		while (!isdigit(c))b ^= c == '-', c = fetch();
		while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
		return b ? a : -a;
	}
}
using ae86::read;

int qPow(int a, int b) {
	int ans = 1;
	for ( ; b; b >>= 1, a = a * a % mod) {
		if (b & 1) ans = ans * a % mod;
	}
	return ans % mod;
}

signed main() {
	// freopen("code.in", "r", stdin);
	n = read(), m = read(), k = read();
	s[0][0] = pw[0] = des[0] = 1;
	int inv = qPow(m, mod - 2) % mod, ans = 0;
	for (int i = 1; i <= k; ++ i) {
		for (int j = 1; j <= i; ++ j) s[i][j] = (s[i - 1][j] * j % mod + s[i - 1][j - 1]) % mod;
	}
	for (int i = 1; i <= k; ++ i) pw[i] = pw[i - 1] * inv % mod;
	for (int i = 1; i <= k; ++ i) des[i] = des[i - 1] * (n - i + 1) % mod;
	for (int i = 0; i <= k; ++ i) ans = (ans + s[k][i] * des[i] % mod * pw[i] % mod) % mod;
	printf("%lld\n", ans);
	return 0;
}
```

最后修改：2021 年 08 月 20 日