51nodLOJ分析为了方便，下面简记 $f_S$ 为 $f_{a_1},f_{a_2},\cdots,f_{a_k}$，其中 $S=\{a_1,a_2,\cdots,a_k\}$。考虑一个经典容斥从小到大枚举倍数算贡献即可。实现得好的话时间复杂度是 $\mathcal{O}(n\log n)$ 的。代码// ==================================== // ...
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...