题意#

A 和 B 正在进行一场射箭比赛。他们轮流射击靶子，A 先射。每次射击时，A 射中靶子的概率是 $\frac{a}{b}$，而 B 射中靶子的概率是 $\frac{c}{d}$。第一个射中靶子的人将赢得比赛。求 A 赢得比赛的概率。

观察#

1. 比赛可能无限次进行下去

2. 可以用无穷幂级数表示最后结果

3. 公式：$S = \dfrac{a_1}{1 - r}, when |r| < 1$ (来自于等比数列求和公式，分子由于无穷小变为1, |r| < 1 保证收敛)

这里 $a_1 = \frac{a}{b}, r = (1 - \frac{a}{b})(1 - \frac{c}{d})$

代入化简即可

Link | 回忆

题意#

给定一个排列，求经过若干次变换后，排列整体有序的概率。

变换的规则如下：给定 r 和 q, 表示这次变换有 p 的概率使得现在的排列中前 r 个数字变为有序，有 (p - 1) 的概率不变。

观察#

1. 如果最后 k 个元素没有在它们应该在的位置，那么对于所有 $r <= (n - k)$ 的变换，无法使得整个排列整体有序，因此可以直接忽略。

2. 反过来的写法，也就是求出失败的概率，再用 1 来减的写法更好写。（不过回忆中并不是这样写的）

3. 只考虑 r 足够大的变换。对于每个这样的变换遍历，求条件概率之和。

Link | 回忆

题意#

有 n 个人环状坐下。每个人有一个范围 [l, r]，按照均匀分布从这个范围中取一个数字。

给定一个质数 p ，如果相邻两个人（注意环状）取的数字相乘的结果为 p 的倍数，则获得 2000 奖励。请问奖励的期望。

观察#

1. 期望具有线性性质，即总期望等于各个部分期望的和。

2. 快速计算 [l, r] 中，为 p 的倍数的数量：类似前缀和思想。

Link | 回忆

题意#

圣诞老人收到了来自 n 个不同孩子的信件。每个孩子都希望从圣诞老人那里得到一些礼物：具体来说，第 i 个孩子要求圣诞老人给他们 ki 种不同物品中的一种作为礼物。有些物品可能被多个孩子要求。

圣诞老人非常忙，所以他希望新年机器人（Bot）为所有孩子选择礼物。然而，机器人选择礼物的算法存在错误。为了给某个孩子选择礼物，机器人执行以下步骤：

1. 从所有 n 个孩子中均匀随机选择一个孩子 x；
2. 从孩子 x 想要的 kx 个物品中均匀随机选择一个物品 y；
3. 从所有 n 个孩子中均匀随机选择一个孩子 z（这个选择与选择 x 和 y 是独立的）；

• 这样得到的三元组 (x, y, z) 称为机器人的“决策”。

如果孩子 z 在他们的愿望清单中列出了物品 y，那么这个决策是有效的；否则，决策是无效的。

圣诞老人想知道按照上述算法生成的一个决策是有效的概率是多少。

观察#

1. 前两步与第三步是独立关系，因此可以分别计算概率相乘得到联合概率。

2. 逆元的求解：根据费马小定理，当 p 与 x 互质时，$x^{p-2}$ 就是 x 在模 p 下的乘法逆元。通过快速幂求解。

3. 由于在模意义下，因此线性求和即可。

Link | 回忆

题意#

有 n 个不同的类别和 s 个不同的子系统。每天随机发现一个类别和子系统的组合（每个组合等概率）。求发现每个类别至少一次且每个子系统至少一次的期望天数。

观察#

1. 可以将问题分解为多个子问题：当前已经满足了 i 个类别和 j 个子系统的情况下，期望还需多少天满足总条件？

2. 问题之间存在依赖关系。借此想到使用期望 DP 求解。使用期望 DP 时，正推求概率，逆推求期望，这里逆推(即求当前条件下“还需”多少天，而不是“需要”多少天达到当前条件)。

3. 边界：dp[n][s] 及之后均为0，需逆推求解 dp[0][0]

4. 转移：dp[i][j] 条件下： 转移到 dp[i][j] 的概率为 $\frac{i}{n} * \frac{j}{s}$ dp[i + 1][j]: $\frac{n - i}{n} * \frac{j}{s}$ dp[i][j + 1]: $\frac{i}{n} * \frac{s - j}{s}$ dp[i + 1][j + 1]: $\frac{n - i}{n} * \frac{s - j}{s}$

坑#

1. 注意除零的情况

2. 进行有理化，防止丢失精度(后来发现不有理化也可以)

Link | 回忆

题意#

观察#

Link | 回忆

题意#

观察#

Link | 回忆