刷题群里有人甩了一道 P1654 OSU!标题乍一看像是音游相关点进去才发现是道期望 DP。这题我做的时候第一反应是模拟整个序列把所有连续 O 段长度取出来然后对每个段算 L³ 的期望写到一半感觉复杂度直接爆炸。后来老老实实推式子才意识到这题真正考的不是枚举而是期望的线性性和状态设计的维度选择。洛谷上评级是蓝我觉得这个评级挺中肯——它不考什么玄学优化也不考高难度数据结构但是每个递推式子里都藏着一个“为什么能这么写”的深层逻辑只要对期望 DP 的理解差一点就容易在E(l²)和E(l)²这种地方翻车。这篇文章我把完整推导、代码实现、以及我实际提交过程中踩过的坑都整理出来尤其是第三个大点里那个“答案为什么不能直接拿长度期望的三次方来算”的问题我当初在这里卡了快两个小时。如果你正在刷期望 DP 专题或者准备算法竞赛的初赛复赛这篇文章可以直接当题解用也能当思维训练材料。1. 从游戏规则到数学模型这道题到底在算什么东西1.1 先读懂 OSU 的判定规则OSU 这个名字来自一个点击节奏游戏玩家需要根据音乐节拍点击屏幕上的音符连续点击成功会累计 Combo连击数一旦 miss 连击就会中断。题目把这种机制抽象成了一个非常经典的伯努利序列模型有 n 个位置每个位置独立地以概率 p_i 产生一个“O”字符否则产生一个“X”字符然后你要计算整段序列的得分期望。这里的得分函数是最容易让人踩坑的地方。把任意一段连续的 O 看作一个整体比如一段长度为 L 的连续 O 段它的贡献是 L³而不是 L也不是 L²。也就是说一个长度为 2 的 O 段贡献 8 分长度为 3 的 O 段贡献 27 分两个长度为 2 的段贡献 16 分。为什么用三次方这是为了模拟音游里“连击越长、单次得分增量越大”的奖励机制——第 k 个连击音符的得分增量大约是 k² 级别所以累积到 L 时就是立方级别。题目既然定义了这样的得分函数我们的状态设计就必须围绕“连击段长度”本身来展开。读题时我建议你先把“段”这个概念想清楚。比如序列OOXOO它有两个连续 O 段长度分别是 2 和 2得分是 8 8 16而不是把整个序列看成一个长度 4 的段。这个区分对后续推导至关重要因为递推过程中我们每次只处理“当前这个位置是否是 O”而不是一次处理一整段。1.2 期望线性性是破题的第一把钥匙如果你尝试对所有可能的 O/X 序列做全枚举那是指数级别的状态直接不可行。这时候必须动用期望线性性若干随机变量之和的期望等于各自期望之和哪怕这些变量之间并不独立。这是整个题解最核心的一条原理也是“为什么明明前后概率相关却可以一格格地推下去”的解释。具体来说我们把总得分拆成 n 次增量每次考虑“如果当前位置 i 是 O那么相比前一格得分增加了多少”。这样原序列的期望得分就变成了[ E[\text{总得分}] \sum_{i1}^{n} E[\text{第 } i \text{ 个位置带来的增量}] ]这里的关键在于每个增量的期望只跟当前位置 i 和它之前的“连续 O 段长度”有关而之后的位置是什么完全不影响这一步的增量。也就是说我可以从左到右逐位扫描维护一个状态来刻画“最近一段连续 O 的长度”然后用它的期望来算下一步的增量期望。这个“线性拆分成增量”的思路可复用在很多得分函数较复杂的题目上比如得分函数是 2^L 或 L(L1)/2 的变种。我也要顺手提醒一点很多同学看到总分是三段落三次方第一反应是对“总连击长度”求期望再三方然后直接算 E[L³]这从数学上是完全错误的。期望算子不穿过非线性函数E[L³] 一般不等于 (E[L])³。正确方式是先把总得分按位置拆成增量再对增量求期望。1.3 明确目标量我们需要维护的并不是答案本身先想清楚最终答案是什么——是 E[总得分]也就是所有段贡献值之和的期望。按照上一节的拆法我们要在扫描到第 i 个字符时知道此时“若第 i 个字符是 O它会把当前正在累积的那段连续 O 的长度从多少变成多少”然后算出长度变化带来的得分增量。如果我们定义当前 i 位置之前不包含 i的连续 O 段长度为 l那么当第 i 个位置是 O 时l 会变成 l1得分增量就是 (l1)³ - l³ 3l² 3l 1。而当第 i 个位置是 X 时l 归零得分增量为 0。于是第 i 个位置带来的增量期望为[ p_i \times (3E[l^2] 3E[l] 1) ]看懂了这个式子就会发现我们真正需要维护的变量并不是“总得分期望”本身而是 l 的一阶矩 E[l] 和二阶矩 E[l²]。答案则放到另一个累加器里每次加上当前位置的增量期望。这里也自然地引出了下一节的递推状态设计让 E[l] 和 E[l²] 以各自的递推方式向下传递最后汇总进答案。想通这一点后整道题的框架就很清晰了问题不在于“期望怎么算”而在于“哪些随机变量的期望值得被追踪”。2. 状态设计是怎么想出来的一次连续段的自我更新2.1 用一个随机变量追踪连续的 O 段长度我们设随机变量 l_i 表示扫描完前 i 个字符后从第 i 个字符开始往前追溯得到的最长连续 O 段的长度。换句话说l_i 是以位置 i 结尾的连续 O 段的长度。如果第 i 个字符是 X那么 l_i 0。这个变量在相邻位置之间有非常清晰的递推关系。第 i1 个字符的情况取决于它本身是不是 O如果第 i1 个位置是 O那么以它结尾的连续 O 段长度就是在 l_i 的基础上加 1即 l_{i1} l_i 1。如果第 i1 个位置是 X那么 l_{i1} 0。写成随机变量就是[ l_{i1} \begin{cases} l_i 1, \text{概率 } p_{i1} \ 0, \text{概率 } 1 - p_{i1} \end{cases} ]这个递推本身非常简单但它的价值不在于形式而在于它允许我们对两边同时取期望。因为 l_i 本身分布未知我们不能只凭期望值重建整个分布但好在我们需要的只是 E[l_i]、E[l_i²] 这两个低阶矩。我们把递推关系分别平方和一次方后取期望就会得到一组闭合的递推方程。这里有一个很隐蔽的细节取期望时p_{i1} 乘以的是关于 l_i 的某个量的期望这个 l_i 来自上一轮因此只要上一轮的信息传下来这一轮就可以精确算出下一轮。你可能会有疑问题目给的概率是每个位置独立的为什么这里不需要考虑更早之前的历史原因在于 l_i 这个变量已经浓缩了“到 i 为止”的所有历史信息而伯努利过程的独立性保证了下一次的结果只依赖当前 l_i 和当前概率。换句话说l_i 是一个马尔可夫式的状态把分布压缩成了一个可递推的量——虽然它事实上丢失了部分分布信息但对于期望的线性结构来说保留到二阶矩已经足够。2.2 核心推导E[l] 与 E[l²] 的递推方程现在我们把上一节的递推式两边取期望。先看一阶矩[ E[l_{i1}] p_{i1} \cdot (E[l_i] 1) (1 - p_{i1}) \cdot 0 ]整理可得[ E[l_{i1}] p_{i1} \cdot (E[l_i] 1) ]这里特别要注意的是括号里用的是E[l_i] 1而不是E[l_i 1]其实两者一样但不能再化简成E[l_i] * p_{i1} 1因为加 1 的操作只在 O 发生时才执行X 发生时不执行。很多人在这一步把 1 单独拿出来乘 p其实对最终递推结果没区别因为 p*(E[l]1)p*E[l]p但为了保持思路严谨还是建议按条件期望的分支方式推导。再看二阶矩。我们把递推关系两边平方[ l_{i1}^2 \begin{cases} (l_i 1)^2 l_i^2 2l_i 1, \text{概率 } p_{i1} \ 0, \text{概率 } 1 - p_{i1} \end{cases} ]两边取期望[ E[l_{i1}^2] p_{i1} \cdot (E[l_i^2] 2E[l_i] 1) ]注意这里出现了 2E[l_i] 的交叉项这就是为什么我们必须同时维护一阶矩——只靠 E[l²] 自己无法闭合递推。反过来说如果题目把得分函数改成 L²那么我们就只需要维护 E[l²] 和 E[l] 这两项就够了如果改成 L 的一次方只需要一阶矩。这个“需要的矩的阶数”由得分函数的阶数决定而得分函数是三次方所以需要一阶和二阶矩答案增量用三阶展开时交叉项又需要一阶二阶矩整体是自洽的。有的题解会把答案也写进递推里但我不建议这样做因为在代码阅读和调试时把“累计答案”和“状态矩”混在一起很容易搞混。我的做法是用两个变量a和b分别表示 E[l] 和 E[l²]用一个变量ans累加总期望。每扫到一个位置就先利用当前a、b计算本次增量再更新a、b到下一位。这样整个代码结构非常清楚不容易错。2.3 为什么不能直接维护 E[l³]在刚看到题目时我的第一直觉是定义数组c[i]表示到第 i 位时的 E[l_i³]然后最后答案就是 c[n]。这个思路一开始看起来特别顺——毕竟得分函数就是三次方答案看起来就是 l 的三次方的期望。但推导之后会发现这个方向是死路原因有两点。第一个原因是l_i³的递推虽然可以写出来但它的更新又需要 E[l_i²] 和 E[l_i]于是必须同时维护三个数组更关键的是最终答案并不是 l_n³而是所有连续段贡献的总和——在一个序列中可能有多个连续 O 段只有最后一段的段长是 l_n前面那些段在遇到 X 时已经“结算”了它们的信息会丢失。如果只维护到当前位置的立方期望你事实上只会得到最后一段的期望而不是整串序列的累计得分期望。举个例子序列OOXOO最后一段长度为 2贡献是 8但前面那段长度为 2 的段已经因为 X 而结算过一次贡献也是 8总计是 16。如果只用l_5的立方来算只会得到 8漏掉了前面一段。因此答案不能简单等于某个“终止状态”的立方期望而要在每个位置“结算”增量。这也是 E[增量] 与 E[状态] 两种统计口径的核心区别。换句话说E[l²]和E[l]是用来帮助计算“增量”的辅助变量它们并不直接是答案的一部分但答案的每一笔增量都依赖它们。这个“状态矩”和“答案累计器”分离的设计在区间 DP 和期望 DP 里经常出现比如很多“可以有多次命中/奖励”的模型也是类似思路。3. 递推实现与代码细节三维状态如何压缩成三个变量3.1 逐步写出完整递推式我们设a为当前位比如 i结束时的 E[l]b为 E[l²]。当扫描到下一个位置 i1概率 p时更新一阶矩a_new p * (a 1)更新二阶矩b_new p * (b 2*a 1)得分增量期望ans p * (3*b 3*a 1)这里的三个式子有一个很漂亮的统一关系如果把“增量期望”里的系数和“二阶矩更新”里的交叉项系数对照一下会发现都来自(l1)^3 - l^3 3l^2 3l 1和(l1)^2 l^2 2l 1。这也是一种自检方式你在写代码时如果发现b的递推里系数和答案增量里的系数不一致那多半是推错了。我们用一个具体例子来检验递推式。假设 n1p_10.5。那么ans 初始为 0ab0。增量期望 0.5 * (30 30 1) 0.5。更新 a 0.5b 0.5。这个答案符合直觉一个长度为 1 的 O 段贡献 1出现概率 0.5所以期望 0.5。再看 n2 且两个位置概率都是 0.5。手算总共四种情况XX得分 0XO得分 1OX得分 1OO得分 8平均得分是 (0118)/4 2.5。用递推第一位后a0.5b0.5ans0.5第二位 p0.5增量 0.5 * (30.5 30.5 1) 0.5 * (1.51.51) 2.0ans 总 0.5 2.0 2.5和手算一致。用这种小规模穷举来验证递推式是写期望 DP 时最有效的自检手段没有之一。3.2 三种实现形态朴素数组、滚动变量与分数模拟最常见的实现是直接用三个变量滚动因为你只需要上一个位置的信息。伪代码如下double a 0, b 0, ans 0; for (int i 1; i n; i) { double p; cin p; ans p * (3 * b 3 * a 1); double nb p * (b 2 * a 1); a p * (a 1); b nb; } printf(%.1f\n, ans);注意这里的更新顺序b的新值依赖a的旧值所以要么用临时变量暂存nb要么先更新b再更新a。我上面是先算nb再更新a最后把nb赋给b这样能避免用更新后的a去算交叉项。这是很多新手写这个题最容易产生隐蔽 bug 的地方因为肉眼看上去只是两行顺序之差但结果完全不对。另外有些题解会额外开数组存每一步的a、b这其实没必要因为期望 DP 的递推只依赖上一步。不过如果你是想输出中间过程做调试那开数组也无妨。还有一个变种如果概率是用百分数整数给出的比如p input_int / 100.0一定要先转成 double 再参与乘法否则整数除法直接会截断成 0整个递推就废了。如果你喜欢用 Python 刷题可以参考这个写法n int(input()) a b ans 0.0 for _ in range(n): p float(input()) ans p * (3 * b 3 * a 1) nb p * (b 2 * a 1) a p * (a 1) b nb print(f{ans:.1f})这里我特别说明一下为什么答案用浮点数而不是分数。虽然从数学上我们可以把所有概率转化为分数进行精确计算但题目的数据范围通常 n 在 10^5 量级以上浮点数的双精度完全足够容纳误差而且每次递推都是乘小于等于 1 的概率误差只会逐渐衰减而不是放大。你不需要使用分数类来“求稳”那会白白增加常数和代码复杂度。3.3 复杂度分析与稳定性自检这个题的时间复杂度是 O(n)空间复杂度 O(1)这是它的天然优势。你可能会想为什么看似复杂的得分规则能压缩到如此简单原因在于我们把三维的随机演化过程长度、平方、答案压缩成了低维矩的递推而伯努利序列每个位置只有两种结果所以每次更新都只需要常数次运算。我建议在提交前做几组边界自检n1p0 或 p1答案应该分别是 0 和 1。所有 p1此时序列一定全 O唯一连续段长度 n答案应为 n³。所有 p0答案应为 0。交替概率 0/1 组合可以通过穷举小 n 验证。对于“所有 p1”的情况推导一下a 每轮加 1b 每轮从 (k)² 变成 (k1)²ans 每轮增加 3k²3k1正好从 0 加到 n³。如果代码输出不是 n³那递推式中大概率有系数错误。这种“特殊概率退化到确定性模型”的验证方式也是我调试期望 DP 时最常用的手段。4. 常见问题与排查技巧实录我踩过的坑与库里的解法对照4.1 老生常谈却总有人犯的把 E[l²] 当成 E[l]²这是这道题评论区里出现频率最高的错误也是我最初卡了两小时的地方。很多人在推答案增量时会把式子写成[ p \times (3(E[l])^2 3E[l] 1) ]也就是把b替换成a*a。表面上看这好像只是在“用期望长度代替随机长度”但数学上这是完全错误的因为对于非退化随机变量几乎总有[ E[l^2] \neq (E[l])^2 ]举个最简单的例子l 以 0.5 概率取 00.5 概率取 2那么 E[l]1E[l²]2而 (E[l])²1两个值差了整整一倍。在连续 O 段的演化过程中l 的分布通常非常不均匀当概率接近 1 时它接近确定值概率较小时它大量取 0所以直接用 a² 来代替 b 会导致答案系统性偏差。这个问题的本质是混淆了“随机变量函数的期望”和“随机变量期望的函数”在概率论里这两个概念差了十万八千里。如果你怀疑自己犯了这类错误最快的检验方式是打印每一步的 a 和 b看它们是否满足b a*a因为方差非负。如果出现b a*a那一定不是四舍五入的问题而是更新逻辑错了。我在调试时发现这个不等式特别好用。4.2 答案增量到底加在什么时候先结算还是先更新代码里一个常见争议是ans 的累加应该用“当前位置的旧状态”还是“更新后的状态”。我们回到定义正确答案是ans 必须使用“处理当前位之前的 a 和 b”因为第 i 个字符带来的长度增量是从 l_{i-1} 变成 l_i 的过程得分增量对应的是从旧状态切换到新状态时的差值。我们用旧状态计算期望增量然后才更新状态。如果反过来先更新 a、b 再用新状态去算增量那实际上你会把“下一步”的增量提前累加导致答案偏大。在概率固定且序列均匀时可能看不出来但一旦概率非均匀错误会非常明显。这里我建议在代码注释里明确标注结算和更新的顺序防止自己或者看代码的人误改顺序。有些题解会把 ans 的更新放到循环体最前面把状态更新放到后面这是对的因为循环体开始时a、b正好是“上一次迭代结束”的状态也就是当前位的旧状态。可以用这个约定来统一所有题解的口径减少理解成本。4.3 多位小数的输出陷阱与读入稳定性题目输出通常要求保留 1 位小数即%.1f。这时如果你用float而不是double在大数据量下可能会累积几分的误差导致最后一位小数错误。我的建议是统一用double因为 O(n) 量级下的 1e5 次递推虽然误差增长很慢但 float 的有效精度只有大约 7 位十进制而中间那个3*b的值可能达到 1e10 量级比如 n 很大且 p 接近 1 时float 直接丢精度。另外如果题目给的概率是整数百分比比如85表示 0.85读入后一定要先转 double 再除以 100不要写p (double)(x / 100)那样会先做整数除法再转 double结果直接变 0。我见过不止一个人在这个换行上卡死而且这种 bug 特别隐蔽因为 n 较小的时候输出看起来“差不多对”n 一大就面目全非。还有一点想提的是编译选项。C 里如果你用了pow(l1, 3)这类函数去算增量性能和精度都不如直接用整数乘法展开。虽然这题 n 不大但养成直接展开的习惯能避免很多符号类型问题。4.4 对拍验证用穷举法建立信心最后我非常推荐你在本地写一个暴力穷举器来做小数据对拍。所谓穷举器就是枚举长度为 n 的序列的所有 2^n 种情况对每种情况按题意算得分并乘以对应概率然后求和。在 n 10 的范围内这个穷举完全可行可以用来验证递推代码的正确性。伪代码思路如下double brute(int n, vectordouble p) { double total 0; for (int mask 0; mask (1 n); mask) { double prob 1.0; for (int i 0; i n; i) { int bit (mask i) 1; prob * bit ? p[i] : (1 - p[i]); } int len 0; double score 0; for (int i 0; i n; i) { if (i n ((mask i) 1)) { len; } else { score 1.0 * len * len * len; len 0; } } total prob * score; } return total; }如果 n10 而递推代码与穷举结果在1e-9误差内一致那你基本可以放心提交。这个对拍过程只需要几分钟却能省下大量罚时。我自己每次写期望 DP都会顺手写一个这样的验证器——它不单是验证实现也是在验证我对题意的理解有没有偏差。5. 从 P1654 延伸开期望、幂次与场景变形的一整套策略5.1 改成二次方或一次方状态维度如何缩放不少 OJ 上存在 OSU! 系列的姊妹题比如得分函数是连续段长度的平方或者干脆就是长度本身。这类题的核心技巧完全一致唯一的区别是你所需要维护的矩的阶数不同得分是 L答案增量 L1 - L 1你只需要维护 aans 累加p * 1。实际上这时答案就是所有位置概率之和甚至不需要 DP。得分是 L²答案增量 (L1)² - L² 2L1你需要维护 a 和 bans 累加p * (2a1)。这里就体现出了为什么维护二阶矩是必要的。得分是 L³就是本题需要维护 a、bans 累加p * (3b 3a 1)。如果要计算 L 的更高次方比如 L⁴你需要维护到三阶矩因为 (L1)⁴ - L⁴ 的展开式里会出现 L³ 项。你可以从这个角度归纳出一个通用框架得分函数的幂次决定了你要维护到几阶矩以及答案增量里会出现哪些低阶矩项。遇到任意多项式得分甚至指数型得分你都可以通过同样的“增量分解”思路来推导。5.2 随机概率与区间分段从 OSU 到更复杂的期望模型有些扩展问题不再要求每个位置独立同分布而是概率在区间内以某种规律变化比如 p_i i/n 或 p_i (i % 2 0) ? 0.8 : 0.2。这种情况下递推框架仍然完全适用因为每个位置只用当轮的 p_i不需要历史信息。这比很多需要维护前缀和的期望题还要简单——但它也提醒我们一个题看起来复杂未必真的很复杂关键要看状态是否满足马尔可夫式压缩。另一些变体把“连续 O 段贡献三次方”改成“每个长度为 k 的完整段额外触发一次奖励”这时你就不能单纯用逐位增量来结算了而需要在段结束时额外处理。这种时候往往要引入“段计数”变量或者把状态设计成“最后一段是否结束”的二维状态复杂度也会随之上升。但从 P1654 学到的核心思想——用低阶矩追踪连续段、用增量来累加非独立随机变量——在这些更复杂的模型里依然有效。5.3 把这道题当作面试或教学题的潜力我后来复盘时发现P1654 其实非常适合作为期望 DP 的教学素材因为它把三个关键概念浓缩在一个短小的代码里条件期望的分支写法、矩递推的闭合性、以及答案累计器与状态变量的解耦。如果你在给别人讲这道题我最大的建议是不要上来就给代码而是先让学生手算 n2 的例子自己推出增量公式这样他们对E[l²]和E[l]²的区别会印象极其深刻。刷题的时候我们往往追求“多而快”但这道题值得“慢下来”。我甚至建议你把代码注释写详细一点把每一行对应的数学含义都标出来比如// a: E[连续段长度] // b: E[连续段长度的平方] // ans: 累计得分期望所有增量之和标好之后后面再遇到期望 DP 时反复看这份代码很多思路都会复用。我自己就是从这道题开始建立起了“先推数学式、再写代码”的习惯之后做其它期望题的速度明显提升。说到底P1654 并不难难的是你把每一步的“为什么”想透。期望 DP 这类的题一旦你能把随机过程的低阶矩递推写清楚代码就只是几行而已。真正的功夫全在动手推式子之前。希望这份复盘能帮你少走一点我当初走过的弯路。
期望DP经典题P1654 OSU!：从连续段长度到低阶矩递推全解析
刷题群里有人甩了一道 P1654 OSU!标题乍一看像是音游相关点进去才发现是道期望 DP。这题我做的时候第一反应是模拟整个序列把所有连续 O 段长度取出来然后对每个段算 L³ 的期望写到一半感觉复杂度直接爆炸。后来老老实实推式子才意识到这题真正考的不是枚举而是期望的线性性和状态设计的维度选择。洛谷上评级是蓝我觉得这个评级挺中肯——它不考什么玄学优化也不考高难度数据结构但是每个递推式子里都藏着一个“为什么能这么写”的深层逻辑只要对期望 DP 的理解差一点就容易在E(l²)和E(l)²这种地方翻车。这篇文章我把完整推导、代码实现、以及我实际提交过程中踩过的坑都整理出来尤其是第三个大点里那个“答案为什么不能直接拿长度期望的三次方来算”的问题我当初在这里卡了快两个小时。如果你正在刷期望 DP 专题或者准备算法竞赛的初赛复赛这篇文章可以直接当题解用也能当思维训练材料。1. 从游戏规则到数学模型这道题到底在算什么东西1.1 先读懂 OSU 的判定规则OSU 这个名字来自一个点击节奏游戏玩家需要根据音乐节拍点击屏幕上的音符连续点击成功会累计 Combo连击数一旦 miss 连击就会中断。题目把这种机制抽象成了一个非常经典的伯努利序列模型有 n 个位置每个位置独立地以概率 p_i 产生一个“O”字符否则产生一个“X”字符然后你要计算整段序列的得分期望。这里的得分函数是最容易让人踩坑的地方。把任意一段连续的 O 看作一个整体比如一段长度为 L 的连续 O 段它的贡献是 L³而不是 L也不是 L²。也就是说一个长度为 2 的 O 段贡献 8 分长度为 3 的 O 段贡献 27 分两个长度为 2 的段贡献 16 分。为什么用三次方这是为了模拟音游里“连击越长、单次得分增量越大”的奖励机制——第 k 个连击音符的得分增量大约是 k² 级别所以累积到 L 时就是立方级别。题目既然定义了这样的得分函数我们的状态设计就必须围绕“连击段长度”本身来展开。读题时我建议你先把“段”这个概念想清楚。比如序列OOXOO它有两个连续 O 段长度分别是 2 和 2得分是 8 8 16而不是把整个序列看成一个长度 4 的段。这个区分对后续推导至关重要因为递推过程中我们每次只处理“当前这个位置是否是 O”而不是一次处理一整段。1.2 期望线性性是破题的第一把钥匙如果你尝试对所有可能的 O/X 序列做全枚举那是指数级别的状态直接不可行。这时候必须动用期望线性性若干随机变量之和的期望等于各自期望之和哪怕这些变量之间并不独立。这是整个题解最核心的一条原理也是“为什么明明前后概率相关却可以一格格地推下去”的解释。具体来说我们把总得分拆成 n 次增量每次考虑“如果当前位置 i 是 O那么相比前一格得分增加了多少”。这样原序列的期望得分就变成了[ E[\text{总得分}] \sum_{i1}^{n} E[\text{第 } i \text{ 个位置带来的增量}] ]这里的关键在于每个增量的期望只跟当前位置 i 和它之前的“连续 O 段长度”有关而之后的位置是什么完全不影响这一步的增量。也就是说我可以从左到右逐位扫描维护一个状态来刻画“最近一段连续 O 的长度”然后用它的期望来算下一步的增量期望。这个“线性拆分成增量”的思路可复用在很多得分函数较复杂的题目上比如得分函数是 2^L 或 L(L1)/2 的变种。我也要顺手提醒一点很多同学看到总分是三段落三次方第一反应是对“总连击长度”求期望再三方然后直接算 E[L³]这从数学上是完全错误的。期望算子不穿过非线性函数E[L³] 一般不等于 (E[L])³。正确方式是先把总得分按位置拆成增量再对增量求期望。1.3 明确目标量我们需要维护的并不是答案本身先想清楚最终答案是什么——是 E[总得分]也就是所有段贡献值之和的期望。按照上一节的拆法我们要在扫描到第 i 个字符时知道此时“若第 i 个字符是 O它会把当前正在累积的那段连续 O 的长度从多少变成多少”然后算出长度变化带来的得分增量。如果我们定义当前 i 位置之前不包含 i的连续 O 段长度为 l那么当第 i 个位置是 O 时l 会变成 l1得分增量就是 (l1)³ - l³ 3l² 3l 1。而当第 i 个位置是 X 时l 归零得分增量为 0。于是第 i 个位置带来的增量期望为[ p_i \times (3E[l^2] 3E[l] 1) ]看懂了这个式子就会发现我们真正需要维护的变量并不是“总得分期望”本身而是 l 的一阶矩 E[l] 和二阶矩 E[l²]。答案则放到另一个累加器里每次加上当前位置的增量期望。这里也自然地引出了下一节的递推状态设计让 E[l] 和 E[l²] 以各自的递推方式向下传递最后汇总进答案。想通这一点后整道题的框架就很清晰了问题不在于“期望怎么算”而在于“哪些随机变量的期望值得被追踪”。2. 状态设计是怎么想出来的一次连续段的自我更新2.1 用一个随机变量追踪连续的 O 段长度我们设随机变量 l_i 表示扫描完前 i 个字符后从第 i 个字符开始往前追溯得到的最长连续 O 段的长度。换句话说l_i 是以位置 i 结尾的连续 O 段的长度。如果第 i 个字符是 X那么 l_i 0。这个变量在相邻位置之间有非常清晰的递推关系。第 i1 个字符的情况取决于它本身是不是 O如果第 i1 个位置是 O那么以它结尾的连续 O 段长度就是在 l_i 的基础上加 1即 l_{i1} l_i 1。如果第 i1 个位置是 X那么 l_{i1} 0。写成随机变量就是[ l_{i1} \begin{cases} l_i 1, \text{概率 } p_{i1} \ 0, \text{概率 } 1 - p_{i1} \end{cases} ]这个递推本身非常简单但它的价值不在于形式而在于它允许我们对两边同时取期望。因为 l_i 本身分布未知我们不能只凭期望值重建整个分布但好在我们需要的只是 E[l_i]、E[l_i²] 这两个低阶矩。我们把递推关系分别平方和一次方后取期望就会得到一组闭合的递推方程。这里有一个很隐蔽的细节取期望时p_{i1} 乘以的是关于 l_i 的某个量的期望这个 l_i 来自上一轮因此只要上一轮的信息传下来这一轮就可以精确算出下一轮。你可能会有疑问题目给的概率是每个位置独立的为什么这里不需要考虑更早之前的历史原因在于 l_i 这个变量已经浓缩了“到 i 为止”的所有历史信息而伯努利过程的独立性保证了下一次的结果只依赖当前 l_i 和当前概率。换句话说l_i 是一个马尔可夫式的状态把分布压缩成了一个可递推的量——虽然它事实上丢失了部分分布信息但对于期望的线性结构来说保留到二阶矩已经足够。2.2 核心推导E[l] 与 E[l²] 的递推方程现在我们把上一节的递推式两边取期望。先看一阶矩[ E[l_{i1}] p_{i1} \cdot (E[l_i] 1) (1 - p_{i1}) \cdot 0 ]整理可得[ E[l_{i1}] p_{i1} \cdot (E[l_i] 1) ]这里特别要注意的是括号里用的是E[l_i] 1而不是E[l_i 1]其实两者一样但不能再化简成E[l_i] * p_{i1} 1因为加 1 的操作只在 O 发生时才执行X 发生时不执行。很多人在这一步把 1 单独拿出来乘 p其实对最终递推结果没区别因为 p*(E[l]1)p*E[l]p但为了保持思路严谨还是建议按条件期望的分支方式推导。再看二阶矩。我们把递推关系两边平方[ l_{i1}^2 \begin{cases} (l_i 1)^2 l_i^2 2l_i 1, \text{概率 } p_{i1} \ 0, \text{概率 } 1 - p_{i1} \end{cases} ]两边取期望[ E[l_{i1}^2] p_{i1} \cdot (E[l_i^2] 2E[l_i] 1) ]注意这里出现了 2E[l_i] 的交叉项这就是为什么我们必须同时维护一阶矩——只靠 E[l²] 自己无法闭合递推。反过来说如果题目把得分函数改成 L²那么我们就只需要维护 E[l²] 和 E[l] 这两项就够了如果改成 L 的一次方只需要一阶矩。这个“需要的矩的阶数”由得分函数的阶数决定而得分函数是三次方所以需要一阶和二阶矩答案增量用三阶展开时交叉项又需要一阶二阶矩整体是自洽的。有的题解会把答案也写进递推里但我不建议这样做因为在代码阅读和调试时把“累计答案”和“状态矩”混在一起很容易搞混。我的做法是用两个变量a和b分别表示 E[l] 和 E[l²]用一个变量ans累加总期望。每扫到一个位置就先利用当前a、b计算本次增量再更新a、b到下一位。这样整个代码结构非常清楚不容易错。2.3 为什么不能直接维护 E[l³]在刚看到题目时我的第一直觉是定义数组c[i]表示到第 i 位时的 E[l_i³]然后最后答案就是 c[n]。这个思路一开始看起来特别顺——毕竟得分函数就是三次方答案看起来就是 l 的三次方的期望。但推导之后会发现这个方向是死路原因有两点。第一个原因是l_i³的递推虽然可以写出来但它的更新又需要 E[l_i²] 和 E[l_i]于是必须同时维护三个数组更关键的是最终答案并不是 l_n³而是所有连续段贡献的总和——在一个序列中可能有多个连续 O 段只有最后一段的段长是 l_n前面那些段在遇到 X 时已经“结算”了它们的信息会丢失。如果只维护到当前位置的立方期望你事实上只会得到最后一段的期望而不是整串序列的累计得分期望。举个例子序列OOXOO最后一段长度为 2贡献是 8但前面那段长度为 2 的段已经因为 X 而结算过一次贡献也是 8总计是 16。如果只用l_5的立方来算只会得到 8漏掉了前面一段。因此答案不能简单等于某个“终止状态”的立方期望而要在每个位置“结算”增量。这也是 E[增量] 与 E[状态] 两种统计口径的核心区别。换句话说E[l²]和E[l]是用来帮助计算“增量”的辅助变量它们并不直接是答案的一部分但答案的每一笔增量都依赖它们。这个“状态矩”和“答案累计器”分离的设计在区间 DP 和期望 DP 里经常出现比如很多“可以有多次命中/奖励”的模型也是类似思路。3. 递推实现与代码细节三维状态如何压缩成三个变量3.1 逐步写出完整递推式我们设a为当前位比如 i结束时的 E[l]b为 E[l²]。当扫描到下一个位置 i1概率 p时更新一阶矩a_new p * (a 1)更新二阶矩b_new p * (b 2*a 1)得分增量期望ans p * (3*b 3*a 1)这里的三个式子有一个很漂亮的统一关系如果把“增量期望”里的系数和“二阶矩更新”里的交叉项系数对照一下会发现都来自(l1)^3 - l^3 3l^2 3l 1和(l1)^2 l^2 2l 1。这也是一种自检方式你在写代码时如果发现b的递推里系数和答案增量里的系数不一致那多半是推错了。我们用一个具体例子来检验递推式。假设 n1p_10.5。那么ans 初始为 0ab0。增量期望 0.5 * (30 30 1) 0.5。更新 a 0.5b 0.5。这个答案符合直觉一个长度为 1 的 O 段贡献 1出现概率 0.5所以期望 0.5。再看 n2 且两个位置概率都是 0.5。手算总共四种情况XX得分 0XO得分 1OX得分 1OO得分 8平均得分是 (0118)/4 2.5。用递推第一位后a0.5b0.5ans0.5第二位 p0.5增量 0.5 * (30.5 30.5 1) 0.5 * (1.51.51) 2.0ans 总 0.5 2.0 2.5和手算一致。用这种小规模穷举来验证递推式是写期望 DP 时最有效的自检手段没有之一。3.2 三种实现形态朴素数组、滚动变量与分数模拟最常见的实现是直接用三个变量滚动因为你只需要上一个位置的信息。伪代码如下double a 0, b 0, ans 0; for (int i 1; i n; i) { double p; cin p; ans p * (3 * b 3 * a 1); double nb p * (b 2 * a 1); a p * (a 1); b nb; } printf(%.1f\n, ans);注意这里的更新顺序b的新值依赖a的旧值所以要么用临时变量暂存nb要么先更新b再更新a。我上面是先算nb再更新a最后把nb赋给b这样能避免用更新后的a去算交叉项。这是很多新手写这个题最容易产生隐蔽 bug 的地方因为肉眼看上去只是两行顺序之差但结果完全不对。另外有些题解会额外开数组存每一步的a、b这其实没必要因为期望 DP 的递推只依赖上一步。不过如果你是想输出中间过程做调试那开数组也无妨。还有一个变种如果概率是用百分数整数给出的比如p input_int / 100.0一定要先转成 double 再参与乘法否则整数除法直接会截断成 0整个递推就废了。如果你喜欢用 Python 刷题可以参考这个写法n int(input()) a b ans 0.0 for _ in range(n): p float(input()) ans p * (3 * b 3 * a 1) nb p * (b 2 * a 1) a p * (a 1) b nb print(f{ans:.1f})这里我特别说明一下为什么答案用浮点数而不是分数。虽然从数学上我们可以把所有概率转化为分数进行精确计算但题目的数据范围通常 n 在 10^5 量级以上浮点数的双精度完全足够容纳误差而且每次递推都是乘小于等于 1 的概率误差只会逐渐衰减而不是放大。你不需要使用分数类来“求稳”那会白白增加常数和代码复杂度。3.3 复杂度分析与稳定性自检这个题的时间复杂度是 O(n)空间复杂度 O(1)这是它的天然优势。你可能会想为什么看似复杂的得分规则能压缩到如此简单原因在于我们把三维的随机演化过程长度、平方、答案压缩成了低维矩的递推而伯努利序列每个位置只有两种结果所以每次更新都只需要常数次运算。我建议在提交前做几组边界自检n1p0 或 p1答案应该分别是 0 和 1。所有 p1此时序列一定全 O唯一连续段长度 n答案应为 n³。所有 p0答案应为 0。交替概率 0/1 组合可以通过穷举小 n 验证。对于“所有 p1”的情况推导一下a 每轮加 1b 每轮从 (k)² 变成 (k1)²ans 每轮增加 3k²3k1正好从 0 加到 n³。如果代码输出不是 n³那递推式中大概率有系数错误。这种“特殊概率退化到确定性模型”的验证方式也是我调试期望 DP 时最常用的手段。4. 常见问题与排查技巧实录我踩过的坑与库里的解法对照4.1 老生常谈却总有人犯的把 E[l²] 当成 E[l]²这是这道题评论区里出现频率最高的错误也是我最初卡了两小时的地方。很多人在推答案增量时会把式子写成[ p \times (3(E[l])^2 3E[l] 1) ]也就是把b替换成a*a。表面上看这好像只是在“用期望长度代替随机长度”但数学上这是完全错误的因为对于非退化随机变量几乎总有[ E[l^2] \neq (E[l])^2 ]举个最简单的例子l 以 0.5 概率取 00.5 概率取 2那么 E[l]1E[l²]2而 (E[l])²1两个值差了整整一倍。在连续 O 段的演化过程中l 的分布通常非常不均匀当概率接近 1 时它接近确定值概率较小时它大量取 0所以直接用 a² 来代替 b 会导致答案系统性偏差。这个问题的本质是混淆了“随机变量函数的期望”和“随机变量期望的函数”在概率论里这两个概念差了十万八千里。如果你怀疑自己犯了这类错误最快的检验方式是打印每一步的 a 和 b看它们是否满足b a*a因为方差非负。如果出现b a*a那一定不是四舍五入的问题而是更新逻辑错了。我在调试时发现这个不等式特别好用。4.2 答案增量到底加在什么时候先结算还是先更新代码里一个常见争议是ans 的累加应该用“当前位置的旧状态”还是“更新后的状态”。我们回到定义正确答案是ans 必须使用“处理当前位之前的 a 和 b”因为第 i 个字符带来的长度增量是从 l_{i-1} 变成 l_i 的过程得分增量对应的是从旧状态切换到新状态时的差值。我们用旧状态计算期望增量然后才更新状态。如果反过来先更新 a、b 再用新状态去算增量那实际上你会把“下一步”的增量提前累加导致答案偏大。在概率固定且序列均匀时可能看不出来但一旦概率非均匀错误会非常明显。这里我建议在代码注释里明确标注结算和更新的顺序防止自己或者看代码的人误改顺序。有些题解会把 ans 的更新放到循环体最前面把状态更新放到后面这是对的因为循环体开始时a、b正好是“上一次迭代结束”的状态也就是当前位的旧状态。可以用这个约定来统一所有题解的口径减少理解成本。4.3 多位小数的输出陷阱与读入稳定性题目输出通常要求保留 1 位小数即%.1f。这时如果你用float而不是double在大数据量下可能会累积几分的误差导致最后一位小数错误。我的建议是统一用double因为 O(n) 量级下的 1e5 次递推虽然误差增长很慢但 float 的有效精度只有大约 7 位十进制而中间那个3*b的值可能达到 1e10 量级比如 n 很大且 p 接近 1 时float 直接丢精度。另外如果题目给的概率是整数百分比比如85表示 0.85读入后一定要先转 double 再除以 100不要写p (double)(x / 100)那样会先做整数除法再转 double结果直接变 0。我见过不止一个人在这个换行上卡死而且这种 bug 特别隐蔽因为 n 较小的时候输出看起来“差不多对”n 一大就面目全非。还有一点想提的是编译选项。C 里如果你用了pow(l1, 3)这类函数去算增量性能和精度都不如直接用整数乘法展开。虽然这题 n 不大但养成直接展开的习惯能避免很多符号类型问题。4.4 对拍验证用穷举法建立信心最后我非常推荐你在本地写一个暴力穷举器来做小数据对拍。所谓穷举器就是枚举长度为 n 的序列的所有 2^n 种情况对每种情况按题意算得分并乘以对应概率然后求和。在 n 10 的范围内这个穷举完全可行可以用来验证递推代码的正确性。伪代码思路如下double brute(int n, vectordouble p) { double total 0; for (int mask 0; mask (1 n); mask) { double prob 1.0; for (int i 0; i n; i) { int bit (mask i) 1; prob * bit ? p[i] : (1 - p[i]); } int len 0; double score 0; for (int i 0; i n; i) { if (i n ((mask i) 1)) { len; } else { score 1.0 * len * len * len; len 0; } } total prob * score; } return total; }如果 n10 而递推代码与穷举结果在1e-9误差内一致那你基本可以放心提交。这个对拍过程只需要几分钟却能省下大量罚时。我自己每次写期望 DP都会顺手写一个这样的验证器——它不单是验证实现也是在验证我对题意的理解有没有偏差。5. 从 P1654 延伸开期望、幂次与场景变形的一整套策略5.1 改成二次方或一次方状态维度如何缩放不少 OJ 上存在 OSU! 系列的姊妹题比如得分函数是连续段长度的平方或者干脆就是长度本身。这类题的核心技巧完全一致唯一的区别是你所需要维护的矩的阶数不同得分是 L答案增量 L1 - L 1你只需要维护 aans 累加p * 1。实际上这时答案就是所有位置概率之和甚至不需要 DP。得分是 L²答案增量 (L1)² - L² 2L1你需要维护 a 和 bans 累加p * (2a1)。这里就体现出了为什么维护二阶矩是必要的。得分是 L³就是本题需要维护 a、bans 累加p * (3b 3a 1)。如果要计算 L 的更高次方比如 L⁴你需要维护到三阶矩因为 (L1)⁴ - L⁴ 的展开式里会出现 L³ 项。你可以从这个角度归纳出一个通用框架得分函数的幂次决定了你要维护到几阶矩以及答案增量里会出现哪些低阶矩项。遇到任意多项式得分甚至指数型得分你都可以通过同样的“增量分解”思路来推导。5.2 随机概率与区间分段从 OSU 到更复杂的期望模型有些扩展问题不再要求每个位置独立同分布而是概率在区间内以某种规律变化比如 p_i i/n 或 p_i (i % 2 0) ? 0.8 : 0.2。这种情况下递推框架仍然完全适用因为每个位置只用当轮的 p_i不需要历史信息。这比很多需要维护前缀和的期望题还要简单——但它也提醒我们一个题看起来复杂未必真的很复杂关键要看状态是否满足马尔可夫式压缩。另一些变体把“连续 O 段贡献三次方”改成“每个长度为 k 的完整段额外触发一次奖励”这时你就不能单纯用逐位增量来结算了而需要在段结束时额外处理。这种时候往往要引入“段计数”变量或者把状态设计成“最后一段是否结束”的二维状态复杂度也会随之上升。但从 P1654 学到的核心思想——用低阶矩追踪连续段、用增量来累加非独立随机变量——在这些更复杂的模型里依然有效。5.3 把这道题当作面试或教学题的潜力我后来复盘时发现P1654 其实非常适合作为期望 DP 的教学素材因为它把三个关键概念浓缩在一个短小的代码里条件期望的分支写法、矩递推的闭合性、以及答案累计器与状态变量的解耦。如果你在给别人讲这道题我最大的建议是不要上来就给代码而是先让学生手算 n2 的例子自己推出增量公式这样他们对E[l²]和E[l]²的区别会印象极其深刻。刷题的时候我们往往追求“多而快”但这道题值得“慢下来”。我甚至建议你把代码注释写详细一点把每一行对应的数学含义都标出来比如// a: E[连续段长度] // b: E[连续段长度的平方] // ans: 累计得分期望所有增量之和标好之后后面再遇到期望 DP 时反复看这份代码很多思路都会复用。我自己就是从这道题开始建立起了“先推数学式、再写代码”的习惯之后做其它期望题的速度明显提升。说到底P1654 并不难难的是你把每一步的“为什么”想透。期望 DP 这类的题一旦你能把随机过程的低阶矩递推写清楚代码就只是几行而已。真正的功夫全在动手推式子之前。希望这份复盘能帮你少走一点我当初走过的弯路。
