并非这本
概率基础
古典概型
- 样本空间有限
- 基本事件等可能发生
若事件 \(A\) 包含 \(k\) 个基本事件，样本空间有 \(n\) 个基本空间。
于是显然就有:
\[P(A) = \frac{k}{n}
\]
条件概率
- \(P(B | A)\) 表示在 \(A\) 发生的情况下 \(B\) 发生的概率
有：
\[P(B | A) = \frac{P(AB)}{P(A)}
\]
画个图的话就是：
乘法原理
\[P(AB) = P(A)P(B|A)
\]
\[P(ABC) = P(A)P(B|A)P(C|AB)
\]
那么如果 \(A,B\) 独立就有：
\[P(AB) = P(A)P(B)
\]
全概率公式与贝叶斯公式
设样本空间为 \(S\)，\(B_1, ..., B_n\) 是 \(S\) 的一个划分，有
\[P(A) = \sum_{i = 1}^{n} P(A|B_i)P(B_i)
\]
这就是全概率公式。
定义如上，还有：
\[P(B_i|A) = \frac{P(A|B_i)P(B_i)}{\sum_{j = 1}^{n} P(A|B_j)P(B_j)}
\]
这就是贝叶斯公式。
以上公式感觉画个图是好理解的，并可证明：
连续性随机变量的分布与密度函数
随机变量 \(X\) 的分布函数：
\[F(x) = P \{ X \le x \}
\]
密度函数 \(f(x)\) 满足：
\[F(x) = \int_{-\infty}^{x} f(t)dt
\]
积分感性理解一下就是面积，和求导为逆运算。
感觉以上的知识对我们解决 OI 题没有任何帮助。
我们会前置知识 \(1\) 了，现在来杀穿 校OJ 的训练吧！
绑鞋带
我们不妨设现在已经连成链的有 \(i\) 个，则下次练成一条链的概率为：
\[\frac{2n - 2i - 2}{2n - 2i - 1}
\]
答案就为：
\[\prod_{i = 0}^{n - 2} \frac{2n - 2i - 2}{2n - 2i - 1}
\]
神盾局特工
如何呢，状压DP 秒了。
Bad Luck Island
我们设 \(dp_{i,j,k}\) 表示三种人每种分别还剩这么多的概率，转移是好转的
数学期望
设 \(E(X)\) 表示随机变量的期望，就有：
\[E(X) = \sum {x \cdot p_x}
\]
实际上就是值乘概率。
如果随机变量 \(X\) 是连续的，就有：
\[E(X) = \int_{-\infty}^{\infty} tf(t)dt
\]
我们会前置知识 \(2\) 了，现在来杀穿 校OJ 期望的训练吧！
B君的连通
答案很好推，为
\[2^{n - 2} (n - 1) + 2^{n - 1}
\]
Ilya and Escalator
我们考虑设 \(dp_{i,j}\) 表示第 \(i\) 秒，有 \(j\) 个人在电梯的概率，转移好转，之后用定义式即可。
绿豆蛙的归宿
一讲期望就绕不开这一题，我们建反图，然后设 \(dp_i\) 表示 \(i \to n\) 的期望步数，然后跑拓扑排序，有转移：
\[\frac{1}{deg_v}(dp_u + val) \to dp_v
\]
为什么不能正着跑：
因为到达每个点的概率不同，我们上述 dp 设计不用考虑此问题。
如果自己向自己连边或连成个环怎么办？
我们只需要带入之后解方程即可。