SPOJ1026 Favorite Dice & 赠券收集问题

原题链接

假设有 $n$ 个数，每种每个数获取机率相同，而且每个数亦无限供应。若取 $t$ 个，能集齐这 $n$ 个数的概率是多少？

题解

我们考虑当你手上已有 $i$ 种不同的数，从集合中任选一个数得到新数的概率，为 $\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}$。

当然也可以用概率 dp 来推：

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

显然 $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}$。

于是整理一下就变成了 $f[0]=\sum _{i=1}^n\frac{n}{i}$。