期望转换 笔记

$$\begin{array}{rl}E(X)=& \sum _{i=1}^{n}i\times P(X=i)\\ =& \sum _{i=1}^n\sum _{j=1}^{i}P(X=i)\\ =& \sum _{j=1}^n\sum _{i=j}^{n}P(X=i)\\ =& \sum _{i=1}^{n}P(X\ge i)\end{array}$$

于是就可以寻找更优的计数或者 DP 方式。