1. 题目还原把抽奖翻译成一个能计算的随机过程蓝桥杯省 A 组今年的 P12140抽奖考完以后讨论度不低。很多选手跟我交流时都说这题读题花了十分钟真正写代码反而两分钟就结束了。这其实就是近几年省 A 的典型风格背景故事讲得很满剥掉外壳以后模型极其干净。因为我这边没有官方题面的逐字版只能按赛后流传的题意还原。如果你在考场上拿到的是完整题面可以对照一下核心模型是一样的有一个抽奖箱里面放着 w 个白球和 b 个黑球。白球代表奖品球摸到白球得 1 分并且可以继续从箱子里摸下一个球黑球代表终止球摸到黑球抽奖立刻结束。所有球都是不放回的也就是说每摸出一个球箱子里就少一个球。问顾客最终得分的期望值是多少这道题虽然叫抽奖但和我们平时说的中奖概率是多少完全不是一回事。它本质是一个随机过程而不是一次独立事件。先说一个最容易踩的直觉陷阱。如果只看单次摸球摸到白球的概率确实是 w/(wb)很多人第一反应就是答案等于这个比例。但这个抽奖是摸到白球必须继续摸那么一个白球被摸出来的前提是它在所有黑球之前被摸到。这就引入了顺序和停止条件答案从 w/(wb) 变成了 w/(b1)多出来的那个 1其实是停止位置造成的偏移。为什么会有这个偏移我后面会从三个角度去推这里先建立一个标准记号。设状态为 E(w,b)表示当前箱子里有 w 个白球、b 个黑球时从此刻开始还能拿到的期望分数。最终答案就是 E(w,b)。另外要提醒一点如果题目没有额外说明b0 的情况会产生永远停不下来的语义问题。正常题面要么会保证 b≥1要么会补一句箱子摸空则自动结束。两种约定下的期望是不同的这一点我在第三节专门展开很多人的分数就丢在这个边界上。2. 三种推导期望DP、指示器变量和空隙对称2.1 先用期望 DP 手推小数据最朴素的做法是设状态做期望递推。第一次摸球只有两种可能摸到白球概率是 w/(wb)。此时得 1 分箱子里变成 w-1 个白球、b 个黑球后续期望是 E(w-1,b)摸到黑球概率是 b/(wb)。此时得 0 分过程结束。所以E(w,b) w/(wb) × (1 E(w-1,b)) b/(wb) × 0边界条件是 E(0,b)0因为箱子里没有白球可摸了。我习惯把这个递推写成代码前先手算几个小数据确认规律E(1,1)第一次摸到白球概率 1/2得 1 分后状态变成 E(0,1)0摸到黑球概率 1/2得 0 分。所以 E(1,1)1/2。E(2,1)第一次摸到白球概率 2/3得 1 分后状态变成 E(1,1)1/2摸到黑球概率 1/3。所以 E(2,1)2/3 × (11/2)1。E(1,2)第一次摸到白球概率 1/3得 1 分后状态变成 E(0,2)0摸到黑球概率 2/3。所以 E(1,2)1/3。E(3,1)E(3,1)3/4 × (1E(2,1)) 3/4 × 2 3/2。把结果列出来E(1,1)1/2E(2,1)1E(1,2)1/3E(3,1)3/2。如果把答案和 w/(b1) 对照1/(11)1/22/(11)11/(21)1/33/(11)3/2全部吻合。到这里基本可以确定闭合公式就是 w/(b1)。DP 递推在数据范围小的时候是能跑的但 O(wb) 的状态数面对 10^9 级别的范围根本不现实。它的价值主要体现在验证和小数据对拍上。2.2 用指示器变量直接一步到位真正考场上应该用的方法是期望的线性性。设第 i 个白球最终能被摸出的指示变量为 X_i那么总分就是 X_1 X_2 ... X_w期望等于每个变量期望的和。而 E[X_i] 就等于第 i 个白球被摸出的概率。于是E Σ P(X_i 1)关键问题是P(X_i 1) 等于多少第 i 个白球能被摸出当且仅当在它和所有 b 个黑球这 b1 个对象中它排在第一个。为什么因为一旦任何一个黑球先出现抽奖就立刻停止第 i 个白球再也摸不到只有当它比所有黑球都靠前它才会在停止之前被摸出来。这 b1 个对象的相对顺序是均匀随机的所以第 i 个白球排在第一个的概率就是 1/(b1)。注意这里不需要关心其他白球在哪里。其他白球无论排在第 i 个白球前面还是后面都不影响结论。这样我们就得到了E w × 1/(b1) w/(b1)这个推导成立的关键是指示变量之间不要求独立。期望的线性性对任何随机变量都成立哪怕它们强相关。这就是为什么用这个方法的效率远高于写 DPw 个白球看似纠缠在一起实际上每个白球的命运只由它和 b 个黑球的相对排列决定。2.3 用空隙模型做最后一个直觉验证第三种视角我觉得更适合讲给别人听也适合在草稿纸上快速检查。把 b 个黑球想象成 b1 个空隙的隔板。任意摸球顺序等价于把 w 个白球随机撒进这 b1 个空隙里。抽奖会碰到第一个黑球就停止所以最终能被摸出来的白球只有落在第一个空隙里的那些其余空隙里的白球全都拿不到。每个白球落在任意空隙的概率都是 1/(b1)于是落在第一个空隙的白球期望数就是 w/(b1)。这个空隙模型还有一个额外好处它直接解释了为什么分子是 w、分母是 b1而不是 b。因为黑球把序列切成了 b1 段停止点只在第一个空隙之后立刻出现最终能拿走的部分就是第一段的期望长度。我建议有排列组合基础的同学彻底记住这三种思路。它们的适用范围略有不同期望 DP 适合状态少、能递推的题指示器变量适合能定义单位贡献的题空隙模型适合停止位置明确的顺序题。P12140 属于最后一种所以考场上最省时间的其实是空隙模型。2.4 补充一个容易混的变体有放回抽奖的期望是 w/b很多同学做完这道题以后会拿它和有放回的情况对比这是一个很好的习惯。如果把规则改成每次摸球后把球放回去也就是每次摸到白球的概率恒为 w/(wb)摸到黑球概率恒为 b/(wb)那么这变成一个标准的几何分布问题。摸到黑球才停止摸到白球的数量期望是w/(wb) ÷ b/(wb) w/b对比一下就能看到无放回是 w/(b1)有放回是 w/b。区别就在于无放回时每摸出一个白球后续白球的相对占比其实在下降而且停止位置本身也挤掉了一个概率名额。这个 1 的差异在出题人眼里就是区分你有没有真正理解随机过程的关键。3. 输出形式才是真正的丢分点分数取模与边界处理公式一旦变成 w/(b1)这题似乎就结束了。但蓝桥杯省 A 的题目不会让你轻轻松松输出一个小数因为 w/(b1) 很可能不是有限小数比如 w1、b2 时答案是 1/3浮点数在判题里会产生精度问题。所以出题人通常会要求两种输出方式之一输出最简分数 p/q输出 p × q 在模 M 意义下的逆元即 p * q^{M-2} mod M。这两种我都实现过下面分别说明。先统一做约分g gcd(w, b1)化简后分子 num w/g化简后分母 den (b1)/g如果题目要求最简分数直接输出 num 和 den 就行中间用斜杠隔开。这里唯一要注意的是数据范围如果 w 和 b 都是 10^18 级别num 和 den 仍然在 long long 能表示的范围内输出没有问题。如果题目要求模意义下的值就用费马小定理求逆元。模数 M 一般是 1e97 或 998244353两者都是质数。代码逻辑是ll inv pow_mod(den % MOD, MOD - 2, MOD); ll ans (num % MOD) * inv % MOD;这里有几个我在实际提交中踩过的坑。第一个坑读入类型。b1 可能达到 10^18 甚至更大如果你用 int 读 b直接溢出变成负数。不要问我是怎么知道的。蓝桥杯的评测机不会给你任何溢出警告结果只会显示答案错误。所以读入请用 long long。第二个坑约分前先算 b1。有人会先对 w 和 b 求 gcd然后拿 gcd 去除 w 和 b再用结果算分母这种写法在 b0 时会把分母算成 1最后答案变成 w看起来挺正常但本质上没理解分数为什么可以约分。正确做法是先构造 b1再约分。第三个坑取模输出时分子为 0 的情况。如果 w0那么答案就是 0。有些模板会在 num0 时仍然去求逆元虽然模数是质数时逆元大概率存在但多一步计算完全没有必要而且存在分母恰好是模数的倍数这种极端数据时可能出错。稳妥起见先判断 num0直接输出 0 结束。第四个坑分母可能等于 MOD 的倍数。理论上如果 b1 是 1e97 的倍数逆元不存在。竞赛数据一般不会这么构造但严谨的写法应该判断一下。如果你在本地对拍时发现某个数据点跑出来逆元是 0多半就是这个原因。边界情况再梳理一遍如果 w0答案恒为 0没有任何悬念如果 b0要看题面有没有箱子摸空自动结束的约定。如果有答案等于 w因为你会把所有白球全部摸完如果没有这个约定过程不会停止期望是无穷大。正规题面一定会写清楚这一点考场上碰到类似题目时建议先看数据范围和特殊约定如果 w 和 b 都很大注意乘法前先取模(num % MOD) * inv 这一步如果直接用 long long 乘两个 10^9 级别的数相乘会接近 10^18虽然不溢出但随手再乘一个数就可能爆所以每个乘法步骤都要取模。这道题我见过不少人公式推对了但输出写成分数时忘了约分或者输出取模值时把 p/q 当成整数直接输出。建议写完之后用题目样例跑一遍再用 w1,b2 这种分数结果验证一次。4. 参考实现C 主解与 Python 对拍器4.1 C 实现我考场版本大概是这样的核心就三个函数gcd、快速幂、主逻辑。逻辑尽量短因为竞赛里你根本没有时间写花里胡哨的封装。#include bits/stdc.h using namespace std; typedef long long ll; ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; } ll pow_mod(ll a, ll k, ll mod) { ll res 1; a % mod; while (k) { if (k 1) res res * a % mod; a a * a % mod; k 1; } return res; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); ll w, b; cin w b; const ll MOD 1000000007LL; ll den b 1; ll g gcd(w, den); ll num w / g; den / g; if (num 0) { cout 0 \n; return 0; } ll inv pow_mod(den % MOD, MOD - 2, MOD); ll ans (num % MOD) * inv % MOD; cout ans \n; return 0; }这里解释几个细节。快速幂那个a % mod放在开头是为了防止 a 本身超过 long long 范围。虽然我们的 den 在约分之后不会太大但保险起见加上没有坏处。gcd(w, den)的调用顺序留意一下den 是先算出来的 b1如果你写成gcd(w, b)然后自己心算分母是 b/g很容易把 1 弄丢。这种错误在考场压力下非常常见建议写代码时直接把分母表达式写在变量名里类似long long denominator b 1;一目了然。4.2 Python 对拍脚本Python 写起来就舒服很多尤其是Fraction会自动约分特别适合赛后验证。import math from fractions import Fraction w, b map(int, input().split()) den b 1 g math.gcd(w, den) num w // g den // g # 如果题目要求输出最简分数 print(f{num}/{den}) # 如果题目要求取模再算一下 MOD 10**9 7 ans (num % MOD) * pow(den % MOD, MOD - 2, MOD) % MOD print(ans)Fraction的版本更简短适合丢进对拍脚本里当标准答案from fractions import Fraction w, b map(int, input().split()) frac Fraction(w, b 1) print(f{frac.numerator}/{frac.denominator})两种写法结果一致。我自己本地验证时一般用Fraction版本做基准用 C 版本做被测程序然后跑随机数据对拍。4.3 用随机模拟做交叉验证虽然公式可以严格证明但考场上最怕的是模型理解错。我会再写一个 30 行以内的模拟程序用随机生成排列的方式逼近答案import random def simulate(w, b, trials100000): total 0 for _ in range(trials): balls [w] * w [b] * b random.shuffle(balls) score 0 for ball in balls: if ball b: break score 1 total score return total / trials拿几组参数跑一下和公式对表参数 (w, b)公式 w/(b1)10 万次模拟(1, 1)0.50.5001(2, 1)1.00.9987(1, 2)0.33330.3329(3, 2)1.01.0002(5, 3)1.251.2506(10, 7)1.251.2491误差都在千分之一以内说明模型和实现都没问题。这个习惯我保持了很久凡是期望题至少用模拟验证一次哪怕只是心理安慰也能避免重大理解失误。5. 复盘这类抽奖期望题真正的拿分点把这道题翻来覆去讲完以后我想聊聊对下一届有用的复盘心得。省 A 组近几年特别喜欢出数学期望 取模的组合题。这种题有非常明显的套路特征第一读题时要快速剥离背景。看到抽奖抽卡摸球这类字眼先不要被词汇带进排列组合的泥潭。寻找三个关键词是否连续操作、是否有停止条件、是否有计分规则。只要这三样齐全大概率是期望题考的是你对随机过程的理解而不是暴力枚举。第二优先尝试单位贡献分解。看到期望就写二维 DP 是最亏的做法。期望的线性性是竞赛里性价比最高的工具之一几乎所有期望题都能先问一句能不能定义指示变量在这道题里一个白球就是一个单位贡献问题瞬间变成求单一概率。省下的大量时间可以用来做检查或其他题。第三取模三件套必须形成肌肉记忆gcd 约分、快速幂、费马小定理求逆元。我见过不少同学在赛场上临时推导 pow_mod写得慢还容易错。建议在赛前把这几个模板抄到顺手最好能做到不用想就写对。第四永远先手推三个小数据。拿到题后别急着敲键盘先心算 E(1,1)、E(2,1)、E(1,2)如果发现规律和猜测一致再动手写代码。这个猜规律 小数据验证的组合比直接开始推导要快很多尤其适合题目背景比较绕的时候。P12140 这道题本身不算是地狱难度它考察的是你能不能把一个抽奖故事压缩成一行公式。只要把期望线性性、停止条件、分数取模这三层想清楚在考场上就是一道 10 到 15 分钟的送分题。最后再分享一个我自己的习惯写这类期望题的时候我会在草稿纸上先写一行答案 白球数 / (黑球数 1)然后把数据往里代感觉顺手了再写代码。这种仪式感看起来多余但能防止最蠢的 1 漏写。希望这篇复盘能帮你下次遇到抽奖题时笑着把它写完。