蓝桥杯省赛 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 Collectors 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 和任意 ii p设 p q * i r其中 q p // ir 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 没有坏处。5.3 识别同类题的信号历年省赛期望题的包装五花八门但识别信号其实很固定。题面只要出现期望平均需要多少次随机抽取集齐这些词基本就是期望题出现保证必定最坏情况几次则是另一类最坏情况题和期望是两回事。拿到题目先过三个开关有放回还是无放回概率相等还是概率不同输出浮点还是取模。三个问题的答案组合基本就锁定了解法框架。这道《抽奖》就是最经典的有放回 等概率 取模组合推导出来的调和级数公式还能让你顺带验证一下数量级属于蓝桥杯里性价比很高的一类送分题。最后分享一个我自己的备赛习惯凡是遇到期望题永远先花五分钟写一版暴力模拟小数据对拍过了再上正解。这道题代码虽然短但背后的期望推导和取模处理几乎是每年必考的底层能力。把抽奖彻底吃透之后不管是集卡还是开盲盒的换皮题你都能一眼认出它的真身。