牛客挑战赛36D 排名估算

博主： tony102
发布时间：2020 年 10 月 24 日
1362 次浏览
暂无评论
1969字数
分类：题解

[Link](https://ac.nowcoder.com/acm/contest/3782/D)

## Description

有 $n$ 个人参加比赛，最终的排名恰好不重复。马老师想要知道自己的排名，于是他询问了 $m$ 个人，结果都比他排名靠后。马老师觉得他rank1稳了，求马老师真实排名的期望。

## Sol

马老师事件$B_i$为随机一个排名在第$i$名， $P(B_i)=\frac{1}{n}$

设事件$A$为连续$m$次抽排名都没抽中$i$，$P(A) = (\frac{i}{n-1})^m$

那么

$$
P(A|B_i) = (\frac{n-i}{n-1}) ^ m
$$

那么根据全概率公式：

$$
P(A|B) = \frac{1}{n} \sum_{i=1}^{n}  (\frac{n-i}{n-1}) ^ m
$$

再按照贝叶斯公式有：

$$
P(B|A) = \frac{P(A|B)P(B)}{\sum_{i} P(A|B_j)P(B_j)}
$$

现在来计算$E(P(B|A))$，我们已经知道$E(P(B)) = i$

$$
E=\frac{\frac{1}{n} \sum_{i=1}^{n} (\frac{n-i}{n-1}) ^ m \times i}{\frac{1}{n} \sum_{i=1}^{n}(\frac{n-i}{n-1}) ^ m}
$$

可以约掉$\frac{1}{n}$ ，$(\frac{n-i}{n-1}) ^ m$ 注意该项仅仅可以约掉分母

$$
E = \frac{\sum_{i=1}^{n} (n-i)^m \times i}{\sum_{i=1}^{n} (n-i)^m }
$$

对$n-i$这种项的求和倒过来就是$i$了吧，注意换一下后面的乘$i$要变成$n-i$

$$
E = \frac{\sum_{i=1}^{n} i^m \times (n-i)}{\sum_{i=1}^{n} i^m }
$$

把$n$放在外面乘，现在就是

$$
E = n - \frac{\sum_{i=1}^{n} i^{m+1}}{\sum_{i=1}^{n} i^m }
$$

只要进行自然数幂求和就可以了，现在来推倒自然数幂求和公式。题目仅仅要求在$O(m^2)$级别的时间内做到

我们要计算

$$
\sum_{i=0}^{n} i^m
$$

把幂转成第二类斯特林数和下降幂（非常套路

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

把下降幂拆了，约掉分母中的$j!$ 。再把斯特林数提到前面去算

$$
\sum_{j=0}^{m} \begin{Bmatrix}m\\j\end{Bmatrix} \sum_{i=0}^{n} \frac{i!}{(i-j)!}
$$

然后不会算了，改变思路。如果不约掉分母中的$j!$的话

$$
\sum_{j=0}^{m} \begin{Bmatrix} m\\ j\end{Bmatrix} j! \sum_{i=0}^{n}  \binom{i}{j}
$$

这是在上指标求和吧，变成了

$$
\sum_{j=0}^{m} \begin{Bmatrix}m\\j\end{Bmatrix}j!\binom{n+1}{j+1}
$$

直接$O(m^2)$预处理第二类斯特林数，注意到$n$的范围很大所以递推顺便算一下就好了

## Code

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

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

int n, m;
int inv[SIZE], fac[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;
}

void init() {
	fac[0] = 1;
	for (int i = 1; i <= m + 2; ++ i) fac[i] = fac[i - 1] * i % mod;
	inv[m + 2] = qPow(fac[m + 2], mod - 2) % mod;
	for (int i = m + 1; ~i; -- i) inv[i] = inv[i + 1] * (i + 1) % mod;
	s[0][0] = 1;
	for (int i = 1; i <= m + 2; ++ i) {
		for (int j = 0; j <= i; ++ j) s[i][j] = ((j > 0 ? s[i - 1][j - 1] : 0) + s[i - 1][j] * j) % mod;
	}
}

int sol(int n, int m) {
	int ans = 0, c = n + 1;
	for (int i = 0; i <= m; ++ i) {
		ans = (ans + s[m][i] * fac[i] % mod * c % mod) % mod;
		c = (c * qPow(i + 2, mod - 2) % mod * (n - i) % mod) % mod;
	}
	return ans % mod;
}

signed main() {
	// freopen("code.in", "r", stdin);
	n = read() % mod, m = read(); init();
	int sum1 = 0, sum2 = 0;
	sum1 = sol(n - 1, m + 1), sum2 = qPow(sol(n - 1, m) % mod, mod - 2) % mod;
	(sum1 *= sum2) %= mod; printf("%lld\n", (n - sum1 + mod) % mod);
	return 0;
}
```

最后修改：2021 年 09 月 28 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

看透一切的人士
催更名人传
看透一切的人士
催更
tham
催更！！！！
wyzwyz
建议把从“小有名气的贫僧”之后的全删了，包括我这句，前面都是一...
潜心学习的打工人
催更

牛客挑战赛36D 排名估算

tony102 • 2020 年 10 月 24 日

[Link](https://ac.nowcoder.com/acm/contest/3782/D)

## Description

## Sol

马老师事件$B_i$为随机一个排名在第$i$名， $P(B_i)=\frac{1}{n}$

设事件$A$为连续$m$次抽排名都没抽中$i$，$P(A) = (\frac{i}{n-1})^m$

那么

$$
P(A|B_i) = (\frac{n-i}{n-1}) ^ m
$$

那么根据全概率公式：

$$
P(A|B) = \frac{1}{n} \sum_{i=1}^{n}  (\frac{n-i}{n-1}) ^ m
$$

再按照贝叶斯公式有：

$$
P(B|A) = \frac{P(A|B)P(B)}{\sum_{i} P(A|B_j)P(B_j)}
$$

现在来计算$E(P(B|A))$，我们已经知道$E(P(B)) = i$

$$
E=\frac{\frac{1}{n} \sum_{i=1}^{n} (\frac{n-i}{n-1}) ^ m \times i}{\frac{1}{n} \sum_{i=1}^{n}(\frac{n-i}{n-1}) ^ m}
$$

可以约掉$\frac{1}{n}$ ，$(\frac{n-i}{n-1}) ^ m$ 注意该项仅仅可以约掉分母

$$
E = \frac{\sum_{i=1}^{n} (n-i)^m \times i}{\sum_{i=1}^{n} (n-i)^m }
$$

对$n-i$这种项的求和倒过来就是$i$了吧，注意换一下后面的乘$i$要变成$n-i$

$$
E = \frac{\sum_{i=1}^{n} i^m \times (n-i)}{\sum_{i=1}^{n} i^m }
$$

把$n$放在外面乘，现在就是

$$
E = n - \frac{\sum_{i=1}^{n} i^{m+1}}{\sum_{i=1}^{n} i^m }
$$

只要进行自然数幂求和就可以了，现在来推倒自然数幂求和公式。题目仅仅要求在$O(m^2)$级别的时间内做到

我们要计算

$$
\sum_{i=0}^{n} i^m
$$

把幂转成第二类斯特林数和下降幂（非常套路

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

把下降幂拆了，约掉分母中的$j!$ 。再把斯特林数提到前面去算

$$
\sum_{j=0}^{m} \begin{Bmatrix}m\\j\end{Bmatrix} \sum_{i=0}^{n} \frac{i!}{(i-j)!}
$$

然后不会算了，改变思路。如果不约掉分母中的$j!$的话

$$
\sum_{j=0}^{m} \begin{Bmatrix} m\\ j\end{Bmatrix} j! \sum_{i=0}^{n}  \binom{i}{j}
$$

这是在上指标求和吧，变成了

$$
\sum_{j=0}^{m} \begin{Bmatrix}m\\j\end{Bmatrix}j!\binom{n+1}{j+1}
$$

直接$O(m^2)$预处理第二类斯特林数，注意到$n$的范围很大所以递推顺便算一下就好了

## Code

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

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

int n, m;
int inv[SIZE], fac[SIZE], s[SIZE][SIZE];

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;
}

牛客挑战赛36D 排名估算

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

名人传

VP: AtCoder Beginner Contest 222(ABC222)

写在 CSP-S2021 前

机房标准化岚语发音对照

VP: AtCoder Beginner Contest 221(ABC221)

Codechef CTREE Chef and Chefcoin

20211101 沙漠绿洲 (desert)

Luogu1891 疯狂 LCM

Luogu5994 [PA2014]Kuglarz

Luogu6280 [USACO20OPEN]Exercise G

牛客挑战赛36D 排名估算

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

牛客挑战赛36D 排名估算

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款