# SPOJ1026 Favorite Dice & 赠券收集问题

Author: Fanyi Pu

Published: 2018-12-22

Canonical: <https://pufanyi.com/blog/oi-icpc/spoj/sp1026>

SPOJ1026 Favorite Dice & 赠券收集问题题解。

[原题链接](https://www.spoj.com/problems/FAVDICE/)

假设有 $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}$。