蓝桥杯Python抽奖题：优惠券收集问题的期望与取模实现-育师

蓝桥杯省赛 Python 组每年都会出那么一两道"把经典模型包装成故事"的题目，2025 年第十六届省赛这道《抽奖》就是典型。我拿到题面扫了一眼，第一反应是用 random 库疯狂模拟，好在这个念头只持续了两秒钟——等看到数据范围就彻底清醒了。这篇就把题面还原、期望推导、Python 实现和同类变体完整拆一遍。想读透这道题，你需要掌握三件事：期望的线性性质、几何分布、还有分数取模。正在备赛的 Python 选手，或者对算法题里的期望计算还不太熟练的读者，这篇文章应该能把你的思路彻底理顺。

1. 题面还原与这道题真正的考点

1.1 题意简化与输入输出约定

原题套了一层商城抽奖活动的故事背景，但剥掉外衣，核心逻辑是这样一个经典问题：一共有 n 种奖品，每次抽奖等概率抽到其中任意一种，而且奖品池不会因为被抽走而减少，同一种奖品可以被重复抽到。目标是把 n 种奖品全部集齐，问抽奖次数的期望值是多少。

这里有个容易被忽略的细节：输出形式会直接决定写代码的姿势。早期题目可能只会让你输出一个保留两位小数的浮点数，但近几年省赛更常见的要求是输出对 1e9 + 7 取模的整数结果。这两种写法差别非常大——浮点版可以走实数累加，取模版则必须在分数层面做逆元运算。尤其是当 n 的量级来到 10^6 甚至 10^7 时，理论上只能选择整数模运算的路线，浮点数那套方案根本站不住脚。

1.2 为什么这不是一道模拟题

新手最容易掉进去的坑就是："抽奖嘛，模拟一下不就行了。"

暴力模拟的思路大致长这样：开一个 visited 数组记录哪些种类已经出现过，循环生成随机数，直到所有种类都出现过，统计总次数；重复跑一百万次，求平均。这种做法有两个层面上的硬伤。

第一是精度问题。期望本身是随机变量的均值，模拟误差的消减速度只跟试验次数的平方根成正比。想得到稳定到小数点后两位的结果，试验次数往往要拉到亿级，赛场上根本等不起，而且每次模拟的随机种子不同，答案还会上下抖动。

第二是确定性问题。当题目要求输出取模整数时，模拟出来的浮点数天然无法转化成精确的取模结果。哪怕你算出 5.999999，你也不知道正确答案到底是 6 还是某个更大数在模域下的映射。

所以这道题题名虽然朴素，考点其实非常集中：你有没有掌握"期望的线性性质""几何分布"和"分数取模"这三板斧。代码可以短到十几行，但背后的数学推导一步都不能省。

2. 从"集齐 n 种"的直觉到调和级数公式

2.1 把大目标拆成 n 个独立的等待阶段

现在我们把"集齐 n 种"这个大目标拆开。假设当前已经集齐了 k 种奖品，接下来要做的事情非常明确：一直抽，直到抽到一个还没出现过的种类。

在这个阶段里，每次抽奖抽到新奖品的概率是：

p_k = (n - k) / n

这里的 n - k 就是还没集齐的奖品种类数。注意，重复独立试验直到首次成功，所需要尝试的次数服从的是几何分布，而这个分布的期望恰好等于成功概率的倒数，也就是 1 / p_k。

这个概念值得用最俗的方式解释一遍：盲盒里某个隐藏款出现的概率是 1/60，那么你平均要拆 60 个盲盒才能见到它一次。成功率越低，等待次数越长，而且这个"平均等待次数"和概率是严格的倒数关系，不偏不倚。很多同学记不住这个结论，到考场上一紧张就开始瞎猜，其实你在草稿纸上画个树形图就能立刻想起来。

2.2 累加得到 E = n × H(n)

第 k 阶段（当前已经集齐 k 种）的期望等待次数是 n / (n - k)。让阶段编号从 0 一直走到 n - 1，把所有阶段的期望直接累加：

E = n/n + n/(n-1) + ... + n/1

整理一下就是：

E = n × (1 + 1/2 + 1/3 + ... + 1/n) = n × H(n)

这个式子就是数学里大名鼎鼎的优惠券收集问题，英文常叫 Coupon Collector's Problem。调和级数 H(n) 的增长速度大约是 ln n + γ，其中 γ 是欧拉常数。所以集齐 n 种奖品的期望抽奖次数大约在 n ln n 这个量级，而不是很多人直觉中的 n，也不是 n²。

