期望这东西学了一次忘了，再学一次过了两天又不会了。我是鱼。
故写此博客以便加深记忆及日后复习。
经典问题 1
某事件发生概率为 \(p\)，则该事件首次发生的期望次数为 \(\frac{1}{p}\)。
证明 link 懒得打 latex
经典问题 2
SP1026 FAVDICE - Favorite Dice
设已经有 \(k\) 个面出现过。则出现一个新面的概率为 \(\frac{n-k}{n}\)，由上题得出现期望次数为 \(\frac{n}{n-k}\)。
故答案为 \(\sum\limits_{i=0}^{n-1}\frac{n}{n-i}=nH_n\)。
CF1540B Tree Array
- 对于树上连通块问题先枚举树根。
考虑枚举每个点对 \((u,v)\) 对答案的贡献 (u<v)。
设 \(x=dep[u]-dep[LCA],y=dep[v]-dep[LCA]\)，再设 \(g_{x,y}\) 表示第一个点需要走 \(x\) 步，第二个点需要走 \(y\) 步，且第一个点先走到的概率。
则 \(g_{i,j}=(g_{i,j-1}+g_{i-1,j})/2\) 。预处理即可。
ARC150D Removing Gacha
...
未完待续。