本文剖析CF1067D「环上带随机停留的期望奖励更大化」的矩阵幂+凸包优化双路核心解法：给定n节点双向无向环，每节点带停留奖励a_u，T步内可每步停得a_u，或花一步随机等概率跳相邻节点得0奖励，初始节点任选求更大累计期望，剩余f步的更大期望序列具凸性，倍增时用凸包筛选更优转移候选，对大规模T步采用快速幂加速，压缩冗余计算。
作为Codeforces Div.1 的第4题（原题Div.2是F题），CF1067D Randomizer on Ring 是一道将数学期望建模、矩阵快速幂优化线性递推、环上序列的凸包维护求线性函数极值三个经典竞赛知识点巧妙融合的综合性难题——既考察对动态规划方程构造的敏感度，又对细节处理（比如环的处理顺序、凸包更新逻辑）有较高要求，今天我们就一步步拆解这道题的思路。
先读透题：把“随机游走环”的迷雾拨开原文（简化核心版）
给定一个长度为n的有向环（编号1~n，点i指向i+1，点n指向1），每个点i有三个参数：
- $a_i$：首次到达点i时获得的固定奖励；
- $p_i \in (0,1)$：到达点i后，停留一步的概率；
- $r_i \in (0,1)$：停留/移动到点i后，触发游戏结束的概率（触发后直接停止，不再获得后续奖励）。
注意：
- 停留一步时,仍算作“已到达过点i”，不会再获得$a_i$，但会再次有$r_i$的概率结束游戏；
- 你可以自由选择起点，求从更优起点出发的期望总奖励更大值。
关键转化（之一步就决定了解法方向）
观察触发结束的条件：每一步在某个点j时，都有$r_j$的概率立即停止，我们可以把这个“即时停止”转化为提前完成一次“连续存活链”的期望——因为每一步在j点是否存活独立，我们可以把游戏流程拆成“只在连续存活的时刻移动/停留”，触发结束就视为“这条存活链走到了尽头”。
这样转化后,每一步的决策（不管是停还是走）都默认存活，存活概率可以提前归一化到决策概率里：
- 定义有效停留概率：$q_i = \frac{p_i(1-r_i)}{1-p_i r_i}$（停留的同时存活，归一化掉“停留并结束”的死路）；
- 定义有效移动概率：$s_i = \frac{(1-p_i)(1-r_i)}{1-p_i r_i}$（移动的同时存活，同样归一化）；
- 显然,$q_i + s_i = 1$（因为决策后必须且只能存活或结束，归一化后只剩存活分支）；
- 首次到达奖励$a_i$ 仍然只加一次，后续在j点的所有“存活操作”（停或走）都没有额外固定奖励。
建模期望：从“终点”倒推更简单
对于带终止条件的随机游走期望问题,倒推法（从终止状态向前推导已确定状态的期望） 通常比顺推更方便——因为终止状态的期望是明确的（0）。
定义DP数组
设：
- $x_i$：从点i出发，首次到达点i（起点不算首次？哦不对，倒着来的话，起点就是当前位置，但倒推时我们要考虑“从某个点出发，走完一圈的有效部分并触发后续奖励”——换个更严谨的定义）
- 正推修正后的标准DP定义：$x_i$ 表示“从点i出发，首次完成一次完整的、包含点i的移动链（即停留在i若干次后之一次移动到i+1）”的过程中，除了起点i的首次奖励外，获得的期望总奖励。
等等,这样绕一圈回到i+1可能有点绕，不如再简化成环上的线性版本： 因为环是对称（或者说可旋转）的，我们可以先固定一个起点k，计算从k出发的期望总奖励$E_k$，最后取更大值。
固定起点k的正推DP
设 $E$ 为从k出发的总期望奖励：
- 之一次到达k（必到），获得 $a_k$；
- 之后进入“存活决策循环”：
- 以$q_k$概率停留在k，无奖励，再次进入循环；
- 以$s_k$概率移动到k+1，此时相当于“进入了以k+1为新起点，但必须走回k后才能结束当前分支”的子问题？不对，倒推更直接！
正确的倒推DP（拆成线性+环闭合）
我们把环“剪开”成线性序列 $k, k+1, \dots, n, 1, 2, \dots, k-1$，设剪开后的第t个点为原环的点 $c_t$（$c1=k, c{n+1}=k$）。
定义 $f_t$：从剪开后的第t个点出发，走到第t+1个点之前的所有存活决策过程中，获得的期望总奖励（这里的“奖励”不包含首次奖励，除非t=1首次触发）。
计算单个$f_t$
从$c_t$出发：
- 首次停留在$c_t$时，如果是t=1的之一次停留，已经加过$a_k$了，后续所有在$c_t$的停留都不加；如果是t>1，首次到达$ct$时（也就是剪开后的第t步开始），加$a{c_t}$，后续停留不加。
- 决策循环（每次决策默认存活）：
- 以$q_{c_t}$概率停：无奖励，继续循环；
- 以$s_{ct}$概率走到$c{t+1}$：结束当前$ft$的计算，进入$f{t+1}$（如果t=n+1，走到$c_{n+1}=k$时，已经绕完一圈，不能再加$a_k$，直接结束当前的闭合环期望）。
设 $g_t$ 为从$ct$出发，“首次走到$c{t+1}$之前”的首次奖励部分（只有t>1时是$a_{c_t}$，t=1或t=n+1时是0），$h_t$ 为从$ct$出发到$c{t+1}$的“存活停留次数的期望”（但停留无奖励，所以不用算，不过可以用来算循环的结束概率权重）。
用几何分布算“首次走到$c{t+1}$的期望步数”前的权重： 每次决策，成功走到$c{t+1}$的概率是$s_{c_t}$，所以从$ct$到$c{t+1}$的整个过程的“期望存活权重”（相当于把所有可能的停留次数都折算成一个系数，用来乘后续的奖励）为： $$wt = \sum{k=0}^{\infty} q_{ct}^k \cdot s{ct} = \frac{s{ct}}{1 - q{ct}} = \frac{s{ct}}{s{c_t}} = 1$$ 哦！这个归一化太关键了！不管怎么停留，从$ct$走到$c{t+1}$的整个存活分支的“贡献系数”都是1——也就是说，$f_t$可以写成： $$f_t = g_t + wt \cdot f{t+1} = gt + f{t+1}$$
等等,这是不是太简单了？不对，我们刚才漏了“闭合环的影响”——因为剪开后的序列是$c_1 \to c_2 \to \dots \to cn \to c{n+1}=c1$，而$c{n+1}$的$f{n+1}$不能直接取0，因为走到$c{n+1}=c_1$之后，游戏并没有结束，而是会继续绕环走，但此时已经不能再加任何首次奖励了（因为所有点都已经被首次到达过）！
处理“无首次奖励的环上循环期望”
现在我们把问题拆成两部分：
- 首次遍历阶段：从k出发，之一次绕环走一圈，每个点$ct$（t=2~n）首次到达时加$a{c_t}$，这部分的期望总奖励是固定的吗？等下，刚才的$ft$里，首次遍历阶段到$c{n+1}=c_1$时，累计的奖励是$Sk = \sum{t=2}^n a_{ct} = \sum{i \neq k} a_i$——对！因为不管怎么停留，都会走完所有首次到达，这部分是固定值，和停留无关！
- 循环遍历阶段：绕完之一圈后，所有点的首次奖励都已用完，之后的每一圈都是“无固定奖励的随机游走环”，我们需要计算这个阶段的期望次数$C_k$（绕多少圈后触发游戏结束）——但这里的“触发结束”已经不能用之前的归一化了，因为归一化是把“每一步存活”当成前提，现在循环遍历阶段的“触发结束”是和每一步的实际停留/移动结合的！
哦,刚才的归一化拆分可能误导了我们，我们重新用未归一化的真实概率建模循环遍历阶段的期望——设绕完之一圈后，当前在点k（因为之一圈结束回到k），此时的期望奖励为$Y_k$，那么从k出发的总期望奖励$E_k$ $$E_k = ak + \sum{i \neq k} a_i + Yk = (\sum{i=1}^n a_i) + Y_k$$ 哇！总奖励的固定部分是所有a_i的和！那我们只需要求$Y_k$的更大值，最后加上总和就是答案——这一步大大简化了问题！
现在聚焦$Y_k$：绕完之一圈在k，之后每一步的流程是：
- 每到一个点j（初始是k），
- 以$r_j$概率结束：获得0奖励，Y=0；
- 以$1-r_j$概率继续：
- 子分支1：以$p_j$概率停留，无奖励，继续在j点重复流程；
- 子分支2：以$1-p_j$概率走到j+1，无奖励，继续在j+1点重复流程。
现在用倒推法定义$Y_j$：从点j出发（此时所有首次奖励已用完）的期望后续奖励——显然，我们要求的就是$Y_k$。
列写Y_j的线性递推方程
对任意j： $$Y_j = 0 \cdot r_j + (1-r_j) \cdot [ p_j Y_j + (1-pj) Y{j+1} ]$$ 整理一下： $$Y_j = (1-r_j)p_j Y_j + (1-r_j)(1-pj) Y{j+1}$$ 把含$Y_j$的项移到左边： $$Y_j [1 - (1-r_j)p_j] = (1-r_j)(1-pj) Y{j+1}$$ 令$b_j = \frac{(1-r_j)(1-p_j)}{1 - (1-r_j)p_j}$（注意$b_j$和我们之前的$s_i/q_i$归一化后的s_i完全一样！因为之前的s_i就是这个值）， $$Y_j = bj \cdot Y{j+1}$$
闭合环的约束：找到Y_k的表达式！
因为是环,Y_{n+1} = Y_1$，我们可以把递推式展开到环闭合： $$Y_1 = b_1 Y_2 = b_1 b_2 Y_3 = \dots = b_1 b_2 \dots bn Y{n+1} = B Y1$$ B = \prod{j=1}^n b_j$。
现在分两种情况讨论：
情况1：$B = 1$
Yj = Y{j+1}$对所有j成立，代入递推式的原始未整理形式： $$Y_j = (1-r_j)p_j Y_j + (1-r_j)(1-p_j) Y_j = (1-r_j) Y_j$$ 移项得$Y_j \cdot r_j = 0$，而题目中$r_j > 0$，Y_j = 0$对所有j成立——此时不管选哪个起点k，$Y_k=0$，总期望奖励就是所有a_i的和！
情况2：$B \neq 1$
这是更普遍的情况,Y_j = 0$是唯一解吗？不对！刚才我们的递推式是不是漏了什么？哦不——刚才的定义“绕完之一圈后所有首次奖励已用完”是对的，但有没有可能，在首次遍历阶段绕环的过程中，就触发了游戏结束？
！！！致命错误！！！ 刚才的归一化和拆分把“首次遍历阶段一定能走完一圈”当成了前提，但实际上，游戏可能在首次到达某个点j后，停留或移动的过程中就触发结束——根本走不完一圈！
好的,现在推翻之前的“固定首次奖励总和”的结论，重新严谨建模（这次一定不会漏了！）。
推翻重来：严谨的正推线性建模（带环约束）
我们还是固定一个起点k,把环剪开成$c_1=k, c_2=k+1, \dots, cn=k-1, c{n+1}=k$的线性序列，定义全新的、带系数的DP数组： 设：
- $x_t$：从$c_t$出发，在首次触发游戏结束之前，获得的期望总奖励；
- 为了闭合环,再定义$z_t$：从$c_t$出发，首次触发游戏结束之前，成功绕回到$c_{n+1}=k$的概率**（绕回k后，就相当于进入了以k为起点的子问题，但所有点都已经可能被首次到达过？不，绕回k时，只有剪开后的t>1的点被首次到达过，所以此时的总奖励应该是“从$ct$到$c{n+1}$的期望奖励”加上“绕回k的概率”乘以“从k出发但不能再加$a_k$的期望奖励”——这个思路可以，但我们换一种更通用的“线性函数表示x_t”的 *** ，因为环的约束通常会把DP表示成$x_t = At x{t+1} + B_t$，闭合后就能解出x_k！
对！这个 *** 是解决“环上线性递推”的通用套路：如果能把每个xt表示成x{t+1}的一次线性函数，那么闭合后x_{n+1}=x_1，代入就能解出x_1（也就是起点k的期望）。
好的,现在列写$x_t$的方程： 从$c_t$出发：
- 首次到达$ct$（如果是之一次到达，即不是绕回来的，加$a{c_t}$——但绕回来的情况是通过z_t引入的，所以这里的x_t已经包含了首次到达奖励吗？不，我们把首次到达奖励放在初始分支里）：
- 哦更清晰的拆分：从$c_t$出发，之一步一定是“到达$c_t$并触发一次存活判断”吗？不，题目中起点就是$c_t$，所以直接开始决策循环： 决策循环（起点就是$ct$，已经算首次到达，所以加$a{c_t}$作为初始项）：
- 初始获得$a_{c_t}$；
- 每一轮在$ct$： a. 以$r{ct}$概率结束：总奖励就是$a{ct}$； b. 以$1-r{ct}$概率继续： i. 以$p{c_t}$概率停留：无额外奖励，回到“在$ct$的新一轮决策循环，但已经加过$a{ct}$了”； ii. 以$1-p{ct}$概率走到$c{t+1}$：总奖励就是$a_{ct}$加上$x{t+1}$（注意$x{t+1}$已经包含了$c{t+1}$的首次奖励）。
现在把“已经加过$a_{c_t}$的后续决策循环”设为$y_t$，xt = a{c_t} + y_t$。
接下来列写$y_t$的方程： 从$y_t$（在$c_t$，已加过首次奖励）出发：
- 以$r_{c_t}$概率结束：获得0；
- 以$1-r_{ct}$概率继续： i. 以$p{c_t}$概率停留：回到$yt$； ii. 以$1-p{ct}$概率走到$c{t+1}$：获得$x_{t+1}$。
整理$y_t$： $$yt = 0 \cdot r{ct} + (1-r{ct}) [ p{c_t} yt + (1-p{ct}) x{t+1} ]$$ $$yt = (1-r{ct})p{c_t} yt + (1-r{