998244353?998244353!
HDU$n$ 个物品,每次得到第 $i$ 个物品的概率为 $p_i$ ,而且有可能什么也得不到,问期望多少次能收集到全部 $n$ 个物品。分析$\text{min-max}$ 容斥。本题中显然有 $\displaystyle E(\min(T))=\frac{1}{\sum_{i\in T}p_i}$ 。于是直接枚举子集即可求出 $E(\max(S))$ 。代码// ============...
Luogu分析首先你要会 $\text{kth-max}$ 容斥:$\displaystyle\text{kth-max}(S)=\sum_{T\subseteq S}(-1)^{|T|-k}{|T|-1\choose k-1}\min(T)$ 。当然它也可以扩展到期望:$\displaystyle E\left(\text{kth-max}(S)\right)=\sum_{T\subset...
LuoguBZOJ分析我们把每个数看成一些二进制位的集合,每一位的值是加入的时间。那么我们要求的是全集的 $\max$ 值。根据 $\mathrm{min}$-$\mathrm{max}$ 容斥,有 $\large E(max(S))=\sum\limits_{T\subseteq S}(-1)^{|T|+1}E(min(T))$ 。考虑 $E(min(S))$ 怎么求。显然有 $\larg...