拿这个估算值去验证题目给的样例数据，往往几秒就能判断自己的公式对不对。这种"先估数量级再看题面"的习惯，在赛场上比什么都管用。

2.3 期望的线性性质说明

第一次接触这个推导的人，几乎都会在一个地方卡住：这几个阶段之间并不独立啊？

确实，第一阶段抽到新品的概率一定是 1，但到第二阶段，你可能第一次就中，也可能要抽十次才中。后面阶段的成败和前面阶段的结果显然存在某种关联。但这里有一个极其重要的结论：期望的线性性质并不要求随机变量相互独立。只要这些随机变量本身存在期望值，就可以直接相加，无论它们之间有多少复杂的依赖关系。

换句话说，E(X1 + X2 + ... + Xn) = E(X1) + E(X2) + ... + E(Xn) 永远成立。这是整个推导能成立的根，也是概率论里最被低估的一个性质。赛前把这个点想透，你就不会在"能不能相加"这个问题上浪费任何犹豫的时间。

3. Python 实现的三种写法与选型思考

3.1 浮点输出版：适合小数据和浮点要求

如果题目明确允许输出浮点数，最直接的实现就是把公式敲进去：

n = int(input()) ans = 0.0 for i in range(1, n + 1): ans += 1.0 / i ans *= n print(f"{ans:.2f}")

这个写法复杂度 O(n)，优点是代码和公式一一对应，连注释都不用写。缺点是当 n 变大时，循环内的浮点加法会不断累积舍入误差。调和级数的求和顺序还会让误差进一步放大——你先把小的 1/n 加到大的累计值上，精度损失会比反过来更严重。实测中 n 到 10^6 时，输出保留两位小数还算安全，想保留六位就得看运气。

3.2 取模版：费马小定理求逆元

题目要求结果对 MOD = 1e9 + 7 取模时，加法里的每一个分数 a/b 都要翻译成 a 乘以 b 的模逆元。由于 1e9 + 7 是质数，根据费马小定理，b 的模逆元就是 pow(b, MOD - 2, MOD)。

所以最朴素的取模写法是：

MOD = 10 ** 9 + 7 n = int(input()) total = 0 for i in range(1, n + 1): inv = pow(i, MOD - 2, MOD) total = (total + inv) % MOD print(total * n % MOD)

这个版本空间 O(1)，只有时间上是 O(n log MOD)。单次 pow 里 log MOD 大约在 30 次乘法左右，n 到 10^6 就是 3000 万次乘法。听起来很吓人，但 pow 是 CPython 的内置函数，整个快速幂循环运行在 C 语言层，实际速度比你想的快不少。n 在 10^6 以内时，这个朴素的写法往往能直接过。

3.3 线性逆元版与真实性能讨论

如果继续优化，可以用线性递推一次求出 1 到 n 的所有逆元，把总复杂度降到 O(n)。

递推公式长这样：

