假设有 \(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}\)。