近期题目小做（9.2）

每天做点题

UVa 10288

题目大意：有 $n$ 种不同的彩票，等概率买到一种。问若要集齐所有种彩票，需要购买的期望张数。

设集齐不同种的 $k$ 张时答案为 $f(k)$。有递推关系

$$f(k+1) = f(k) + \sum_{i=1}^{\infty} i {\lparen \frac{k}{n} \rparen}^{i-1} \cdot \lparen\frac{n-k}{n} \rparen$$

其中 $f(0)=0$。由幂级数求和有 $f(k+1) = f(k) + \frac{n}{n-k}$。因此答案是 $\sum_{i=1}^n \frac{n}{i}$。