如果让我从近年的算法竞赛题库里挑一道“看着像纯概率、其实一行公式就能秒”的入门题我会选 P1297《单选错位》。题面不复杂有 n 道单选题第 i 题有 a_i 个选项每道题的正确答案等概率地出现在这 a_i 个选项里。有个同学填答题卡时看错了题号把第 i 题的答案涂到了第 i1 题的位置第 n 题的答案涂到第 1 题。问他期望答对多少题只要思路对头最终答案就是一行求和公式代码甚至不用开数组。很多初学者拿到这种题第一反应是模拟随机的正确答案或者想用动态规划记录“当前错位状态”其实完全不需要。这道题希望传递的核心思想是把“答对的题数”拆成每个位置答对事件的期望之和再利用两个独立均匀随机变量相等的概率每个事件直接算成 1/max(a_i, a_{i-1})。本文会从暴力枚举讲起先让你信服这个公式再做严格推导最后给出可提交的代码和踩坑记录。无论你是刚接触期望题的新人还是想找一道经典题给学员讲透的老师这篇应该都能帮上忙。1. 题目模型与核心思路1.1 错位是怎么发生的先还原一下场景。假设考试一共 3 道题这位同学的答案是按照第 1、2、3 题的顺序写下来的但他抄到答题卡时整体往后挪了一位第 1 题答案写到了第 2 题位置第 2 题答案写到了第 3 题位置第 3 题答案写到了第 1 题位置。于是答题卡上第 1 题位置的答案其实是第 3 题原本的答案第 2 题位置的答案其实是第 1 题原本的答案第 3 题位置的答案其实是第 2 题原本的答案。这个关系是一个固定的一一映射。你不需要关心他哪道题“本来该选什么”只需要知道对于任意第 i 题位置涂在上面的答案来自第 (i-1) 题特别地第 1 题位置上的答案来自第 n 题。换句话说位置 i 的答案等于第 (i-1) 题的正确答案。定义一个下标 0 表示 n就能把环形边界也纳入统一公式。如果每道题的正确答案是确定的那整个问题就变成简单的字符串比较。但题目故意加入了随机性每道题的正确答案都在 a_i 个选项中等概率选取。这样才能把问题变成概率期望也让“答对题数”变成随机变量。1.2 随机变量每个选项都可能是对的我们用 X_i 表示第 i 题的正确选项它是一个离散均匀随机变量取值范围是 {1, 2, ..., a_i}且 P(X_i k) 1/a_i。题目没有明说的几个默认条件必须点出来一是所有题目的正确选项相互独立二是每道题的选项编号虽然各自数量不同但都是从同一个“选项池”里取的比如第 i 题有 a_i 个选项那它的选项就是 1 到 a_i而另一题可能是 1 到 a_j两者重叠部分恰好是 min(a_i, a_j)。为什么独立很重要因为第 i 题位置涂的是第 (i-1) 题的正确答案而这个正确答案又和第 i 题正确答案是独立的。如果正确选项之间存在关联比如前后两题总是设置同一正确答案那题目就会复杂很多但竞赛题通常默认独立。这也是概率期望题最常见的“理想化”背景。1.3 目标期望答对题数不是模拟设 S 为答对的总题数我们把每题是否答对定义成事件指示变量 Y_i如果第 i 题位置答对了Y_i1否则 Y_i0。那么 S Y_1 Y_2 ... Y_n。要求 E[S]很多新手会想着穷举所有可能的正确选项组合再统计每种组合下答对几题最后加权平均。这在小数据下可行但 n 一大就废了。实际上期望有线性性E[S] E[Y_1] E[Y_2] ... E[Y_n]这件事不需要各 Y_i 独立也能成立。所以只要单独算出每个位置答对的概率加起来就是答案。这就是整道题的核心思路。有的朋友可能会问Y_i 和 Y_{i1} 明明有很强的关联比如第 i 题和第 i1 题共用了一些随机变量为什么还能直接加这就是期望线性性的妙处。就像掷两颗骰子问你两颗骰子点数和期望你不会去管第一颗大时第二颗是不是大概率小直接把各自的期望 3.5 相加得到 7。这个道理放在这里完全适用。2. 手算验证为什么答案是 1 / max(a_i, a_{i-1})2.1 用 n2 小样例先猜结论空讲公式不直观先拿一个最小的例子验证。设 n2两题的选项数分别是 a_12a_23。那么第一题正确选项 X_1 从 {1,2} 中选第二题正确选项 X_2 从 {1,2,3} 中选。由于错位是往后的第 1 题位置涂的是第 2 题答案即 X_2第 2 题位置涂的是第 1 题答案即 X_1。于是第 1 题答对当且仅当 X_2 X_1第 2 题答对当且仅当 X_1 X_2。在这个例子里两个事件其实完全同时发生总共答对题数要么是 2要么是 0。X_1 和 X_2 相同的概率是多少X_2 落在 {1,2} 的概率是 2/3落在那两个值中任意一个后X_1 恰好等于它的概率是 1/2所以总概率为 2/3 × 1/2 1/3。两题都一样的概率是 1/3则期望答对题数 2 × 1/3 2/3。注意这里每个位置答对概率都是 1/3如果用公式写就是 1/max(a_1,a_2) 1/3。为什么是 max 而不是 min因为两个均匀随机变量的共同取值有 min 个而组合总数是 a_{i-1}×a_i所以概率等于 min/(a_{i-1}×a_i) 1/max。这个直觉可以先记下来。2.2 枚举全部答案组合枚举 X_1 和 X_2 的所有组合一共 2×36 种每种等概率 1/6。我列一张表第一列为第 1 题答案第二列为第 2 题答案然后看答题卡上的判分。X_1X_2第1题位置答案第1题是否对第2题位置答案第2题是否对答对总数11X_21对X_11对212X_22不对X_11不对013X_23不对X_11不对021X_21不对X_12不对022X_22对X_12对223X_23不对X_12不对0把答对总数加起来是 200020 4平均到 6 种情况得到 4/6 2/3。这个结果和 1/31/32/3 完全一致。一旦理解了“每个位置答对概率相等且为 1/max”整个问题的求和公式就水到渠成。2.3 暴力程序对照为了更直观可以写一个暴力枚举程序来验算任意小数据。下面的 Python 代码枚举所有可能正确答案统计总答对数再除以情况数得到期望同时用公式算一遍两边对比。这样能帮你发现推导中的错误。import itertools def brute(n, a): # 每题的选项范围 1..a[i] total_correct 0 total_cases 0 # 生成每种正确答案组合长度为n for choices in itertools.product(*[range(1, x1) for x in a[1:]]): # choices[0] 对应第1题答案choices[1] 对应第2题答案... choices (0,) choices score 0 for i in range(1, n1): # 位置 i 的答案来自 i-1 题i1时来自第n题 src n if i 1 else i-1 if choices[src] choices[i]: score 1 total_correct score total_cases 1 return total_correct / total_cases def formula(n, a): ans 0.0 for i in range(1, n1): pre n if i 1 else i-1 ans 1.0 / max(a[pre], a[i]) return ans n 3 a [0, 2, 3, 4] print(暴力:, brute(n, a)) print(公式:, formula(n, a))实测输出应该一致。注意暴力里我把数组下标从 1 开始所以给 a 时前面塞了一个 0。这种“先暴力验小数据再上公式”的顺序是我做期望题最喜欢的检查方式。3. 严格推导期望线性性 独立均匀变量3.1 定义事件和随机变量现在建立完整的记号。第 i 题的正确答案记为 X_iX_i 在 {1,2,...,a_i} 上等概率取值。第 i 题位置涂的答案记为 B_i。由于错位规则B_i X_{i-1}其中下标按环形理解X_0 就是 X_n。第 i 题答对事件 A_i 就是 {B_i X_i}即 {X_{i-1} X_i}。所以我们只需要计算两题正确答案相同的概率。这里有个细节值得强调B_i 并不是一个独立于 X_i 的变量它其实就是另一个题的正确答案。由于题目给出各题正确答案独立所以 X_{i-1} 和 X_i 是相互独立的。如果“独立”这个条件被去掉下面整个推导都要推翻。这也是为什么很多期望题首先要读清楚随机性的来源。3.2 计算 P(X_{i-1} X_i)设前一个题有 u a_{i-1} 个选项当前题有 v a_i 个选项。两个随机变量 X_{i-1} 和 X_i 独立均匀分布。它们能相等的取值只能是两个取值范围交集里的元素交集大小是 min(u,v)。对于交集里的任意一个具体选项 kX_{i-1}k 的概率是 1/uX_ik 的概率是 1/v由于独立同时发生的概率是 1/(u v)。于是P(X_{i-1} X_i) Σ_{k ∈ 交集} P(X_{i-1}k) * P(X_ik) min(u,v) × (1/(u v)) 1/max(u,v)。最后一步是因为 u v / min(u,v) max(u,v)。这个推导很短但每一步都有意义求和范围为什么是交集概率为什么是一堆 1/(uv)。如果你只背公式很容易背成 1/min但如果你记住了推导就不会错。用场景举个例子u1v100。前题只有一个选项那它的正确选项固定就是那一个当前题有 100 个选项两者相等的概率只有 1/100。用 1/max(1,100) 得到 1/100合理。如果错误地用了 1/min会得到 1显然不符合直觉。这种样本边界是记忆公式的好帮手。3.3 环形索引与公式落地有了概率再把期望线性性用上E[S] Σ_{i1}^n P(A_i) Σ_{i1}^n 1 / max(a_i, a_{i-1})。这里规定 a_0 a_n。代码里如果数组下标从 1 开始i1 时的前一个是 a[n]而不是 a[0]除非你提前把 a[0] 复制成 a[n]。我个人习惯在代码里用 last 变量保存“前一个选项数”的循环方式这样既避免了数组寻址也更贴近“滚动生成”的场景。还可以注意到这个式子对 i 求和时所有相邻 pair (a_i, a_{i-1}) 都会被算一次是一个环形相邻对。3.4 为什么不需要考虑事件之间的独立性很多初学者在这里会卡住第 1 题答对和第 2 题答对显然不是独立的比如 n2 且 a1a2 时要么两题都对要么两题都错相关系数甚至等于 1但期望就是可以相加。这不是巧合而是期望线性性的一般结论对任意随机变量哪怕它们极度依赖和的期望等于期望的和。证明也很简单E[Y_1Y_2] E[Y_1]E[Y_2]这是积分/求和的可加性与联合分布无关。正因为如此我们不需要算复杂的联合概率不需要做 DP只需要把每个位置单独看。这个“线性拆解”的思想比这道题本身更重要。4. 参考代码与实现细节4.1 直接读数组版本大多数时候题目会直接把 a_i 作为输入给出来。此时一个最朴素的 C 解法如下#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorint a(n 1); for (int i 1; i n; i) { cin a[i]; } long double ans 0.0L; for (int i 1; i n; i) { int pre (i 1 ? a[n] : a[i - 1]); ans 1.0L / max(pre, a[i]); } cout fixed setprecision(6) (double)ans endl; return 0; }代码没什么花哨的就是把公式翻译了一遍。使用long double是为了累加很多项时尽量减少浮点误差如果你觉得没必要直接用 double 也通常能过但养成用 long double 的习惯对大量浮点累加的题目更稳妥。Python 版本同样很直接import sys def main(): data sys.stdin.buffer.read().split() if not data: return n int(data[0]) a [0] list(map(int, data[1:1 n])) ans 0.0 for i in range(1, n 1): pre a[n] if i 1 else a[i - 1] ans 1.0 / max(pre, a[i]) print(f{ans:.6f}) if __name__ __main__: main()注意 Python 的sys.stdin.buffer.read().split()一次性读取所有数据在 n 高达百万时也比逐行input()快很多。如果你的 OJ 给的 a 数组是一整行这个方法也能稳定解析。4.2 空间优化滚动写法什么时候能用上面的版本占用了 O(n) 的空间存储 a 数组。其实计算期望时每个位置 i 只依赖 a_i 和 a_{i-1}理论上不需要保存整个数组但坏就坏在 i1 时要用到 a_n而 a_n 数在最后才出现。如果输入是直接给数组且只能顺序读一遍你就必须先把所有值存下来或者第一遍先读入全部数据第二遍再计算。既然都要存储直接用 vector 也无可厚非。如果原题输入采用“压缩生成式”也就是给出一个种子和递推公式让程序自己生成每个 a_i那就可以用两次扫描来做到 O(1) 空间第一次扫描只为了求出 a_n 的值第二次扫描重新从头生成并累加答案。示例框架如下long long nextValue(long long x, long long A, long long B, long long C) { return (x * A B) % C 1; } // 第一次扫描求 a[n] long long x initValue; for (int i 1; i n; i) x nextValue(x, A, B, C); long long an x; // 第二次扫描边生成边累加 x initValue; long long prev an; long double ans 0; for (int i 1; i n; i) { ans 1.0L / max(prev, x); prev x; x nextValue(x, A, B, C); }这个框架不针对任何特定生成规则核心思想是把 a_i 的生成函数抽象出来。具体到某道题你需要把initValue和nextValue换成题目给定的表达式。4.3 生成式输入一种常见情况不少老题为了卡数据大小会设计生成式输入。常见套路是第一行给 n 以及三个整数 A、B、C然后 a_1 给定之后 a_i (a_{i-1} × A B) mod C 1。这类式子里的乘法可能超过 int 范围所以中间的变量必须用 long long。你只要把读入数组的逻辑替换成生成逻辑主循环完全不变。如果你已经掌握了上一节的框架换成什么规则都只是改一个函数的问题。有的同学会问为什么不直接用数组存下生成结果当然可以n 到 10^7 时 vector 也就 40MB一般能过。但如果 n 到 10^8 甚至更大内存就危险了这时候滚动/两遍扫描就成了必要。竞赛中学会这种“用生成规则换取空间”的思路能帮你应对很多压缩输入题。4.4 精度与溢出注意事项首先1.0 / max(pre, a[i])中 max 返回整数除以 1.0 隐式转换为浮点数没问题。但如果你用long double ans注意1.0是 double 型字面量最好写成1.0L否则会先按 double 精度计算再赋值给 long double。虽然本题差距不大但严谨一点是好的。其次如果你是按生成式算 a_i递推式里x * A可能达到 1e18 级别C 里 int 必炸一定用long long甚至可能需要__int128防范更大值的题目。如果题目给的是 1e9 范围内的数long long 足够。最后输出要求保留 6 位小数用fixed setprecision(6)。期望值的精度一般不需要太高因为每个概率都在 [0,1]n 在 1e6 时总和最多 1e6double 的 15 位有效数字仍然能保证小数点后好几位正确。不要因为担心精度而用高精度库没必要。5. 常见错误与排查清单5.1 边界写错把 a[0] 当 a[n]这是最典型的错误。数组从 1 开始存时a[0] 通常是 0如果你在 i1 时直接取 a[i-1]就会把第一题的“前一个选项数”当成 0于是计算 1/max(0, a[1]) 1/a[1]答案完全偏掉。正确写法是判断i 1时用a[n]。如果在循环前先把a[0] a[n]也可以让代码统一但要注意 n1 的特殊情况此时 a[0]a[1]公式变成 1/a[1]期望确实等于 1/a[1]因为唯一一道题的错位是“自己涂自己”正确概率当然就是 1/a[1]。很多人在 n1 数据上 WA 才发现边界不是小问题。5.2 公式记反min 和 max 的取舍前面说过正确的概率是 1/max。但有些人会想成“两个选项范围交集有 min 个概率应该是 min/某个数”最后写成 1/min。有一个保命检验法构造极端例子。比如前题只有 1 个选项当前题有 9 个选项两个正确答案相同的概率显然是 1/9而 1/max1/91/min1。看到 1/min 的结果超过 1 或者荒谬就知道公式错了。更严谨的记忆是概率 min / (u*v)而不是 min/(min^2)。这一步推导才是根。5.3 忽略独立均匀条件强行套公式如果某道题的正确答案分布不是均匀的或者前后题正确答案相关那么就不能用 1/max。判断依据是P(X_{i-1}X_i)Σ p_{i-1}(k) * p_i(k)只有当 p_{i-1}(k)1/u 且 p_i(k)1/v 时才能化简为 1/max。所以遇到变式题先检查随机分布假设是否一致。竞赛题里如果没提“等概率”三个字基本就在暗示你不能直接套这个公式。5.4 生成式输入处理不当有些同学看到 n 很大只读入前几个数字或者把生成公式里的取模顺序写错导致 a_i 跟预期不同。建议先把生成逻辑单独写成一个函数并用小样例打印前几项跟题目描述核对一遍再进入主循环。另外如果使用两次扫描第二次扫描时一定要从初始状态重新开始不能沿用第一次扫描后的变量否则计算的就是后一半数据答案自然错误。5.5 累加精度问题虽然 double 一般够用但如果你使用float精度就明显不足尤其是 n 达到 1e6 时float 的误差会积累到不可忽视。务必使用 double 或 long double。还有C 的printf(%lf)和cout的默认精度不同使用printf(%.6Lf)时要注意 long double 的格式说明符在 Windows 和 Linux 上可能不同建议直接cout搭配fixed setprecision(6)避免平台差异。6. 变体与延伸思考6.1 如果所有选项数相同假设每道题都有 m 个选项那么 E Σ 1/max(m,m) n/m。这个结论很漂亮也很好理解任意相邻两题的正确答案都是均匀地从 m 个选项中取相等的概率就是 1/m。如果 m 是 1那期望就是 n因为每道题只有一个选项无论怎么错位都必对如果 m 很大期望就趋近于 0因为不同题的正确答案很难撞在一起。这种“退化情形”经常出现在找规律题里。你可以先用 m1 和 m100 验证公式不会越界再代入一般的 a_i 数组。6.2 如果错位方向变化本题是“第 i 题答案填到第 i1 题”所以位置 i 的答案来自第 i-1 题。如果改成“第 i 题答案填到第 i-1 题”则位置 i 的答案来自第 i1 题概率变成 1/max(a_i, a_{i1})。对整个循环而言仍然是所有相邻 pair 各算一次最终答案不变因为环形上每对相邻题目被考虑的顺序不影响 sum max 的值。换句话说错位方向朝前还是朝后对环形期望没有影响。但如果是一条链而非环最后一题不填到第 1 题那边界项就要单独处理公式会复杂一些。6.3 如果选项概率不均匀更一般的情况第 i 题正确答案取选项 k 的概率是 p_i(k)不一定是 1/a_i。此时第 i 题答对概率为 Σ_k p_{i-1}(k) p_i(k)这就是两个概率分布的内积。如果分布来自同一个随机种子还可能涉及协方差结构的计算。遇到这种题不要再想 1/max 了老老实实从定义出发先写出分布再算内积。P1297 的均匀假设是一个特例但也正是这个特例让公式足够简洁适合用来教学。6.4 从这题抽出的通法期望题三步走做期望题我摸索出一个固定套路第一步把目标量拆成若干个指示变量之和第二步对每个指示变量写出它等于 1 的事件条件和涉及的随机变量第三步用随机变量的联合分布算这个事件的概率最后把所有概率加起来。很多所谓“难题”都只是每一步的计算变复杂但框架不变。P1297 把这三步都浓缩在一个非常小的例子里拆题数 - 找错位来源 - 算相等概率。把这个过程吃透以后遇到“期望”“随机排列”“匹配”字眼的题目你至少知道从哪里下手。我个人做完这题的体会是期望题的“难”往往不是计算难而是视角转换难。看到“错位”两个字第一反应可能是去模拟答题卡上的串位过程越想越乱但一旦把每个位置的来源用随机变量写出来答案自己就浮现了。后来我每遇到一道概率题都会先问自己这里到底有哪些随机变量每个得分事件的概率是多少其他相关性统统交给期望线性性处理。P1297 就是这样一瓶很好的“催化剂”希望你也动手枚举一遍、推导一遍、提交一遍把这种思路变成肌肉记忆。
