抽奖期望题核心解法：从期望DP到指示器变量的随机过程思维

1. 题目还原：把"抽奖"翻译成一个能计算的随机过程

蓝桥杯省 A 组今年的 P12140"抽奖"，考完以后讨论度不低。很多选手跟我交流时都说，这题读题花了十分钟，真正写代码反而两分钟就结束了。这其实就是近几年省 A 的典型风格：背景故事讲得很满，剥掉外壳以后，模型极其干净。

因为我这边没有官方题面的逐字版，只能按赛后流传的题意还原。如果你在考场上拿到的是完整题面，可以对照一下，核心模型是一样的：

有一个抽奖箱，里面放着 w 个白球和 b 个黑球。白球代表奖品球，摸到白球得 1 分，并且可以继续从箱子里摸下一个球；黑球代表终止球，摸到黑球抽奖立刻结束。所有球都是不放回的，也就是说每摸出一个球，箱子里就少一个球。问顾客最终得分的期望值是多少？

这道题虽然叫"抽奖"，但和我们平时说的"中奖概率是多少"完全不是一回事。它本质是一个随机过程，而不是一次独立事件。

先说一个最容易踩的直觉陷阱。如果只看单次摸球，摸到白球的概率确实是 w/(w+b)，很多人第一反应就是答案等于这个比例。但这个抽奖是"摸到白球必须继续摸"，那么一个白球被摸出来的前提是：它在所有黑球之前被摸到。这就引入了顺序和停止条件，答案从 w/(w+b) 变成了 w/(b+1)，多出来的那个 1，其实是"停止位置"造成的偏移。

为什么会有这个偏移？我后面会从三个角度去推，这里先建立一个标准记号。设状态为 E(w,b)，表示当前箱子里有 w 个白球、b 个黑球时，从此刻开始还能拿到的期望分数。最终答案就是 E(w,b)。

另外要提醒一点：如果题目没有额外说明，b=0 的情况会产生"永远停不下来"的语义问题。正常题面要么会保证 b≥1，要么会补一句"箱子摸空则自动结束"。两种约定下的期望是不同的，这一点我在第三节专门展开，很多人的分数就丢在这个边界上。

2. 三种推导：期望DP、指示器变量和空隙对称

2.1 先用期望 DP 手推小数据

最朴素的做法是设状态做期望递推。第一次摸球只有两种可能：

• 摸到白球，概率是 w/(w+b)。此时得 1 分，箱子里变成 w-1 个白球、b 个黑球，后续期望是 E(w-1,b)；
• 摸到黑球，概率是 b/(w+b)。此时得 0 分，过程结束。

所以：

