P(S)是获得S中的元素的概率
E(S)是获得S中的元素的期望步数
E(S)=1/P(S)
min-max容斥
记min(S)为出现S中任意一个元素
max(S)为出现S中全部元素
P(min(S))=∑i∈S P(i)
E(min(S))=1/P(min(S))
则E(min(S))为出现S中任意一个元素的期望步数
E(max(S))为出现S中全部元素的期望步数
E(max(U))=∑S∈U E(min(S))*(-1)^(|S|+1)
概率正着DP，期望倒着DP
若一个dp式子为f(i)=f(i)*p+x，则f(i)=x/(1-p)
原文：https://www.cnblogs.com/lher/p/9281210.html