标签 概率期望 下的文章

「2019 Multi-University Training Contest 2」Everything Is Generated In Equal Probability

题目链接：HDU 6595

Y_UME 有一个整数 $N$ 和一串有趣的代码：

首先，他先等概率随机一个正整数 $n \in [1, N]$，再等概率随机一个长度为 $n$ 的排列。最后他会将这个排列传入函数 $\text{Calculate}$ 并得到一个返回值。请你求出这个值的期望，答案对 $998244353$ 取模。

本题有多组数据。

数据范围：$1 \le N \le 3000$，$\sum N \le 5 \times 10 ^ {4}$。

「Codeforces 1156F」Card Bag

题目链接：Codeforces 1156F

你有一个装有 $n$ 张卡片的袋子，第 $i$ 张卡片上的数字为 $a_i$。

接下来你要玩一个卡片游戏。每一回合，你会随机选择选择袋子里的一张卡片（所有留在袋子里的卡片都是等概率选择的）。从第二回合起，每当你拿出一张卡片（将上面的数字记为 $x$），你都会和上一回合的卡片（将上面的数字记为 $y$）比较：

• 如果 $x < y$，你将会输掉游戏，游戏结束。
• 如果 $x = y$，你将会赢得游戏，游戏结束。
• 如果 $x > y$，游戏继续。

如果袋子里没有卡片了，那么你也将输掉游戏。注意：你取出来的卡片不会重新放回袋子里。

请你求出赢得游戏的概率，答案对 $998244353$ 取模。

数据范围：$2 \le n \le 5000$，$1 \le a_i \le n$。

「Codeforces 1153F」Serval and Bonus Problem

题目链接：Codeforces 1153F

你有一条长度为 $l$ 的线段，我们通过随机选择 $2$ 点，在这条线端上随机选择 $n$ 条线段。这 $2n$ 个点将线段分成了 $2n + 1$ 个区间。你需要对于给定的 $k$，求出被这 $n$ 个随机线段中至少 $k$ 个覆盖的区间的期望总长度。答案对 $998244353$ 取模。

数据范围：$1 \le k \le n \le 2000$，$1 \le l \le 10 ^ 9$。

「Codeforces 1139D」Steps to One

题目链接：Codeforces 1139D

Vivek 最初有一个空数组 $a$ 和一个整数 $m$。接下来他会进行如下操作：

1. 随机选择一个 $1$ 到 $m$ 之间的整数 $x$ 并将它加入到数组 $a$ 的最后。
2. 计算出数组 $a$ 中元素的最大公约数。
3. 如果最大公约数等于 $1$ 那么退出操作。
4. 否则回到步骤 $1$。

请你计算出数组 $a$ 的期望长度，对 $10 ^ 9 + 7$ 取模。

数据范围：$1\le m \le 10 ^ 5$。

「Codeforces 280C」Game on Tree

题目链接：Codeforces 280C

Momiji 有一棵包含 $n$ 个节点的有根树。节点从 $1$ 到 $n$ 编号，其中根节点的编号为 $1​$。Momiji 打算在这棵树上玩一个游戏。

整个游戏包含很多步。每一步，Momiji 选择一个存在的节点，然后把这个节点作为根的子树删除，选择的节点本身也被删除。当这棵树为空时，游戏结束。换言之，当节点 $1$ 被删除后游戏结束。

你需要求出游戏结束的期望步数。

数据范围：$1 \le n \le 10 ^ 5$。