E(w,b) = w/(w+b) × (1 + E(w-1,b)) + b/(w+b) × 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 × (1+1/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 × (1+E(2,1)) = 3/4 × 2 = 3/2。

把结果列出来：E(1,1)=1/2，E(2,1)=1，E(1,2)=1/3，E(3,1)=3/2。如果把答案和 w/(b+1) 对照：1/(1+1)=1/2，2/(1+1)=1，1/(2+1)=1/3，3/(1+1)=3/2，全部吻合。到这里基本可以确定闭合公式就是 w/(b+1)。

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 个黑球这 b+1 个对象中，它排在第一个。为什么？因为一旦任何一个黑球先出现，抽奖就立刻停止，第 i 个白球再也摸不到；只有当它比所有黑球都靠前，它才会在停止之前被摸出来。

这 b+1 个对象的相对顺序是均匀随机的，所以第 i 个白球排在第一个的概率就是 1/(b+1)。

注意，这里不需要关心其他白球在哪里。其他白球无论排在第 i 个白球前面还是后面，都不影响结论。这样我们就得到了：

E = w × 1/(b+1) = w/(b+1)

这个推导成立的关键是"指示变量之间不要求独立"。期望的线性性对任何随机变量都成立，哪怕它们强相关。这就是为什么用这个方法的效率远高于写 DP：w 个白球看似纠缠在一起，实际上每个白球的"命运"只由它和 b 个黑球的相对排列决定。

2.3 用"空隙"模型做最后一个直觉验证

第三种视角我觉得更适合讲给别人听，也适合在草稿纸上快速检查。

把 b 个黑球想象成 b+1 个空隙的隔板。任意摸球顺序等价于把 w 个白球随机撒进这 b+1 个空隙里。抽奖会碰到第一个黑球就停止，所以最终能被摸出来的白球，只有落在第一个空隙里的那些，其余空隙里的白球全都拿不到。

每个白球落在任意空隙的概率都是 1/(b+1)，于是落在第一个空隙的白球期望数就是 w/(b+1)。

这个空隙模型还有一个额外好处：它直接解释了为什么分子是 w、分母是 b+1，而不是 b。因为黑球把序列切成了 b+1 段，停止点只在第一个空隙之后立刻出现，最终能拿走的部分就是"第一段"的期望长度。

我建议有排列组合基础的同学彻底记住这三种思路。它们的适用范围略有不同：期望 DP 适合状态少、能递推的题；指示器变量适合能定义"单位贡献"的题；空隙模型适合停止位置明确的顺序题。P12140 属于最后一种，所以考场上最省时间的其实是空隙模型。

2.4 补充一个容易混的变体：有放回抽奖的期望是 w/b

很多同学做完这道题以后会拿它和有放回的情况对比，这是一个很好的习惯。如果把规则改成"每次摸球后把球放回去"，也就是每次摸到白球的概率恒为 w/(w+b)，摸到黑球概率恒为 b/(w+b)，那么这变成一个标准的几何分布问题。摸到黑球才停止，摸到白球的数量期望是：

w/(w+b) ÷ b/(w+b) = w/b

对比一下就能看到，无放回是 w/(b+1)，有放回是 w/b。区别就在于无放回时，每摸出一个白球，后续白球的相对占比其实在下降，而且"停止位置"本身也挤掉了一个概率名额。这个 1 的差异在出题人眼里就是区分你有没有真正理解随机过程的关键。

3. 输出形式才是真正的丢分点：分数取模与边界处理

公式一旦变成 w/(b+1)，这题似乎就结束了。但蓝桥杯省 A 的题目不会让你轻轻松松输出一个小数，因为 w/(b+1) 很可能不是有限小数，比如 w=1、b=2 时答案是 1/3，浮点数在判题里会产生精度问题。所以出题人通常会要求两种输出方式之一：

• 输出最简分数 p/q；
• 输出 p × q 在模 M 意义下的逆元，即 p * q^{M-2} mod M。

这两种我都实现过，下面分别说明。

先统一做约分：

• g = gcd(w, b+1)
• 化简后分子 num = w/g
• 化简后分母 den = (b+1)/g

如果题目要求最简分数，直接输出 num 和 den 就行，中间用斜杠隔开。这里唯一要注意的是数据范围：如果 w 和 b 都是 10^18 级别，num 和 den 仍然在 long long 能表示的范围内，输出没有问题。

如果题目要求模意义下的值，就用费马小定理求逆元。模数 M 一般是 1e9+7 或 998244353，两者都是质数。代码逻辑是：

ll inv = pow_mod(den % MOD, MOD - 2, MOD); ll ans = (num % MOD) * inv % MOD;

这里有几个我在实际提交中踩过的坑。

第一个坑：读入类型。b+1 可能达到 10^18 甚至更大，如果你用 int 读 b，直接溢出变成负数。不要问我是怎么知道的。蓝桥杯的评测机不会给你任何溢出警告，结果只会显示"答案错误"。所以读入请用 long long。

第二个坑：约分前先算 b+1。有人会先对 w 和 b 求 gcd，然后拿 gcd 去除 w 和 b，再用结果算分母，这种写法在 b=0 时会把分母算成 1，最后答案变成 w，看起来挺正常，但本质上没理解分数为什么可以约分。正确做法是先构造 b+1，再约分。

第三个坑：取模输出时，分子为 0 的情况。如果 w=0，那么答案就是 0。有些模板会在 num==0 时仍然去求逆元，虽然模数是质数时逆元大概率存在，但多一步计算完全没有必要，而且存在"分母恰好是模数的倍数"这种极端数据时可能出错。稳妥起见，先判断 num==0，直接输出 0 结束。

第四个坑：分母可能等于 MOD 的倍数。理论上如果 b+1 是 1e9+7 的倍数，逆元不存在。竞赛数据一般不会这么构造，但严谨的写法应该判断一下。如果你在本地对拍时发现某个数据点跑出来逆元是 0，多半就是这个原因。

边界情况再梳理一遍：

• 如果 w=0，答案恒为 0，没有任何悬念；
• 如果 b=0，要看题面有没有"箱子摸空自动结束"的约定。如果有，答案等于 w，因为你会把所有白球全部摸完；如果没有这个约定，过程不会停止，期望是无穷大。正规题面一定会写清楚这一点，考场上碰到类似题目时建议先看数据范围和特殊约定；
• 如果 w 和 b 都很大，注意乘法前先取模，(num % MOD) * inv 这一步如果直接用 long long 乘，两个 10^9 级别的数相乘会接近 10^18，虽然不溢出，但随手再乘一个数就可能爆，所以每个乘法步骤都要取模。

这道题我见过不少人公式推对了，但输出写成分数时忘了约分，或者输出取模值时把 p/q 当成整数直接输出。建议写完之后用题目样例跑一遍，再用 w=1,b=2 这种分数结果验证一次。

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 是先算出来的 b+1，如果你写成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, trials=100000): 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

