今年蓝桥杯省赛A组有一道题让很多人在考场上卡了很久P12140题目名叫“抽奖”。赛后群里讨论热度不低因为这道题表面看是概率期望实际还埋了组合计数、浮点精度和取模运算的坑。如果你打算打蓝桥杯或者正在备战接下来的算法竞赛这篇文章我想把这类抽奖题的完整思考过程拆给你看——从怎么读题用什么数学模型到最后一行的代码怎么写全部过一遍。考虑到很多同学拿到的题目描述版本不太一样我不逐字复述题面只讲这类“抽奖”题背后最核心的数学结构和代码实现这样不管题目具体长什么样思路都能直接迁移。1. 先分清“抽奖”到底在考什么1.1 从标题能判断出的考察方向“抽奖”这个题名在算法竞赛里是一个很典型的信号它几乎不会真的让你去模拟抽奖过程而是借抽奖的外壳考察两件事第一是“期望”的计算能力第二是“最优策略”的推导能力。蓝桥杯省A组的题目很少会只考一个孤立知识点抽奖题尤其喜欢把概率期望、组合数学、动态规划甚至数论取模揉在一起。如果你看到题目里出现“随机抽取”“概率”“期望”“至少多少次”“中奖”这些词基本可以确定这是一道概率期望题。而蓝桥杯的概率期望题有一个共同特点它不会直接给你一个现成的公式背而是需要你自己从过程描述里把数学模型抽出来。1.2 省A组“抽奖”类题目的三种常见模型我梳理了近几年的蓝桥杯及相关竞赛题目发现抽奖题翻来覆去就三个模型第一种是“集齐型”题目说有n种奖品每次抽奖等概率拿到其中一种问集齐所有种类的期望次数。这种模型在数学上叫优惠券收集者问题答案是n乘上调和级数。如果题目再复杂一点会给每种奖品不同的中奖概率。第二种是“决策型”每次抽奖后可以选择继续抽还是停止目标是最大化收益或最小化期望花费。这种题通常要用动态规划把当前状态下的最优期望写进状态转移方程。第三种是“条件概率型”比如抽奖过程中有“中大奖后重新开始”之类的状态转移或者要计算某个特定事件发生的概率。这种题的本质是马尔可夫过程但竞赛里不会考那么深一般用线性方程组或递推就能解。P12140这道题到底属于哪一种受限于我拿到的信息量我不能百分百断言。但从“抽奖”这个命名习惯和题目编号对应的难度来看它大概率落在第一种或第二种而且最有可能的是表面是第一种实际需要运用到第二种的思维来优化。1.3 拿到题目先别急着写代码三读数据范围很多同学一看到题目就打开编辑器敲代码这是大忌。省赛的坑往往不在算法难而在数据范围没看仔细。抽奖题尤其如此。第一遍读题搞清楚n是多少。如果n很小比如n20那大概率可以用状态压缩DP如果n是10的5次方甚至10的6次方那就必须找到O(n)或O(n log n)的做法容斥枚举子集肯定超时。第二遍读题看输出要求。是输出浮点数保留几位小数还是输出分数取模如果是分数取模就意味着你必须用模逆元浮点数完全派不上用场。这个细节直接决定代码里用double还是long long。第三遍读题看概率是否相等。概率相等和概率不相等是两个完全不同的难度等级前者的期望公式非常简洁后者则要面对容斥或积分近似处理方式完全不同。我在实际指导学生时经常说读完题先花30秒把这三个信息写在草稿纸上比直接上手写代码省下的调试时间多得多。2. 核心数学模型抽奖题到底在算什么2.1 模型A集齐型抽奖的期望推导先看最简单也最常见的等概率集齐模型。假设有n种奖品每次抽奖独立且等概率得到其中任意一种问集齐所有n种奖品的期望抽取次数。这个推导很多同学背过公式但不理解来源所以一旦题目变形就懵。记E_i表示现在已经集齐了i种奖品还差n-i种没集齐时距离集齐还需要抽取的期望次数。从状态i出发下一次抽奖有两种可能抽到新的奖品概率是(n-i)/n抽到已经有的奖品概率是i/n。于是有E_i 1 (i/n) * E_i ((n-i)/n) * E_{i1}移项整理得到E_i n/(n-i) E_{i1}从E_{n-1}一直往前推E_0 n * (1 1/2 1/3 ... 1/n)。这个推导为什么要放出来因为蓝桥杯的题目不会只考你背公式它可能反过来问你“如果已经有了k种奖品期望还要抽多少次”或者“如果某种奖品出现的概率是其他奖品的两倍公式会变成什么”。只要你掌握了从状态转移推期望的方法这些变形都能当场推出来不需要靠记忆。2.2 模型B概率不相同的加权收集问题如果每种奖品的中奖概率分别是p1, p2, ..., pn且概率之和不等于1而是存在一个“没抽中任何奖品”的情况那问题就更贴近真实的抽奖活动。期望集齐时间的计算需要用到容斥原理E Σ_{非空子集S} (-1)^(|S|1) / (Σ_{i∈S} p_i)这个公式的理解方式是这样的如果只关注子集S中的奖品那么“抽中S中任意一种奖品”这个事件的发生概率为Σ_{i∈S} p_i其首次发生的期望时间是1除以这个概率。但多个子集之间会重叠所以要用容斥系数修正。实际做题时如果n较大这个容斥公式不能暴力枚举所有子集否则复杂度是O(2^n)。但有一种特殊情况非常好处理当所有p_i都相等且总和小于等于1时问题退化成优惠券收集公式就能化简。这也是为什么读题时一定要确认概率是否相等的根本原因。如果你拿到的是这种加权模型代码实现可以用动态规划从后向前推dp[i]表示当前已拥有的奖品集合为i时的期望剩余次数转移时枚举下一次抽到哪类奖品按概率加权平均。但注意n超过20时状态数爆炸必须另寻公式。2.3 模型C带决策的抽奖把期望写进状态还有一种更考验综合能力的变形每次抽奖需要支付一定费用抽到的奖品有对应的价值你可以随时选择停止。问最优策略下的期望净收益或最小期望花费。这种题和前面的区别在于它不只是“被动地等概率发生”而是“主动做决策”。通常的解法是定义f[S]为当前已拥有的奖品集合为S时继续参与游戏能带来的最大期望收益。转移时比较“立即停止”和“再抽一次”的期望收益取最大值。这里有一个非常容易踩的坑状态转移里可能形成环。比如抽奖结果包含“什么都没抽到状态不变”那么f[S]的表达式里会出现f[S]自身必须通过移项消去。很多同学在这里直接写递归导致无限循环或者忘记处理自环答案就算不对。所以如果你在考场上发现推出来的转移方程里等式两边都出现同一个状态不要慌这说明需要把状态项移到同一边做一步代数变形再继续解。3. 代码落地从公式到能AC的程序3.1 C版本逆元、浮点、预处理一个都不能少先给一个最常见的实现框架假设题目是等概率集齐模型n最大到10的6次方要求输出分数取模。那么我们需要预处理1到n的逆元累加得到调和级数再乘上n。#include bits/stdc.h using namespace std; const long long MOD 998244353; long long qpow(long long a, long long b) { long long res 1; while (b) { if (b 1) res res * a % MOD; a a * a % MOD; b 1; } return res; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; long long harmonic 0; for (int i 1; i n; i) { harmonic (harmonic qpow(i, MOD - 2)) % MOD; } long long ans harmonic * n % MOD; cout ans \n; return 0; }这里有几个细节要注意。qpow(i, MOD-2)用费马小定理求逆元前提是MOD是质数且i不是MOD的倍数竞赛里常见的998244353和1000000007都满足。如果n特别大逐个求快速幂会慢一些更高效的做法是先用线性递推求出所有逆元时间复杂度O(n)不过对于10的6次方级别快速幂也能接受。3.2 Python版本什么时候该用分数而非浮点蓝桥杯允许使用Python但Python的时间常数较大需要更小心。如果题目要求直接输出小数可以用float累加但n很大时浮点累加的精度不够应该改用数学公式或者分段累加。如果题目要求输出分数取模Python有个天然优势内置的pow函数可以直接求模逆元代码非常简洁。但要注意Python的递归和循环速度较慢10的6次方的for循环配合pow调用在时间紧张时可能压线建议适当优化。MOD 998244353 def solve(): n int(input()) ans 0 for i in range(1, n 1): ans (ans pow(i, MOD - 2, MOD)) % MOD print(ans * n % MOD) if __name__ __main__: solve()这个版本的实现思路和C完全一致区别只是pow函数内置了快速幂。如果你担心常数问题可以把逆元预先算成列表用一个递推公式inv[i] MOD - MOD // i * inv[MOD % i] % MOD这样单个循环里没有快速幂会快很多。3.3 关于“输出的分数取模”的推导很多同学不理解为什么概率期望题要用分数取模输出。原因是浮点数有精度误差在多组数据对比答案时一个微小的误差可能导致判断错误。所以命题人会让选手输出最简分数取模后的结果这样答案唯一确定。把期望E表示成分数分子分母可能非常大所以用模数下的数值代替。核心操作是对于每个分母d我们需要计算d在模MOD意义下的逆元inv(d)然后把所有项加起来。如果你碰到的题目不是等概率而是任意概率同样可以用这种思路每个分数项的分母是若干概率之和对每个分式分母求逆元再相加。注意这里的“概率之和”如果本身也是分数需要先做分数运算还是直接取模取决于题目给的是整数概率还是浮点概率。我的建议是不管题目怎么描述先在草稿纸上把所有期望公式写成纯分数形式再翻译成取模代码。跳过这一步直接调库很容易在容斥项的正负号上出错。3.4 复杂度估算数据范围教你选算法拿到数据范围后可以用一张表快速判断该用什么算法我把常见情况整理成下面这个表格适用于大多数抽奖类题目。n的范围可接受的复杂度推荐算法n 10O(2^n)状态压缩DP或容斥枚举n 10^3O(n^2)动态规划逐个状态转移n 10^5O(n log n)线性DP配合前缀和优化n 10^6O(n)公式推导调和级数累加n 10^9O(log n)数论公式分块求和或杜教筛这里特别想强调n到达10的6次方以上时一定要试着把期望公式化简成可以数学求和的形式。蓝桥杯考场上很多同学不是不会推期望而是推出来是O(n^2)的式子结果连样例都过不了还不知道问题出在复杂度上。4. 考场上的Bug清单与排查思路4.1 浮点精度为什么WA却看不出错概率期望题用double输出是目前最常见的WA原因。double在累加1/i时当i到10的6次方级别累加误差会积累到可以影响第6位小数的程度。题目如果要求保留6位小数这种误差正好卡在边界上有时候本地输出和答案一模一样交上去就是错。解决方法是能用分数取模就绝不用浮点。如果题目坚持要浮点输出可以试试用long double并且把累加方向从小往大加这样能减少误差。更稳妥的办法是把期望公式改成“从大项到小项”的反向计算但效果有限。我自己一般会先跑一个暴力模拟小数据和公式结果对比误差超过1e-9就说明精度策略要换。4.2 逆元与整数溢出两个最常见的坑使用费马小定理求逆元时底数和模数可能都很大乘法过程要用long long并且每步取模防止溢出。C里a * b % MOD当a和b接近MOD时即使a和b各不超过long long乘积也可能溢出。解决方法是使用__int128临时存储或者用快速乘算法。另一个坑是负数的模运算。容斥公式里有(-1)次方项在累加时要先加MOD再对MOD取模否则C里负数取模结果可能为负导致答案错得毫无规律。4.3 边界情况n1、概率为0、答案无穷大n1时期望次数就是1除以抽中概率但要注意如果题目构造的“抽中概率”可能为0那么期望是无穷大这种情况题目一般会给你一个特殊约定比如保证概率为正或者要求输出一个特定的标志。读题时务必看一眼是否有这类说明。概率为0的项出现在期望公式的分母里时程序会直接除零报错。所以代码里要对p_i做一次非零过滤或者确保输入数据不会出现这种情况。蓝桥杯的题目通常有数据保证但你不能假设它一定不会出极端数据。4.4 当TLE出现时先检查这几个位置超时在期望题里很常见多不是因为算法复杂度高而是因为代码里有隐形的高开销操作。第一个位置是逆元的求法。在循环里反复调用快速幂每次O(log MOD)累计起来非常可观。改成线性递推逆元只需要O(1)转移这个是省时间的重点。第二个位置是浮点运算。double的乘除比整数慢但题目如果只要求整数取模根本不该出现浮点运算。很多人习惯用double数组存概率其实可以全部转成模运算。第三个位置是输入输出。蓝桥杯的样例规模可能很大scanf/printf或cin关闭同步都是必须的。Python用户要注意input()的一次性读入用sys.stdin.buffer.read()可以省下大量时间。4.5 一个快速自查的题目速查表我在备考时自己总结了一张抽奖题自查表每次交题前按顺序过一遍能有效降低罚时。放在这里供参考。检查项具体动作对应风险数据范围确认n上限反推复杂度算法选错导致TLE输出形式分数取模还是浮点精度或逆元遗漏概率是否相等相等才可用调和级数公式推错是否存在决策有决策则必须DP状态转移遗漏选项转移是否有环方程两边同状态要移项递归死循环逆元底数是否为0先特判概率为0的情况除零错误负数取模容斥结果加MOD再取模答案变成负数long long溢出乘法用快速乘或__int128答案错误这张表看起来简单但每次都能拦住至少一道题的低级失误。省赛时间宝贵与其反复调试不如在编码前自查。5. 省赛时间分配与这类题的通用套路5.1 多长时间做不出来就该先跳题蓝桥杯省A组的题目通常有10道时间有限如果一道抽奖题你读完题15分钟内没有形成完整思路我建议先跳过去做后面的暴力送分题。抽奖这类题往往放在中间或靠后的位置分值不算最高但思考成本很大。我的经验是先快速扫描全部题目把能直接拿部分分的题先写掉再回头啃硬骨头。很多同学喜欢死磕抽奖题结果最后简单题没时间做很不划算。竞赛比的不是单题AC而是总分。5.2 把“抽奖”题的解法沉淀成模板我个人会把抽奖题的解法模板化成几个固定片段求逆元、调和级数累加、容斥枚举、状态压缩DP。每个片段单独写过并通过几道验证题考场上就能像搭积木一样快速组合。特别是逆元的线性递推模板必须背得滚瓜烂熟。C里一行递推和预处理数组很多期望题都靠它保底。另外输出分数取模的通用函数也可以提前写好省去现场推导时间。5.3 我的一点个人经验带学生打了几年蓝桥杯我的感觉是抽奖这类题是区分度非常高的一道题它考的不是你会不会背公式而是你能不能把一个实际问题抽象成数学结构再果断用代码实现。如果你现在看到这类题还是发怵最好的办法不是刷一百道新题而是把这一道题从推导到实现完整重做三遍直到闭着眼都能写出那几行核心递推。另外想多说一句赛前一定要亲自把逆元、快速幂、容斥这些基础模板敲一遍不要眼高手低。很多同学看别人的代码觉得简单自己一写就各种编译错误。考场上时间宝贵任何一次低级失误都可能让你的省一变成省二。希望这篇拆解能让你在遇到“抽奖”题时多一分从容。