by Duck.
写点有用的。
概率
概率满足容斥原理相关的性质，例如 \(P(A\cup B)=P(A)+P(B)-P(A\cap B)\)。
一般将 \(A\cup B\) 简记为 \(A+B\)，将 \(A\cap B\) 简记为 \(AB\)。也就是 \(P(A+B)=P(A)+P(B)-P(AB)\)。
条件概率：记 \(P(A|B)\) 表示在 \(B\) 发生的条件下 \(A\) 发生的概率，则有
\[P(AB) = P(B)P(A | B)=P(A)P(B|A) \]由此可以导出贝叶斯公式：
\[P(A|B)=\dfrac{P(B\vert A)P(A)}{P(B)} \]全概率公式：记 \(A_i\) 为相互独立的事件，则有
\[P(B)=\sum_{i=1}^nP(A_iB)=\sum_{i=1}^nP(A_i)P(B|A_i) \]结合全概率公式和贝叶斯公式，可以得到在 \(A_i\) 相互独立下的贝叶斯公式：
\[P(A_i|B)=\dfrac{P(B|A_i)P(A_i)}{P(B)}=\dfrac{P(B|A_i)P(A_i)}{\sum_{i=1}^nP(A_i)P(B|A_i)} \]P8804 [蓝桥杯 2022 国 B] 故障
我们记 \(A_i\) 为每个原因发生，\(B\) 为给定的 \(k\) 个现象出现，其余不出现。答案就是 \(P(A_i|B)\)。
每个 \(A_i\) 相互独立，套入全概率贝叶斯公式即可。
时间复杂度 \(\mathcal{O}(nm)\)。
CF16E Fish
显然可以状压。设 \(f(S)\) 表示还存活的鱼的集合为 \(S\) 的概率，转移可以枚举 \(i\) 吃掉 \(j\)。
\[f(S)=\sum_{i\in S,j \not\in S}\dfrac{f(S \cup \{j\})\times a_{i,j}}{\binom{|S|+1}{2}} \]时间复杂度 \(\mathcal{O}(n^22^n)\)。
P4284 [SHOI2014] 概率充电器
注意到期望是假的，我们只需要算每个点通电的概率之和。
一个点通电有三种可能：
- 它自己通电。
- 父亲通电，且它与父亲的边通电。
- 某个儿子通电，且它与这个儿子的边通电。
后面两条限制很像换根 dp 能处理的问题。我们不妨往这个方向考虑一下。
第一次 DFS，求出只考虑 \(u\) 子树内的点，使得 \(u\) 通电的概率。记为 \(f(u)\)，则有
\[f(u)\leftarrow f(u)+P_{(u,v)}f(v)-f(u)f(v)P_{(u,v)} \]这个式子的理由是，\(A,B\) 同时发生的概率为 \(P(A)+P(B)-P(A)P(B)\)。
第二次 DFS，从 \(u\) 更新儿子 \(v\)，只需要算出 \(u\) 不经过 \(v\) 通电的概率，记为 \(P_a\)。按照刚才子树更新的方法，可以得到
\[f(u)=P_a+f(v)P_{(u,v)}-P_af(v)P_{(u,v)} \]注意，这个式子里的 \(f(v)\) 还没有被更新，表示的仍然是 \(v\) 子树里的答案。而 \(f(u)\) 是 \(u\) 完整的答案。
解上面的式子，可以得到
\[P_a=\dfrac{f(u)-f(v)P_{(u,v)}}{1-f(v)P_{(u,v)}} \]得到了 \(P_a\)，再拿去更新 \(f(v)\)。
\[f(v)\leftarrow f(v)+P_aP_{(u,v)}-f(v)P_aP_{(u,v)} \]时间复杂度 \(\mathcal{O}(n)\)。
期望
期望最重要的性质是其线性性。
\[E(X+Y)=E(X)+E(Y)$$绝大多数的期望相关题目都是由此展开的。 同时，对于独立的随机变量 $X,Y$ 有： $$E(XY)=E(X)E(Y)\]一些相关的做题技巧：
- 因为期望的结束状态是确定的，所以一般从后往前设状态。
- 一些高次项的期望，往往通过拆成若干低次项处理。
- 转移成环，考虑高斯消元。
SP1076 FAVDICE - Favorite Dice
可以证明，如果一个时间发生的概率为 \(p\)，则其第一次发生的期望时刻为 \(\dfrac{1}{p}\)。
设当前已经有了 \(x\) 个不同的面，则再扔出一个新的面的概率为 \(\dfrac{n-x}{n}\)，期望时刻为 \(\dfrac{n}{n-x}\)。
从而最终的答案为
\[\sum_{x=0}^{n-1}\dfrac{n}{n-x}=nH_n \]时间复杂度 \(\mathcal{O}(n)\)。
P8774 [蓝桥杯 2022 省 A] 爬树的甲壳虫
倒着设状态，令 \(f_i\) 表示从高度 \(i\) 爬到 \(n\) 的期望时间，则有 \(f_n=0\)，答案为 \(f_0\)。
\[f_i=p_{i+1}f_0+(1-p_{i+1})f_{i+1}+1 \]先把 \(f_0\) 写出来：
\[f_0=p_1f_0+(1-p_1)f_1+1 \]我们直接迭代下去，将 \(f_1=p_2f_0+(1-p_2)f_2+1\) 代入。
\[f_0=(p_1+(1-p_1)p_2)f_0+(1-p_1)(1-p_2)f_2+(1-p_1) \]其实这里已经可以看出端倪了。容易说明，不断代入下去可以得到：
\[f_0=\left(\sum_{i=1}^np_i\prod_{j<i}(1-p_j)\right)f_0+\left(\prod_{i=1}^n(1-p_i)\right)f_n+\sum_{i=1}^n\prod_{j<i}(1-p_j) \]中间一项直接 \(=0\)，这样就可以直接解方程得到 \(f_0\)。
时间复杂度 \(\mathcal{O}(n)\)。
P3239 [HNOI2015] 亚瑟王
先把期望拆到每个卡牌上，设第 \(i\) 张卡牌在 \(r\) 轮中出现的概率为 \(g_i\)，那么答案就是 \(\sum g_id_i\)。
慢慢来找点规律。先考虑 \(g_1\)，可以得到 \(g_1=1-(1-p_i)^r\)，就是用 \(1\) 减去一次不出现的概率。
考虑 \(g_2\)，如果某一轮 \(1\) 被用了，那么这一轮会终止，需要在剩下的 \(r-1\) 轮中出现一次 \(2\)，否则不变。
\[g_2=g_1(1-(1-p_2)^{r-1})+(1-g_1)(1-(1-p_2)^r) \]这件事情启发我们，每个数出现的概率与其前面发动了几张牌有关。
考虑 dp。设 \(f(i,j)\) 表示前 \(i\) 个卡牌经过 \(r\) 轮出现了 \(j\) 个的概率。这样可以得到求 \(g_i\) 的式子：
\[g_i=\sum_{j=0}^{r}f(i-1,j)\times (1-(1-p_i)^{r-j}) \]考虑 \(f\) 的转移，分成 \(i\) 是否出现。
- 如果 \(i\) 不出现，则有 \(f(i-1,j)\times (1-p_i)^{r-j} \to f(i,j)\)。
- 如果 \(i\) 出现，则有 \(f(i-1,j-1)\times (1-(1-p_i)^{r-j+1}) \to f(i,j)\)。
时间复杂度 \(\mathcal{O}(Tnr)\)。
标签：概率,期望,dfrac,sum,通电,复杂度 From： https://www.cnblogs.com/duckqwq/p/18132088