P4550 收集邮票

难度	算法s	日期	题目链接
提高+/省选−	数学期望、递推、倒推	2025-07-21	https://luogu.com.cn/problem/P4550

这道题，巧妙之处在于如何推出期望的递推式。太妙了，回味无穷。慢慢消化吧。

题意简述

总共有 $n$ 种邮票，我们希望每种邮票至少买到一张。每次购买时，买到任意一种邮票是等可能的。而且我们第 $k$ 次购买时，需要花费 $k$ 元钱。

求：花费的期望。

Part I

（$99\%$ 是老师讲解才懂的）

如果直接求 “要买到 $k$ 种邮票，期望的购买次数”，很难推。不妨先求出：已经买到 $k$ 种邮票，期望还要买几次，我们记为 $f_k$。体会这里的妙处，前者从前往后考虑（正推），后者从后往前考虑（倒推）。正难则反。 为什么倒推能成呢？因为边界条件 $f_n=0$，我们是知道的。

在已经买到 $k$ 种邮票的情况下，我们再买一张，有两种可能：

• 买到的邮票已经在这 $k$ 种中，概率为 $k/n$；这种情况下，状态不会转移，所以期望还要买的次数为 $(k/n)\times f_k$。
• 买到了新的邮票，概率为 $(n-k)/n$；这种情况下，状态发生转移，期望还要买的次数为 $[(n-k)/n]\times f_{k+1}$。

于是得出了递推式：

$$f_k=(\frac{k}{n}\times f_k+\frac{n-k}{n}\times f_{k+1})+1.$$

（末尾的 $+1$ 是当前消耗一个次数，前面那串是之后消耗的次数。）当然这不是真正的递推式。我们分离出 $f_k$：

$$(1-\frac{k}{n})f_k=\frac{n-k}{n}f_{k+1}+1\\ \Rightarrow f_k=f_{k+1}+\frac{n}{n-k}.$$

注意我们假设在求 $f_k$ 时已求出 $f_{k+1}$。

是不是感觉很神奇？我们在列式子的时候，明明没有求出 $f_k$，但是式子右边却出现了 $f_k$ 相当于我们也假设了已知 $f_k$（？）。但是看了看题解区似乎没人觉得这里有什么奇怪的。总之那个式子恒成立，能用，就用来递推吧。我称之为 “递归推式法”。

聪明的你可能会想，那我们移项——

$$f_{k+1}=f_k-\frac{n}{n-k},$$

如何呢？可不可以正推？很可惜不行。这个式子理论上是成立的，但是我们不知道边界条件 $f_0$。事实上我们想求的就是 $f_0$ 啊。

Part II

注意：期望花费 = $(1+f_0)\times f_0\div2$ 不成立。

现在考虑怎么求花费的期望。类似地，我们定义 $g_k$ 表示：已经买到 $k$ 种邮票，期望还要花的钱。同样考虑倒推：

$$g_k=\frac{k}{n}(g_k+f_k+1)+\frac{n-k}{n}(g_{k+1}+f_{k+1}+1).$$

这里为什么会有 $f$ 项让我困惑了很久。这样理解：

• 我们从后往前递推，每次我们记录的是 “从当前” 买到达到目标要花的钱。但是 “当前” 再买一次，要花多少钱和 “当前是第几次购买” 相关，我们不知道 “当前” 确切地要花多少。所以我们不妨设 “当前” 要花 $1$ 元。

• 然后我们在递推式中 “弥补”：每次向前推一步，相当于后面的购买每次花费都 $+1$。所以就有 $+f_k$ 和 $+f_{k+1}$ 的说法了。

把上面的式子分理出 $g_k$，就得到了真正的递推式：

$$g_k=\frac{k}{n-k}(f_k+1)+g_{k+1}+f_{k+1}+1.$$

同样地，边界条件是 $g_n=0$，$g_0$ 就是题目要求的终极答案。

Part Final

所以我们就用一个 for() 从 k=n 递推到 k=0。因为 g[] 的计算依赖于 f[]，所以每次我们先推出 f[k]，再推 g[k]。