（未完待更！！！！！！！！！！！！！！！！！！！！！！！）
概率
概率空间
一个概率空间是一个三元组 ((Omega,F,mathrm P))，其中
- (Omega) 是样本空间，其中的样本记作 (omega)，任意时刻存在且有唯一 (omegainOmega) 发生；
- 一个事件 (A) 是 (Omega) 的一个子集，(A) 发生当且仅当某个 (omegain A) 发生；若事件 (Acap B=varnothing) 则称 (A,B) 互斥，它们不可能同时发生。(F) 是事件集合，即所有可能的 (A) 的集合（事实上这玩意很鸡肋，一般就认为 (F=2^{Omega}) 吧）；
- 函数 (mathrm P:F o R) 是概率测度，满足三条公理：
- 非负性：对任意 (Ain F) 有 (mathrm P(A)geq 0)；
- 规范性：(mathrm P(Omega)=1)；
- 可加性：对有限个或无限但可列个两两互斥的事件 ({A_i})，有 (mathrm P!left(igcuplimits_iA_i ight)=sumlimits_imathrm P(A_i))，易证 RHS 这个无穷级数是绝对收敛的，于是不需要关心求和顺序，计算该集合的元素和是合理的。
将事件看成样本的集合后，概率问题便可以类似组合计数来处理（可加性说明了为什么概率满足容斥原理）。
条件概率
在概率空间 ((Omega,F,mathrm P)) 中，对 (A,Bin F)，记 (mathrm P(Bmid A)) 为事件 (A) 发生的条件下事件 (B) 的概率（必有 (mathrm P(A)>0)，否则无意义）。考虑如何计算它：(A^{mathrm C}) 中的样本都不可能发生了，于是我们可以新建一个概率空间，其中 (Omega'=A,F'=2^{A})。(mathrm P') 又如何呢？与 (A^{mathrm C}) 有交的事件抛弃，(A) 的子集的概率测度原封不动？这就不满足规范性了，为了解决这个问题，我们可以令对 (forall Csubseteq A) 都有 (mathrm P'(C)=dfrac{mathrm P(C)}{mathrm P(A)})。回到计算条件概率的问题上来，(B) 中仅剩下属于 (A) 的样本有效，于是 (mathrm P(Bmid A)=mathrm P'(Acap B)=dfrac{mathrm P(Acap B)}{mathrm P(A)})，这便是条件概率的计算公式。
将 (mathrm P(A)) 移到左边并根据轮换性扩展得到 (mathrm P(Acap B)=mathrm P(A)mathrm P(Bmid A)=mathrm P(B)mathrm P(Amid B))，这是概率的乘法原理，符合「分步相乘」的直觉。
根据 (mathrm P(A)mathrm P(Bmid A)=mathrm P(B)mathrm P(Amid B)) 得到 (mathrm P(Bmid A)=dfrac{mathrm P(B)mathrm P(Amid B)}{mathrm P(A)})，这是贝叶斯公式，运用它可以轻松计算逆向概率。P.S. 一个生 动 形 象的例子：虽然 NOI 不考多项式，但是 jxd 选手基本都会多项式，根据贝叶斯公式有 (mathrm P( ext{jxd}mid ext{会多项式})=dfrac{mathrm P( ext{jxd})mathrm P( ext{会多项式}mid ext{jxd})}{mathrm P( ext{会多项式})})，根据条件 (mathrm P( ext{会多项式}mid ext{jxd})approx1)，而 (mathrm P( ext{会多项式})ll 1)，可知 (mathrm P(mathrm{jxd}mid 会多项式)ggmathrm P( ext{jxd}))，也就是说学多项式能给进 jxd 增加很大的概率，所以要学！
若对事件 (A,Bin F) 满足 (mathrm P(Acap B)=mathrm P(A)mathrm P(B))，则称 (A,B) 相互独立。这就是说，(mathrm P(A)=mathrm P(Amid B),mathrm P(B)=mathrm P(Bmid A))，它们发生与否对对方的概率没有影响。
全概率公式
对事件 (Ain F)，注意到若可列个事件 ({B_i}) 是样本空间 (Omega) 的一个划分（即两两不交且并和等于 (Omega)），则 ({Acap B_i}) 是 (A) 的一个划分，于是有 (mathrm P(A)=sumlimits_imathrm P(Acap B_i))（易证无穷级数的绝对收敛性），这是全概率公式，同时也是概率的加法原理，符合「分类相加」的直觉。
将加法原理和乘法原理结合起来可以得到 (mathrm P(A)=sumlimits_imathrm P(B_i)mathrm P(Amid B_i))。
期望
随机变量、期望
在概率空间 ((Omega,F,mathrm P)) 中，一个函数 (X:Omega o R) 称为一个随机变量。设 (X) 的值域为 (mathrm R)，那么事件的集合 ({X=xmid xin mathrm R}) 天然地成为 (Omega) 的一个划分。这篇文章中只考虑 (mathrm R) 可列的情况，这样 (X) 称为离散型随机变量（绝大多数 OI 题都不会涉及到非离散型，即使涉及到了可能也不涉及稍难的概率论内容）。
对一个随机变量 (X)，定义它的期望 (mathrm E(X)=sumlimits_{xinmathrm R}xmathrm P(X=x))。若 (Omega) 可列，还可以表示为 (mathrm E(X)=sumlimits_{omegainOmega}X(omega)mathrm P(omega))，其中 (mathrm P(omega)=mathrm P({omega}))。涉及到的无穷级数都易证绝对收敛性。
对两个随机变量 (X,Y)，若 ({X=xmid xin mathrm R_X} imes{Y=ymid yin mathrm R_Y}) 中每一对事件都相互独立，则称 (X,Y) 相互独立。
期望的数乘、和、乘积
期望满足线性性，即对两个随机变量 (X,Y) 以及常数 (a,b) 有 (mathrm E(aX+bY)=amathrm E(X)+bmathrm E(Y))，这通过期望的定义很容易证明，只需要对 ({(X=x)cap(Y=y)mid xin mathrm R_X,yin mathrm R_Y}) 中的事件逐一讨论即可，易证这是 (Omega) 的一个可列划分。
对两个相互独立的随机变量 (X,Y)，它们乘积的期望等于期望的乘积，证明：
条件期望、全期望公式
对随机变量 (X) 和事件 (Ain F)，类似条件概率那样，考虑给 (X) 加上先决条件 (A) 会发生什么。那么对 (forall xin mathrm R) 显然都有 (mathrm P(X=xmid A)=dfrac{mathrm P((X=x)cap A)}{mathrm P(A)})，这包含了加上先决条件 (A) 的 (X) 的全部信息，我们称新产生的随机变量为条件随机变量 (Xmid A)，它定义在新概率空间 (left(Omega'=A,F'=2^A,P' ight)) 上。条件随机变量 (Xmid A) 的期望 (mathrm E(Xmid A)) 为条件期望，显然有 (mathrm E(Xmid A)=dfrac{sumlimits_{xinmathrm R}xmathrm P((X=x)cap A)}{mathrm P(A)})，这是条件期望的计算公式。
对 (Omega) 的一个可列划分 ({A_i})，有 (mathrm E(X)=sumlimits_{i}mathrm P(A_i)mathrm E(Xmid A_i))（易证无穷级数绝对收敛性），这是全期望公式，也是期望的加法原理。证明：
回顾到随机变量可以自然地形成样本空间的一个划分这个特性，注意到全期望公式的 RHS 恰好是「概率乘以值的和」的形式，考虑用另一个随机变量 (Y) 来表示 ({A_i})，有 (mathrm E(X)=sumlimits_{yinmathrm R_Y}mathrm E(Xmid Y=y)mathrm P(Y=y))，那么考虑另一个划分方式与 (Y) 相同但是当 (Y=y) 时值为 (mathrm E(Xmid Y=y)) 的随机变量 (Z)，有 (mathrm E(X)=mathrm E(Z))，不规范地写成 (mathrm E(X)=mathrm E(mathrm E(Xmid Y)))，这是全期望公式的另一种形式，个人不太喜欢。
例题：CF123E - Maze
一开始的样本空间是所有可能的走位方案集合，每个方案是一个经过的边的序列吧，那么每个样本的随机变量取值是包含的边的数量，问的是这个随机变量的期望。这个概率空间的概率测度不是通过确定每个样本的概率而确定的，而是给出走位的转移概率分布，这就不太好直接通过样本来求事件的概率，而要间接的通过其它较好求的事件以及给定条件求事件概率。
先使用全期望公式，哼哼哈嘿！(ans=sumlimits_{i=1}^nsum_limits{j=1}^nmathrm P( ext{起点选}i)mathrm P( ext{终点选}j)mathrm E(Xmid ext{起点选}i, ext{终点选}j))。那考虑对每个条件期望进行分析，此时样本空间变成了所有起点为 (i) 终点为 (j) 的走位方案集合。
接下来使用期望的线性性，哼哼哈嘿！将定义在新概率空间上的 (X(omega)) 等于 (omega) 包含的边数这个随机变量按边拆成若干个小随机变量，这很自然。设 (X_e(omega)) 表示 (omega) 包含的边 (e) 的次数，那么有 (X=sumlimits_eX_e)，根据线性性有 (mathrm E(X)=sumlimits_emathrm E(X_e))，对所有 (mathrm E(X_e)) 逐一分析。
令 (i) 为根，那么边可以分成三类。
- 在子树 (j)，永远不可能走到，(X_e=0) 恒成立，(mathrm E(X_e)=0)；
- 在 (i o j) 路径上，只能走一次，(X_e=1) 恒成立，(mathrm E(X_e)=1)；
- 其它情况，那么可以找到这条边下端与 (j) 的 LCA，在 LCA random_shuffle 的时候，如果通向 (j) 的儿子排在通向 (e) 的儿子前面，那儿肯定走不到 (e)，否则肯定能走到 (e) 并且还要回来。而这两种是对称的，所以 (mathrm P(X_e=0)=mathrm P(X_e=2)=0.5)，所以 (mathrm E(X_e)=1)。
综上 (mathrm E(X)) 就是 (n-sz_j)。那考虑怎么求这个 (mathrm O!left(n^2 ight)) 的全期望公式，固定根的时候 (sz) 相当于一个树形 DP，换根就可以了，复杂度线性。