题解：AT_arc150_d [ARC150D] Removing Gacha

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

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

对于一个点 $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}$ 调和级数。

$1\to i$ 的 $d$ 个点选完所有点的期望次数是 $dH_d$，选到 $i$ 的期望次数是 $H_d$。则本题答案为 $\displaystyle \sum_{i=1}^n H_{d_i}$。