一个关于推期望的小 trick
查看原帖
一个关于推期望的小 trick
91252
EndSaH楼主2020/6/7 16:51

只是单纯的介绍一种小 trick，由于太小就不发题解就扔到讨论区了。

设 f(S)f(S) 表示 SS 中至少出现了一位时的期望步数（也就是 E(min⁡(S))E(\min (S))），有转移式：

f(S)=1+∑T∩S=∅pTf(S)f(S) = 1 + \sum _{T \cap S = \varnothing} p _T f(S)

考虑操作一步，代价是 11；如果选到与 SS 无交集的 TT，则仍然要花费 f(S)f(S) 的代价；选到有交集的，则结束，无贡献。

于是得到

f(S)=1∑T∩S≠∅pTf(S) = \frac 1 {\sum _{T \cap S \not = \varnothing} p _T}
2020/6/7 16:51