OI 中的概率与期望相关
在 OI 中，我们常讨论离散随机变量。
1. 概率的定义
虽然我们都知道概率是 \(0\) 到 \(1\) 之间的一个数，但在解题时，更推荐大家从集合的角度去理解。
设样本空间为 \(\Omega\)（所有可能发生的结果的集合）。对于 \(\Omega\) 中的每一个随机事件 \(A\)，概率 \(P(A)\) 本质上就是一种衡量 \(A\) 在 \(\Omega\) 中“分量”大小的函数。
它必须满足三条公理（柯尔莫哥洛夫公理）：
- 非负性：\(P(A) \geq 0\)。
- 规范性：\(P(\Omega) = 1\)（整个宇宙发生的概率是 1）。
- 可加性：对于互斥事件（不可能同时发生），概率可以直接相加：\(\sum P(A_i) = P(\bigcup A_i)\)。
2. 古典概型
这是最朴素的情况：每个基本结果发生的概率相等。
比如掷骰子，\(\Omega = \{ 1, 2, 3, 4, 5, 6\}\)，大小为 6。设事件 \(A\) 为“点数大于 4”，则 \(A = \{ 5, 6\}\)，大小为 2。
在 OI 中，很多求概率的问题最终都会转化为计数问题（组合数学），算出可行方案数除以总方案数。
3. 条件概率与独立性
3.1 条件概率
条件概率 \(P(A|B)\) 的直观理解是：已知 \(B\) 发生了，那么 \(\Omega\) 就缩水成了 \(B\)。此时 \(A\) 发生的概率，就是在 \(B\) 这个新世界里，属于 \(A\) 的那部分占比。
公式：
- \(P(AB)\) 是 \(A\) 和 \(B\) 的交集（在原世界的大小）。
- 除以 \(P(B)\) 就是为了把分母归一化，把 \(B\) 当作新的 \(1\)。
例子：掷两颗骰子，已知和为 7（事件 \(B\)，共 6 种情况：1+6, 2+5...），求其中一颗是 1（事件 \(A\)）的概率。
- 满足 \(B\) 的有 6 种。
- 同时满足 \(A\) 和 \(B\) 的只有 (1, 6) 和 (6, 1) 这 2 种。
- 所以 \(P(A|B) = 2/6 = 1/3\)。
3.2 事件的独立性
独立性是概率题中最大的坑点，也是最大的简化工具。
- 直观理解：已知 \(B\) 发生，并不会改变 \(A\) 发生的概率，即 \(P(A|B) = P(A)\)。
- 数学定义：\(A, B \text{ 独立} \iff P(AB) = P(A)P(B)\)。
警示：千万不要凭直觉滥用 \(P(AB) = P(A)P(B)\)。只有当你确定两件事物理上互不干扰（比如掷两个不同的骰子，或者题目明确说明独立）时才能用。如果两件事有因果关系或制约关系，必须用条件概率公式。
4. 全概率与贝叶斯
4.1 全概率公式
当我们很难直接求 \(P(B)\) 时，可以把样本空间切成若干个互不重叠的“碎片” \(A_i\)（比如按第一步的操作分类）。
意义：事件 \(B\) 的总概率 = 在各种情况 \(A_i\) 下 \(B\) 发生的概率的加权平均。这在 DP 转移中体现得淋漓尽致。
4.2 贝叶斯公式
贝叶斯公式是全概率公式的逆过程。通常我们容易算出“因 \(\to\) 果”的正向概率 \(P(\text{果}|\text{因})\)，但有时题目会给你结果，问你起因的概率 \(P(\text{因}|\text{果})\)。
典型案例：某病发病率 \(0.1\%\)。检测准确率 \(90\%\)（有病测出阳性 \(90\%\)，没病测出阴性 \(90\%\)）。
问题：你检测呈阳性（事件 \(T\)），你真的有病（事件 \(D\)）的概率是多少？计算：
\[P(D|T) = \frac{P(T|D)P(D)}{P(T)} = \frac{0.9 \times 0.001}{0.9 \times 0.001 + 0.1 \times 0.999} \approx 0.0089 \]结论：即使阳性，你也只有不到 \(1\%\) 的概率真有病！这就是先验概率（发病率极低）的强大影响力。
5. 数学期望
期望 \(E[X]\) 是随机变量的加权平均值：\(E[X] = \sum x_i P(i)\)。
5.1 期望的线性性质
它的强大之处在于：不需要 \(X\) 和 \(Y\) 独立！ 无论关系多么纠缠不清，只要问的是“和的期望”，就可以拆成“期望的和”。
在 OI 中，常设 \(X_i\) 为指示变量（满足条件为 1，否则为 0）：
5.2 期望的可乘性
仅当 \(X, Y\) 独立时，\(E[XY] = E[X]E[Y]\)。
5.3 赠券收集者问题
问题：有 \(n\) 种卡片，每次买一包得到其中一张（概率均等），集齐 \(n\) 种卡片的期望次数？
倒推逻辑：
手里有 \(k\) 种卡片时，买到一张新卡片的概率是 \(p = \frac{n-k}{n}\)。这是一个几何分布，期望尝试次数就是 \(1/p\)。
结论：
6. 高斯消元与期望 DP
前面的期望 DP 通常是在 DAG（有向无环图）或者是树上进行的，可以倒推或正推。但如果图里有环，状态之间会互相依赖：
对于每一个节点 \(u\)，我们都能列出这样一个线性方程。如果有 \(N\) 个点，我们就得到了一个包含 \(N\) 个变量、\(N\) 个方程的线性方程组。
6.1 高斯消元算法
核心步骤：
- 消元：通过“行变换”，把矩阵变成上三角矩阵。
- 回代：从最后一行往回带，算出 \(x_n, x_{n-1}, \dots, x_1\)。
结果判定：
- 唯一解：完美三角形，对角线系数都不为 0。
- 无解：出现 \(0 = 5\) 这种荒谬行。
- 无穷多解：出现 \(0 = 0\) 这种无效行（存在自由元）。
复杂度：\(O(n^3)\)。在 \(N \le 500\) 左右时可用。