第一张在 Qzone 上传的照片，2016 年暑假。 这也是一切的起点吧~
写的很烂。
一. 样本点，样本空间，随机事件
一个随机现象中可能发生的不能再细分的结果成为样本点。所有样本点组成的集合称为样本空间，用 $\Omega$ 表示。
一个随机事件为 $\Omega$ 的子集，由若干样本点组成，用大写字母表示。
对于随机现象的结果 $\omega$ 和随机事件 $A$，称事件 $A$ 发生当且仅当 $\omega\in A$。
二. 概率函数
性质：
- 概率函数是事件域到 $[0,1]$ 的映射，即 $\forall A\in\Omega, P(A)\in[0,1]$.
- $P(\Omega)=1$
- $P(A+B)=P(A)+P(B)-P(AB)$，其中 $A+B=A\cup B, AB=A\cap B$。
三、条件概率：
$P(A|B)$ 指在事件 $B$ 发生的条件下，事件 $A$ 发生的概率，称为条件概率。
两个公式：
- 概率乘法公式：$P(A\cap B)=P(A)P(B|A)$.
- 全概率公式：若一组事件 $A_1,A_2,\cdots,A_n$, $\forall i,j\in[1,n],i\not=j$ 有 $A_i\cap A_j=\phi$ 且 $\bigcup\limits_{i=1}^n A_i=\Omega$，则对于任意事件 $B$ 有 $P(B)=\sum\limits_{i=1}^nP(A_i)P(B|A_i)$.
Bayes 公式：
基本形式：$P(B|A)=\dfrac{P(A|B)P(B)}{P(A)}$
证明：由概率乘法公式，$P(MN)=P(M)P(N|M)$. 则有： $$P(B|A)=\dfrac{P(AB)}{P(A)}$$ $$P(A|B)=\dfrac{P(AB)}{P(B)}$$ 二式相除，即得证。
含全概率公式的 Bayes 公式： $$P(A_i|B)=\dfrac{P(A_iB)}{P(B)}=\dfrac{P(A_i)P(B|A_i)}{\sum\limits_{j=1}^nP(A_j)P(B|A_j)}$$ 证明将全概率公式代入上证明即可。
例：某地疫情发病率为 $0.04%$，现用某抗原进行检测。已知患病患者检测结果 $99%$ 为阳性，没患病的人检测结果 $99%$ 为阴性。若某人检测结果为阳性，那他真的得病的概率为多少？
我们设事件 $A$ 指该人得病，事件 $B$ 指检测结果为阳性。则根据题目，有 $P(B|A)=99%,P(B|\overline A)=1%,P(A)=0.04%,P(\overline A)=99.96%$。 所求即为 $P(A|B)$. 根据 Bayes 公式以及全概率公式，有： $$P(A|B)=\dfrac{P(AB)}{P(B)}=\dfrac{P(A)P(B|A)}{P(A)P(B|A)+P(\overline A)P(B|\overline A)}\approx28.4%.$$
独立性
主观地说，事件 $A$ 与事件 $B$ 无关时，则称事件 $A$ 与事件 $B$ 是相互独立的。下面给出定义。
定义： 若在同一概率空间中，若对于多个事件 $A_1,A_2,\cdots,A_n$ 中任意一组事件都有 $P(A_{i_1},A_{i_2},\cdots,A_{i_m})=\prod\limits^m_{k=1}P(A_{i_k})$，则称这些事件 相互独立。 若在同一概率空间中，若对于多个事件 $A_1,A_2,\cdots,A_n$ 中任意两个事件都有 $P(A_iA_j)=P(A_i)P(A_j)$，则称这些事件 两两独立。
显然，相互独立的性质要强于两两独立。
四、期望：
随机变量
简单地说，随机变量即为样本空间到实数集的映射。
离散型随机变量
若离散型随机变量 $X$ 的概率分布为 $p_i=P{X=x_i}$ 且 $\sum x_ip_i$ 绝对收敛，则这个值称为 $X$ 的期望，记为 $E(X)$。
连续型随机变量
若连续型随机变量 $X$ 的密度函数为 $f(x)$ 且 $\int_\mathbb{R} f(x)\mathrm{d}x$ 绝对收敛，则这个值称为 $X$ 的期望，记为 $E(X)$。
性质
- $E(aX+b)=a\cdot E(X) + b$。
- $E(X+Y)=E(X)+E(Y)$。 若 $X,Y$ 相互独立，则有 $E(XY)=E(X)\cdot E(Y)$。 特别地，上述性质中的独立性并非必要条件。
五、例题
ABC382E
题 意：一包牌由 $N$ 个卡片组成，其中第 $i$ 个卡片为金卡的概率为 $P_i$，求一包一包地开，开到至少 $X$ 张金卡的期望次数为多少。
分析： 设 $Pc(i,j)$ 表示这一包牌的前 $i$ 开了，获得了 $j$ 张金卡的概率。则易得 $Pc(i,j)=Pc(i-1,j-1)\times(1-P_i)+Pc(i-1,j)\times P_i$。 设 $E(i)$ 表示开到 $i$ 张金卡的期望次数，则 $E(i)=\sum\limits_{j=0}^n E(i-j)\times Pc(n,j)+1$。 然而，我们却注意到 $j=0$ 时，我们会使用 $E_i$ 本身更新 $E_i$ 这显然是不可取的。于是，我们需要进行如下变形： $$E(i)=\sum\limits_{j=1}^n E(i-j)\times Pc(n,j)+E(i)\times Pc(n,0)+1$$ $$(1-Pc(n,0))E(i)=\sum\limits_{j=1}^n E(i-j)\times Pc(n,j)+1$$ $$E(i)=\dfrac{\sum\limits_{j=1}^n E(i-j)\times Pc(n,j)+1}{1-Pc(n,0)}$$
$E(X)$ 即所求。
ABC382E Code
|
|
Luogu P1365
题
意：给出一个包含 o, x, ? 的串 $s$，连续的 $n$ 个 o 的贡献为 $n^2$，? 是未填的位置，求贡献的期望。
分析：设 $E_s(i)$ 为以第 $i$ 个字符为结尾的串的期望，$E_l(i)$ 为到第 $i$ 位期望的连续 o 的长度。
则考虑第 $i$ 位字符：
- 若 $s_i=\mathrm{x}$，则 $E_l(i)=0$, $E_s(i)=E_s(i-1)$。
- 若 $s_i=\mathrm{o}$，则 $E_l(i)=E_l(i-1)+1$，$E_s(i)=E_s(i-1)+[E_l(i)^2-E_l(i-1)^2]=E_s(i-1)+2E_l(i-1)+1$.
- 若 $s_i=\mathrm{?}$，此时有 $\dfrac1 2$ 的概率当前位填 $\mathrm o$，$\dfrac1 2$ 的概率当前位填 $\mathrm x$。由离散期望定义易得 $E_l(i)=P(s_i=\mathrm{o})\times (E_l(i-1)+1)+P(s_i=\mathrm{x})\times 0=\dfrac{E_l(i-1)+1}{2}$，同理，$E_s(i)=E_s(i-1)+\dfrac{E_l(i)^2-E_l(i-1)^2+1}{2}=E_s(i-1)+\dfrac{2E_l(i-1)+1}{2}$。
以上，即可 dp 求解。
Luogu P1365 Code
|
|
NOIp2016 tgDay1T3 换教室
题 意：$v$ 个教室，原定第 $i$ 堂课所在教室为 $c_i$，可以申请更改为 $d_i$，申请通过通过率为 $p_i$，共有 $m$ 次申请次数。教室构成一张无向连通图，体力消耗为每两节课教室之间距离之和。试最小化体力消耗的期望。
分析：自然想到设计 $E2(i,j),E1(i,j)$ 表示前 $i$ 节课已经申请过 $j$ 次，第 $i$ 次换/不换的最小期望。对于第 $i$ 节课，考虑换或是不换。若不换，继续考虑上一节课换/不换带来的贡献，换成功带来的贡献为 $p_{i-1}\times\mathrm{dis}(d_{i-1},c_i)$，失败的带来的贡献为 $(1-p_{i-1})\times\mathrm{dis}(c_{i-1},c_i)$，故 $E1(i,j)=\min{E1(i-1,j)+\mathrm{dis}(c_{i-1},c_i),E2(i-1,j)+p_{i-1}\times\mathrm{dis}(d_{i-1},c_i)+(1-p_{i-1})\times\mathrm{dis}(c_{i-1},c_i)}$。同理，若换，继续考虑第 $i-1$ 是否换，不换则类似于 $E1$ 转移式中第二种情况，换则分四种情况讨论：（成功，成功），（成功，失败），（失败， 成功），（失败， 失败）。最后答案为 $\min\limits_{i=0}^m \min {E1(n,i), E2(n,i)}$。
NOIp2016 tgDay1T3 换教室 Code
|
|
Luogu P5249
题 意：$n$ 个人从第 $1$ 个开始轮流朝自己开枪，射中的概率均为 $P_0$，剩下的最后一个人为胜利者。求第 $k$ 个人胜利的概率。特别的，若 $P_0=0$，则认为第一个人胜利。
分析：设 $P(i,j)$ 指剩余 $i$ 人，第 $j$ 人获胜的概率。考虑从第一个人开始，若射中，则剩下 $i-1$ 人，原先的第 $j$ 个人变为 $j-1$，对于 $P(i,j)$ 的贡献为 $P_0\times P(i-1,j-1)$；若没中，则仍有 $i$ 人，由于游戏继续，故当前的第 $j$ 人仍变成第 $j-1$ 人，做出贡献为 $(1-P_0)\times P(i,j-1)$。考虑第 $1$ 个人胜利的情况。此时其为第一个开枪者，绝对不中，而轮到下一个人后，其便成为第 $i$ 个人，故概率为 $(1-P_0)\times P(i,i)$。综上，如下： $$P(i,j)=\begin{cases}P_0\times P(i-1,j-1)+(1-P_0)\times P(i,j-1), & j\ge 2 \ (1-P_0)\times P(i,i) & j=1\end{cases}$$
呈环形结构，考虑变形。设 $P(i,1)=x$，则情况 1 2 联立必可构造出形如 $ax+c=0$ 的方程，解之即可。
由于本题空间较小，故需滚动数组优化。
Luogu P5249 Code
|
|