inv[i] = (MOD - MOD // i * inv[MOD % i]) % MOD

这个公式不是凭空变出来的。对质数 MOD = p 和任意 i（i < p），设 p = q * i + r，其中 q = p // i，r = p % i。两边同时对 p 取模就得到 q * i ≡ -r (mod p)。两边同乘以 inv[i] * inv[r]，整理后就得到上面的递推式。完整的 Python 实现如下：

MOD = 10 ** 9 + 7 def solve(n: int): if n == 1: print(1) return inv = [0] * (n + 1) inv[1] = 1 for i in range(2, n + 1): inv[i] = (MOD - MOD // i * inv[MOD % i] % MOD) % MOD total = 0 for i in range(1, n + 1): total = (total + inv[i]) % MOD print(total * n % MOD) if __name__ == "__main__": n = int(input()) solve(n)

但这里有个反直觉的现象：虽然线性逆元理论复杂度更优，在 CPython 环境下它并不一定比 pow 版快。因为线性逆元的核心循环是纯 Python 代码，每一轮都要做整除、乘法、取模三个操作，解释器开销非常大；而 pow 版的快速幂全在 C 层跑，常数极小。实际比赛里如果是 PyPy 环境，线性逆元有明显优势；如果是 CPython 且 n 只有 10^6，我会更倾向于直接 pow，省心又不容易写错。

3.4 三种写法对照

写法	时间复杂度	空间复杂度	适用场景	主要风险
浮点求和	O(n)	O(1)	只输出小数位	n 大时精度危险
pow 逐个求逆元	O(n log MOD)	O(1)	n 在 10^6 上下，CPython 环境	理论复杂度偏高
线性递推逆元	O(n)	O(n)	PyPy 环境，n 到 10^7 以内	数组下标易写错，内存占用大

内存是第三个容易被忽略的点：线性逆元要开长度为 n + 1 的 Python 列表，当 n 到 10^7，每个整数对象加上列表引用的开销，内存可能冲到几百 MB。如果此时再叠加多个大规模样例，内存超限的风险非常大。所以不要一上来就写线性逆元，先确认数据范围和评测环境再做决定。

4. 实测验证与容易踩的坑

4.1 用手算小数据验证公式

推导出来的公式对不对，第一步永远是用小数据手算验证。

n = 1 时，E = 1 × (1) = 1，只抽一次必然集齐，这显然对。

n = 2 时，E = 2 × (1 + 1/2) = 3。意思是一共有两种奖品，平均要抽 3 次才能集齐。第一次必中新种类，第二阶段只有 1/2 概率抽到剩下的那一种，所以第二阶段平均需要 2 次，加起来正好 3 次，和直觉完全吻合。

n = 3 时，E = 3 × (1 + 1/2 + 1/3) = 5.5。你可以用计算器算一下，五到六次的量级显然是合理的。这三个手算结果可以直接当成单测用例，写完代码立刻跑一遍，能过滤掉绝大多数低级错误。

4.2 浮点精度与取模常见错误

我总结了一下，这道题最容易出事的点有三个。

第一，先算浮点再取模。期望 n × H(n) 在浮点下如果算到 1e-9 级别的误差，乘上 n 之后误差可能被放大到不可接受。当 n 接近 10^6，浮点误差搞出几个整数的偏差是常事，结果错得莫名其妙。正确做法是从头到尾都在整数模运算空间里完成，中间不要出现任何浮点类型。

第二，i 等于 MOD 的倍数时无法求逆元。当 i 恰好是 1e9 + 7 的倍数时，它在模域下等于 0，根本不存在逆元。题目通常保证 n < MOD，但如果你在做本地调试时往大了测，代码里会出现逆元为 0 或者 RuntimeError 之类的诡异表现。这属于测试数据边界没想清楚的坑。

第三，线性逆元数组下标错位。inv[0] 在数学上没有定义，递推必须从 inv[1] = 1 开始。有次我图省事把初值写到了 inv[0]，结果后面每个逆元都是错的，调试了半小时才发现。

4.3 用暴力模拟对拍

任何期望公式，我写完都会配一个暴力模拟脚本做对拍。下面这段代码属于纯验证用途，不追求性能：

import random random.seed(2025) def simulate(n: int, trials: int = 200000) -> float: total = 0 for _ in range(trials): seen = set() cnt = 0 while len(seen) < n: cnt += 1 seen.add(random.randrange(n)) total += cnt return total / trials for n in range(1, 9): approx = simulate(n) exact = n * sum(1.0 / i for i in range(1, n + 1)) print(n, round(approx, 4), round(exact, 4))

把小数据 n = 1 到 8 跑一遍，模拟结果和公式误差应该在 1e-2 以内。对拍通过后，再把取模解交上去，心里就有底了。这套"暴力对拍 + 手算验证"的组合拳，适合所有期望类题目，不限于这一道。

5. 从"抽奖"出发：同类期望题的变体与识别

5.1 不放回抽取的期望模型

上面讨论的都是有放回模型——奖品池里的种类不会减少。如果题目改成不放回，情况就完全不同了。

看一个常见的变体：一共有 n 张奖券，其中 m 张是中奖券，每次随机抽一张、不放回，问你抽到所有 m 张中奖券平均需要抽几张。

这里的推导结论是 E = m × (n + 1) / (m + 1)。我简单验证两个极端：m = 1 时，期望是 (n + 1) / 2，也就是在均匀随机排列的 n 张牌中，唯一一张目标牌的平均位置，这符合直觉；m = n 时全部都是中奖券，必须抽完 n 张，公式给出 n × (n + 1) / (n + 1) = n，正确。你对比一下就能发现，有放回是 n ln n 量级，不放回是线性量级，两者差距极大。做题时第一件事就是确认"到底放不放回"。

5.2 概率不等的加权模型与状态压缩

再进一步，如果每种奖品出现的概率并不相等，而是各自有不同的 p_i，问题就复杂了。

此时不能再用单阶段概率比例的简单拆法，因为你必须知道"当前已经集齐了哪几种"才能算下一步抽中新种类的概率。n 比较小时，常规解法是状态压缩 DP：用一个 n 位的二进制数表示当前集齐状态，按期望递推列出转移方程；n 变大后，要么靠容斥、生成函数等更高阶的工具，要么只能做近似。这种题目蓝桥杯省赛出得不多，但在后面的压轴题里偶尔会出现，提前练一练状态压缩 DP 没有坏处。