企业官网建设流程全解析

今年蓝桥杯省赛A组有一道题让很多人在考场上卡了很久：P12140，题目名叫“抽奖”。赛后群里讨论热度不低，因为这道题表面看是概率期望，实际还埋了组合计数、浮点精度和取模运算的坑。如果你打算打蓝桥杯，或者正在备战接下来的算法竞赛，这篇文章我想把这类抽奖题的完整思考过程拆给你看——从怎么读题，用什么数学模型，到最后一行的代码怎么写，全部过一遍。考虑到很多同学拿到的题目描述版本不太一样，我不逐字复述题面，只讲这类“抽奖”题背后最核心的数学结构和代码实现，这样不管题目具体长什么样，思路都能直接迁移。

1. 先分清“抽奖”到底在考什么

1.1 从标题能判断出的考察方向

“抽奖”这个题名在算法竞赛里是一个很典型的信号，它几乎不会真的让你去模拟抽奖过程，而是借抽奖的外壳考察两件事：第一是“期望”的计算能力，第二是“最优策略”的推导能力。蓝桥杯省A组的题目很少会只考一个孤立知识点，抽奖题尤其喜欢把概率期望、组合数学、动态规划甚至数论取模揉在一起。

如果你看到题目里出现“随机抽取”“概率”“期望”“至少多少次”“中奖”这些词，基本可以确定这是一道概率期望题。而蓝桥杯的概率期望题有一个共同特点：它不会直接给你一个现成的公式背，而是需要你自己从过程描述里把数学模型抽出来。

1.2 省A组“抽奖”类题目的三种常见模型

我梳理了近几年的蓝桥杯及相关竞赛题目，发现抽奖题翻来覆去就三个模型：

第一种是“集齐型”，题目说有n种奖品，每次抽奖等概率拿到其中一种，问集齐所有种类的期望次数。这种模型在数学上叫优惠券收集者问题，答案是n乘上调和级数。如果题目再复杂一点，会给每种奖品不同的中奖概率。

第二种是“决策型”，每次抽奖后可以选择继续抽还是停止，目标是最大化收益或最小化期望花费。这种题通常要用动态规划，把当前状态下的最优期望写进状态转移方程。

第三种是“条件概率型”，比如抽奖过程中有“中大奖后重新开始”之类的状态转移，或者要计算某个特定事件发生的概率。这种题的本质是马尔可夫过程，但竞赛里不会考那么深，一般用线性方程组或递推就能解。

P12140这道题到底属于哪一种，受限于我拿到的信息量，我不能百分百断言。但从“抽奖”这个命名习惯和题目编号对应的难度来看，它大概率落在第一种或第二种，而且最有可能的是：表面是第一种，实际需要运用到第二种的思维来优化。

1.3 拿到题目先别急着写代码：三读数据范围

很多同学一看到题目就打开编辑器敲代码，这是大忌。省赛的坑往往不在算法难，而在数据范围没看仔细。抽奖题尤其如此。

第一遍读题，搞清楚n是多少。如果n很小，比如n<=20，那大概率可以用状态压缩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_{i+1}

移项整理得到：

E_i = n/(n-i) + E_{i+1}

从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到达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 边界情况：n=1、概率为0、答案无穷大

n=1时，期望次数就是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 一个快速自查的题目速查表

我在备考时自己总结了一张抽奖题自查表，每次交题前按顺序过一遍，能有效降低罚时。放在这里供参考。

这张表看起来简单，但每次都能拦住至少一道题的低级失误。省赛时间宝贵，与其反复调试，不如在编码前自查。

5. 省赛时间分配与这类题的通用套路

5.1 多长时间做不出来就该先跳题

蓝桥杯省A组的题目通常有10道，时间有限，如果一道抽奖题你读完题15分钟内没有形成完整思路，我建议先跳过，去做后面的暴力送分题。抽奖这类题往往放在中间或靠后的位置，分值不算最高，但思考成本很大。

我的经验是：先快速扫描全部题目，把能直接拿部分分的题先写掉，再回头啃硬骨头。很多同学喜欢死磕抽奖题，结果最后简单题没时间做，很不划算。竞赛比的不是单题AC，而是总分。

5.2 把“抽奖”题的解法沉淀成模板

我个人会把抽奖题的解法模板化成几个固定片段：求逆元、调和级数累加、容斥枚举、状态压缩DP。每个片段单独写过并通过几道验证题，考场上就能像搭积木一样快速组合。

特别是逆元的线性递推模板，必须背得滚瓜烂熟。C++里一行递推和预处理数组，很多期望题都靠它保底。另外，输出分数取模的通用函数也可以提前写好，省去现场推导时间。

5.3 我的一点个人经验

带学生打了几年蓝桥杯，我的感觉是，抽奖这类题是区分度非常高的一道题，它考的不是你会不会背公式，而是你能不能把一个实际问题抽象成数学结构，再果断用代码实现。如果你现在看到这类题还是发怵，最好的办法不是刷一百道新题，而是把这一道题从推导到实现完整重做三遍，直到闭着眼都能写出那几行核心递推。

另外想多说一句，赛前一定要亲自把逆元、快速幂、容斥这些基础模板敲一遍，不要眼高手低。很多同学看别人的代码觉得简单，自己一写就各种编译错误。考场上时间宝贵，任何一次低级失误都可能让你的省一变成省二。希望这篇拆解能让你在遇到“抽奖”题时，多一分从容。