拿几组参数跑一下，和公式对表：

误差都在千分之一以内，说明模型和实现都没问题。这个习惯我保持了很久：凡是期望题，至少用模拟验证一次，哪怕只是心理安慰，也能避免重大理解失误。

5. 复盘：这类"抽奖"期望题真正的拿分点

把这道题翻来覆去讲完以后，我想聊聊对下一届有用的复盘心得。

省 A 组近几年特别喜欢出"数学期望 + 取模"的组合题。这种题有非常明显的套路特征：

第一，读题时要快速剥离背景。看到"抽奖""抽卡""摸球"这类字眼，先不要被词汇带进排列组合的泥潭。寻找三个关键词：是否连续操作、是否有停止条件、是否有计分规则。只要这三样齐全，大概率是期望题，考的是你对随机过程的理解，而不是暴力枚举。

第二，优先尝试"单位贡献"分解。看到期望就写二维 DP 是最亏的做法。期望的线性性是竞赛里性价比最高的工具之一，几乎所有期望题都能先问一句：能不能定义指示变量？在这道题里，一个白球就是一个单位贡献，问题瞬间变成求单一概率。省下的大量时间可以用来做检查或其他题。

第三，取模三件套必须形成肌肉记忆：gcd 约分、快速幂、费马小定理求逆元。我见过不少同学在赛场上临时推导 pow_mod，写得慢还容易错。建议在赛前把这几个模板抄到顺手，最好能做到不用想就写对。

第四，永远先手推三个小数据。拿到题后别急着敲键盘，先心算 E(1,1)、E(2,1)、E(1,2)，如果发现规律和猜测一致，再动手写代码。这个"猜规律 + 小数据验证"的组合，比直接开始推导要快很多，尤其适合题目背景比较绕的时候。

P12140 这道题本身不算是地狱难度，它考察的是你能不能把一个抽奖故事压缩成一行公式。只要把期望线性性、停止条件、分数取模这三层想清楚，在考场上就是一道 10 到 15 分钟的送分题。

最后再分享一个我自己的习惯：写这类期望题的时候，我会在草稿纸上先写一行"答案 = 白球数 / (黑球数 + 1)"，然后把数据往里代，感觉顺手了再写代码。这种仪式感看起来多余，但能防止最蠢的 +1 漏写。希望这篇复盘能帮你下次遇到抽奖题时，笑着把它写完。