题解 SP1026 【FAVDICE - Favorite Dice】

pufanyi · 2018-07-06 15:54:02 · 题解

典型的赠券收集问题。

我们考虑当你手上已有 i-1 种不同的数，从集合中任选一个数得到新数的概率，为 \frac{n-i+1}{n}，那期望即为 \frac{1}{p} = \frac{n}{n-i+1}。所以总期望为 \sum_{i = 1}^{n}\frac{n}{n-i+1} = \sum_{i=1}^{n}\frac{n}{i}。

upd：期望的和等于和的期望，所以上面的式子是可以简单相加的，比如你获得一个数期望要 A 步，获得另外一个数期望要 B 步，那么如果你想要同时获得这两个数显然期望是 A+B 步。

upd：关于为什么期望是概率分之一，大概就考虑如果你平均取 n 个球才会出现 1 个红球，也就是说期望是 n，那又可以说成是平均每 n 个球中出现 1 个红球，所以概率是 \frac{1}{n}。

当然也可以用期望 dp 来推：

我们设 f_i 表示取了 i 种数时还须取的数的期望。

考虑到如果手上已有n种数，那么就不用再取了，所以 f_n = 0，答案为 f_0，所以为逆推。

又由于选第 i 个数后再选一个数与已经选过的数不同的概率为 \frac{n-i}{n}，相同为 \frac{i}{n}。

于是可得 f_i = \frac{n-i}{n}f_{i+1}+\frac{i}{n}f_i + 1。

解得 f_i = f_{i+1} + \frac{n}{n-i}。

直接 dp 即可，当然整理一下就变成了 f_0 = \sum_{i=1}^{n}\frac{n}{i}，和上面推出来的相同。