题解：AT_arc150_d [ARC150D] Removing Gacha

ty_mxzhn · 2025-02-07 09:29:02 · 题解

想了至少半个小时还是没有什么结果。纪念一下。

考虑如果一个点是坏点才计入贡献。这样子每次随机选一个点即可。

对于一个点 i 计算其被选中的期望次数。求和即为答案。

考虑 1\to i 具有 d 个点的情况。其相当于每个点独立，则如果选到了其他 n-d 个点则不会对这个点的答案造成影响。

我们可以看成在这 d 个点里等概率随机选择。而对于选到了非 i 的点而 1\to i 没有选完的情况，前面的点在选择过程中是否是好点也不对 i 的答案造成影响。

接下来考虑 d 个点选完所有点的期望次数。一开始有 1 的概率选到一个新点，接下来每次有 \dfrac{d-1}d 的概率选到新点。以此类推，第 i 个阶段选到下一个新点的期望次数是 \dfrac{d}{d-i+1}。则答案为 dH_d，其中 \displaystyle H_d=\sum_{i=1}^d \dfrac{1}{i} 调和级数。