说句鲜花：明天就是月考，马上就是 csp。但是不想学有用的东西，就写了这篇博客。
严格数学公理体系：（水平不够，暂略）
贝叶斯公式： 定义 \(P(A|B)\) 为发生 \(B\) 事件下发生 \(A\) 事件的概率。则有
\(P(A|B) = \dfrac{P(B|A)P(A)}{P(B)}\)
证明：由于 \(P(A|B)P(B) = P(B|A)P(A) = P(A\cap B)\)，即证。
例：假设某种疾病的发病率是 \(0.01\%\)。现有一种试剂可以检验患者是否得病，它的准确率是 \(99\%\)，即在患者确实得病的情况下，它有 \(99\%\) 的可能呈现阳性。它的误报率是 \(1\%\)，即在患者没有得病的情况下，它有 \(1\%\) 的可能呈现阳性。现有一个病人的检验结果为阳性，请问他确实得病的可能性有多大？
解：套公式：
\[\begin{aligned} P(得病|阳性) &= \dfrac{P(阳性|得病)P(得病)}{P(阳性)}\\ &=\dfrac{P(阳性|得病)P(得病)}{P(阳性\cap不得病) + P(阳性\cap得病)}(对立事件) \\ &=\dfrac{0.99\times0.0001}{0.0001\times0.99+(1-0.0001)\times0.01}\\ &\thickapprox0.0098 \end{aligned} \]可见，他实际得病概率很低。这是由于误报率要比得病率大很多。
期望： 定义：略。可以简单理解为概率与值的加权平均。在经过充分多的实验后，每次实验的值的算术平均就趋近于期望。
例1：掷色子，充分多次后的点数的算术平均是多少？
解：即为期望 \(E(X) = \sum^6_{i=1}{i\times\frac{1}{6}} = 3.5\)
性质：若随机变量 \(X, Y\) 的期望存在，则
- 对任意实数 \(a, b\)，有 \(E(aX + b) = a \cdot EX + b\)。
- \(E(X + Y) = EX + EY\)。
例2：在 \([0,1]\) 上随机等概率地取两个点 \(A,B\)，求 \(\overline{AB}\) 长的期望。
解：注意到 \(\overline{AB}\) 长的期望等于随机取一点落在 \(\overline{AB}\)上的概率。
我们再取一点 \(C\)。由于 \(A,B,C\) 均是等概率取得，故它们各个大小关系的概率是相等的，共 \(3!\) 种。而 \(C\) 落在 \(\overline{AB}\) 等价于 \(A \le C \le B\) 或 \(B \le C \le A\)。故 \(P(C\in\overline{AB}) = \frac{2}{3!} = \frac{1}{3}\)
各种分布：略。
例题：(由于大部分题复杂度都是 \(\mathcal{O(n)}\) 的，数据范围也都是 \(n=10^5\) 这个量级，数据范围就不标了)
1. 洛谷 P2719 搞笑世界杯
有 A B 两种票各 \(n\) 张。\(2n\) 个人随机等概率买到 A B 中的一张，直至一种票卖完后剩余的人全买剩下的那一种。求最后两个人买到同一张票的概率。
解法1：推式子。
总样本数为\(\tbinom{2n}{n}\)
最后两个人买到同一张票的样本数即为总样本数减去都不相同的样本数。这样更好计算。
不相同的样本数为前 \(2n-2\) 个人刚好买了每种票各 \(n - 1\) 张的样本数。故为\(\tbinom{2n - 2}{n - 1}\)。
所以 \(P(最后两个人不相同)=\dfrac{\tbinom{2n - 2}{n - 1}}{2^{2n - 2}}\)。
最后答案就是 \(1 - \dfrac{\tbinom{2n - 2}{n - 1}}{2^{2n - 2}}\)
继续化简得
\[\begin{aligned} &=1 - \dfrac{(2n-2)!}{(n-1)!\times (2n-2-(n-1))! \times 2^{2n-2}}\\ &=1-\dfrac{\displaystyle{\prod^{2n-2}_{i=n}i}}{(n-1)!4^{n-1}}\\ &=1-\displaystyle{\prod^{2n-2}_{i=n}\dfrac{i}{(i-n+1)\times4}} \end{aligned} \]这样变乘变除而非分子分母分别计算就有效避免了精度问题。
代码如下:
lf res = 1.0, ans = 1.0;
for (int i = n; i <= 2 * n - 2; i++) {
res *= i * 1.0 / (i - n + 1.0) / 4.0;
}
ans -= res;
方法二：概率 dp
设 dp[x][y] 为 剩余 \(x\) 种 A，\(y\) 种 B 时，最后两张相同的概率。考虑递推。
当 \(x \le 1 \and y \le 1\) 时，不可能最后两张相同，dp[x][y] = 0;
当 \(x = 0 \or y = 0\) 时（不同时小于 \(2\)），一定最后两张相同。dp[x][y] = 1;
其他情况，当第 \(x+y\) 次选中 A 时，即为 dp[x-1][y]；选中 B 时，即为 dp[x][y-1]。由于两种情况概率均为 \(0.5\)，故 dp[x][y] = 0.5 * dp[x-1][y] + 0.5 * dp[x][y-1];
代码如下：
for (int i = 2; i <= n; i++) {
dp[i][0] = dp[0][i] = 1;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
dp[i][j] = 0.5 * dp[i - 1][j] + 0.5 * dp[i][j - 1];
}
} // ans = dp[n][n]
2. 洛谷P4316 绿豆蛙的归宿
题意：给出一个 \(n\) 个点 \(m\) 条边的简单 DAG，边权全正，且从任何点都可到终点 \(n\)。每次从当前点的所有出边中等概率随机选择到下一个点。求从 \(1\) 到 \(n\) 的路径期望。
解：dp。
设 p[x] 为 \(1\) 到 \(x\) 的概率， E[x] 为从 \(1\) 到 \(x\) 的期望，in[x] 入度，out[x] 为出度，G[u] 包括以 \(u\) 为起点的所有边。dp 时应该按拓扑序。因此我们可以一边拓扑排序一边 dp。
p[x] 的状态转移方程为 \(\displaystyle{p_u = \sum^{out_u}_{v\in{G_u}} \dfrac{p_v}{out_v}}\)
E[x] 的状态转移方程为 \(\displaystyle{E_u=\sum^{out_u}_{v\in{G_u}} \dfrac{E_v+p_u\times w}{out_v}}\)，其中 \(w\) 为 \((u,v)\) 的权。（证明可以用期望的线性性质）
代码：
queue<int> q;
for (int i = 1; i <= n; i++) {
if (in[i] == 0) q.push(i);
}
E[1] = 0.0; p[1] = 1.0;
while (!q.empty()) {
int u = q.front(); q.pop();
for (auto x : g[u]) {
int v = x.to, w = x.val;
p[v] += p[u] / lf(out[u]);
E[v] += (E[u] + w * p[u]) / lf(out[u]);
in[v]--;
if (in[v] == 0) q.push(v);
}
}
3.洛谷P1654 OSU!
题意：一个 \(01\) 串中每个长度为 \(X\) 的全 \(1\) 子串可贡献 \(X^3\) 的分数。
给出这个长度为 \(n\) 的串每个位置为 \(1\) 的概率，求期望分数。
解：仍然用 dp。
三次方不好处理。但是我们有 \((x+1)^3 - x^3 = 3x^2+3x + 1\) 与 \((x+1)^2-x^2=2x+1\)，这样，就可以递推算 \(X\) 与 \(X^2\) 的期望后再算 \(X^3\) 的期望。
这里设 \(E(X^2)_i\) 为全 \(1\) 的以 \(i\) 结尾串长的二次方的期望，其他同理。
状态转移方程：
\(E(X)_i = (E(X)_(i-1)+1)\times p_i\) （ \(p_i\) 的概率成功值加 \(1\)，失败则清零）
\(E(X^2)_i=(E(X^2)_{i-1}+2\times E(X)_{i-1}+1)\times p_i\)
对于每个 \(i\) ，产生长度 \(x\) 的概率为 \(p_x\)，对于每一个 \(x\) ，操作成功后的贡献为 \(3x^2+3x + 1\)， 第 \(i\) 次操作成功的概率为 \(p_i\)，故有
\(ans_i = ans_{i-1} + p_i\times\displaystyle{\sum_{x=0}^{i-1}p_x\times(3x^2+3x+1)}\)
运用期望的线性性质展开并利用 \(E(X^2)_{i-1} = \displaystyle{\sum_{x=0}^{i-1} p_x\times x^2}\) 与 \(E(X)_{i-1} = \displaystyle{\sum_{x=0}^{i-1} p_x\times x}\) 得
\(ans_i = ans_{i-1}+p_i\times(3\times E(X^2)_{i-1}+3\times E(X)_{i-1}+1)\)
代码：
for (int i = 1; i <= n; i++) {
E1[i] = (E1[i - 1] + 1) * p[i];
E2[i] = (E2[i - 1] + 2 * E1[i - 1] + 1) * p[i];
ans[i] = ans[i - 1] + (3 * E2[i - 1] + 3 * E1[i - 1] + 1) * p[i];
}
4.CF280C Game on Tree
题意：一棵 \(n\) 个节点的树，\(1\) 号节点为根。每次在剩余的节点中等概率地选择一个，并将其与其的子树删除。直至根节点被删。求操作次数期望。
解：每个点最多被选中一次（注意是选中而非删除），故只需找到每个点被选中的概率 \(p_u\)，根据伯努利分布可得该点贡献期望为 \(p_u\)。
设 \(u\) 的深度为 \(dep_u\) 由于 \(u\) 被删等价于其的祖先或自己这 \(dep_u\) 个节点中的一个被删，故要想 \(u\) 被选中，其必须在这 \(dep_u\) 个节点中最先被选中，故这个概率为 \(\dfrac{1}{dep_u}\)。
总期望 \(E(X) = \displaystyle{\sum_{i=1}^n\dfrac{1}{dep_i}}\)
dfs 求深度后直接计算即可。
代码：
dep[1] = 1;
void dfs(int u) {
ans += 1.0 / dep[u];
for (int v : g[u]) {
if (dep[v]) continue;
dep[v] = dep[u] + 1;
dfs(v);
}
}// dfs(1);