概率期望
GYM104114C. COVID
这题考察的是一个 条件概率 。这里记下最基本的式子：
\[P(A|B)=\frac{P(AB)}{P(B)} \]然后再回来考虑这一道题，我们要计算的包含两个部分：
- 所有检测结果都阳性的概率。
- 所有检测结果都阳性，并且 \(i\) 这个人阳了的概率。
先考虑前者，其方案数就是：总方案数 \(-\) 有一次阴性 \(+\) 有两次阴性 \(...\) 并且由于 \(m\leq 15\) ，因此直接枚举哪些阴性容斥计算即可。对于后者计算也是类似。
期望的线性性
\[E(X+Y)=E(X)+E(Y) \]关于这个等式，有一个很重要的性质：随机变量不独立的情况下，等式也成立。
很多题目都是要依靠这个等式，将所求的答案拆开或者合起来考虑。
P4284 [SHOI2014] 概率充电器
比较简单的一个期望 \(\text{dp}\) ，考虑计算出每个点被激活的概率。
记只考虑 \(x\) 子树内的点，将 \(x\) 激活的概率为 \(f_x\) 。转移如下：
\[f_x=p_x+(1-p_x)\left (1-\prod_{y\in son_x}(1-f_y)(1-e_y)\right ) \]对于每个点求答案的话换根处理一下就行。
P6835 [Cnoi2020]线形生物
利用 期望的线性性 ，将答案拆到每一条边上，计算每一条边被经过的期望次数。
记 \(f_i\) 表示 \((i,i+1)\) 这条边被经过的期望次数，\(s\) 为序列 \(f\) 的前缀和。由于除了链以外，只包含返祖边，因此有如下转移：
\[f_{i}=\frac{1}{du_i} \left( \sum_{(j,i)}s_i-s_{j-1}\right)+1 \]将其化简成仅包含前缀和的形式（其中 \(c\) 表示 \(i\) 点连出去的返祖边的条数）：
\[s_i=(s_{i-1}+1)\cdot du_i-\sum_{(i,j)}s_{j-1} \]然后就可以递推前缀和序列了。
这题要分析出图的结构可以划分层次，再利用期望的线性性拆贡献处理。
某个题目
给定 \(n\) ，定义一张图的权值为其哈密顿回路条数，求一张随机竞赛图的权值期望。\(n \leq 10^9\) 。
单独考虑每一条哈密顿回路，计算其会存在于多少个竞赛图中。方法很简单，钦定一条回路，其余边随意。\(n\leq 10^9\) 的话分段打表计算阶乘即可。
\(\text{CTT Day1T3}\)
有一张无向图，从 \(1\) 开始随机游走，到 \(n\) 停止。游走过程中会得到一个分数，初始为 \(0\) 。若经过一类边，分数清零；经过二类边，分数加 \(1\) 。问游走结束时分数的期望和方差。
一个关于 方差 的结论：
\[E(s^2(x))=E(x^2)-\left( E(x)\right)^2 \]因此其实求解方差的期望，与直接求解期望难度差别不大。
对于这题，简单的来讲可以将当前状态维护成一个矩阵，包含 \(x^2,x,1\) ，经过每条边相当于乘上一个转移矩阵。实际操作中将矩阵拆开，维护一些变量之间的方程然后高斯消元即可。
CF963E. Circles of Waiting
一道科技高斯消元的模板，可以使用带状矩阵，也可以用主元法。
带状矩阵
针对每一行非零元素在特定位置的矩阵，时间复杂度为 \(O(nd^2)\) ，\(n\) 为未知数个数，\(d\) 为带宽。
主元法
利用一些元素做主元，需要满足的是这些元素能够表示出其余所有的元素。再用那些没有被用过的方程将主元的值即可。时间复杂度 \(O(m^3)\) ，\(m\) 为主元个数。
\(\text{Min-Max}\) 容斥
\[\min(S)=\sum_{T\neq \phi,T \subseteq S}\max(T)(-1)^{|T|+1} \]P5643 [PKUWC2018]随机游走
这题之前直接分层图跑树形背包写过了，这里记录一下 \(\text{Min-Max}\) 容斥的做法。
设计状态 \(f_{x,S}\) 表示当前站在 \(x\) 点上，要遍历完 \(S\) 集合中的所有点的期望步数。其含义可以理解为遍历到集合中最后一个点的期望步数。将这个条件利用 \(\text{Min-Max}\) 容斥进行转化，转化为求遍历到集合中第一个点的期望步数，然后其余的做法就一模一样了。这样优化的好处是枚举集合 \(S\) 的时候，所有状态不与其它 \(S\) 有关。
**出现最大/最小之类的问题，并且其中一个的答案更加方便求解时，可以考虑 \(\text{Min-Max}\) 容斥。 **
特别注意的是，这种树上高消的办法，在取模意义下可能会出现 \(dp_x\) 的系数为 \(0\) 的情况，这样的话这种办法就不适用。
P6046 纯粹容器
整数概率公式
针对一个取值总为整数的随机变量：
\[E(X)=\sum_{i=1}^{\infty}P(X\geq i) \]其含义为：随机变量 \(X\) 的期望等于其大于每个正整数 \(i\) 的概率总和。证明的话感性理解一下：\(P(i)\) 刚好被加了 \(i\) 次。
这个式子在一类 存活到某时间 或者 最小值 的期望的时候有独特的作用。
再来考虑这一题。记每个数 \(i\) 左右第一个大于其的数分别为 \(L,R\) ，\([L,i]\) 和 \([i,R]\) 以及 \([1,L],[R,n]\) 的空隙个数分别为 \(A,B,C\) 。考虑计算出 \(i\) 存活到第 \(k\) 轮的概率，也就是 \(i\) 在第 \(k\) 轮及之后被删除的概率总和（套用上述公式）。方案数的计算非常容易：
\[f(i,k)=\sum_{a=1}^{A-1}\sum_{b=1}^{B-1}\sum_{c=1}^C[a+b+c=k]\cdot{A \choose a}{B \choose b}{C \choose c} \]对于本题暴力计算即可，也可以通过 组合意义 优化到 \(O(n)\) 。
这一类删除东西的期望题，可以考虑套用整数概率公式。
P4548 [CTSC2006]歌唱王国
只听懂了较为简单的做法，概率生成函数 的做法待补。
这题理解为不断在 \(\text{kmp}\) 匹配的过程，如果下一位相同，则直接走，否则跳 \(\text{fail}\) 跳回去，这样就与上面 线性生物 这题做法一样了。
概率生成函数一些浅显的知识
称 \(F(x)=\sum_\limits{i=0}^{\infty}P(X=i)x^i\) 为概率生成函数。这个东西常用来解决一类无限随机过程的问题，但是注意其是否收敛。这里记录下其两条性质：
- \(F(1)=1\) ，概率总和为 \(1\) 。
- \(E(X)=F'(x)\) 的系数总和，也可以多导几次化成下降幂的形式。
CF605E. Intergalaxy Trips
先考虑朴素的转移方程：
\[f_i=\sum_{S}P(S)\min_{(i,j)\in S}(f_j+1) \]\(S\) 为枚举存在的边的集合。考虑这个转移式子，初值 \(f_n=0\) ，并且 \(f\) 总是由小的转移到大的。因此转移顺序按照 \(f\) 递增的顺序来，用 \(\text{dijkstra}\) 维护转移。计算由当前点转移过去的总贡献。
若转移对象大小存在单调性，且转移系数非负，可以考虑使用 \(\text{dijkstra}\) 维护。
P5155 [USACO18DEC]Balance Beam P
转移式子是非常显然的：
\[f_i=\max\left(v_i,\frac{f_{i-1}+f_{i-2}}{2} \right) \]直接来考虑，是没办法做的。但是注意到一点，将 \((i,f_i)\) 视为平面上的点对，如果 \(f_i\) 取到的是右边，那么该点与左右两边的点共线。据此，我们来探究是否会存在选择左边的点是一个 “凹” 型。答案是不会的，画下图可以发现这样显然不右。然后这题就被转化成了对于 \(v\) 求解上凸壳，作为选择左边的点。
标签：概率,期望,记录,text,讲课,转移,这题,zxy,sum From： https://www.cnblogs.com/oscaryangzj/p/17146015.html