概率与期望 ​

常见结论 ​

期望的线性性 ​

• $E(X + Y)=E(X)+E(Y)$
• $E(aX)=aE(X)$

应用 ​

将一个大的随机事件拆解成若干个随机事件的和，从而分别计算。

无限操作的小结论 ​

一个事件的成功概率是 $p$，不断进行该事件直到成功的期望操作次数是 $\frac{1}{p}$。

价值和计数转期望 ​

适用条件（同时满足） ​

• 对于所有操作序列求对应方案的价值和。
• 操作序列是个排列。

具体处理 ​

• 选择一个决策的概率等于其对应的方案数占总方案数的比值 （通常是当前剩下没确定的操作序列位置数的倒数） 。一些对价值和计算没有影响（只是产生了方案数的乘积）的操作可以忽略。
• 正着算需要记录方案数（概率）和价值和，反着算就只记录期望了。
• 最后得到的期望乘上操作序列的种数就是答案。

作用 ​

• 如果不用此trick，此类问题通常要记录价值和、方案数两个DP数组（此类问题通法）。应用此trick可以大大简化DP式，使优化更为显然和方便。
• 应当注意的是，这是特殊做法，一般情况下还是应该使用两个DP数组做计数。