拆贡献与期望本质：CF1392H

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133355060

题目问牌数，但其实题面有另一个很明显的东西叫轮数

而如果我们每一轮单独考虑，其对应的期望牌数是确定的。

我们肯定会大胆考虑直接用期望牌数乘期望轮数，但为什么对？

每轮牌数乘上前 $i-1$ 轮未结束的的概率，后面的概率是第 $i$ 轮恰好结束的前缀和，而我们再求个和就是期望轮数。

考虑每一轮的期望牌数。首先肯定会抽到一种鬼牌，所以必然+1。然后考虑经典操作拆贡献，每张牌要被拿必须满足之前没鬼牌，也就是 $\frac 1{m+1}$ ，同时也是其期望。 $n$ 张根据期望可加性为 $\frac n {m+1}$ 张，所以一轮是 $\frac n{m+1}+1$ 的期望牌数。

考虑期望轮数。我们算一下剩 $i$ 张牌被选的期望失败轮数 $f(i)$ 再加上最后一轮。

既然失败，说明前面都是先选鬼牌。它在一轮内被选的概率为 $\frac i {m+i}$ ，则期望就是 $\frac {m+i}i$ 。但我们计算的是失败轮数，所以要减1，也就是 $f(i)=\frac m i$ 。

我们对 $f$ 进行求和是 $mH_n$ ，其中 $H$ 为调和级数。