8
感觉是比较冷门的技巧（）
点击这里获得更卡哇伊的阅读体验
引入
> 一个数轴，初始有一个点在 000 位置。现在这个点会移动 nnn 次，每一次有 12\frac1221 的概率点从 xxx 移动到 x+1x+1x+1，另外 12\frac1221 的概率点从 xxx 移动到 x−1x-1x−1。问移动完 nnn 次之后 ∣x∣|x|∣x∣ 的期望值是多少。
上述问题的答案不超过 O(n)O(\sqrt n)O(n ) 级别。下面给出一个简单的证明：
直接计算 E[∣x∣]E[|x|]E[∣x∣] 比较复杂。考虑先放缩一下，计算出 E[x2]E[x^2]E[x2] 的值，然后就可以直接得到 E[∣x∣]≤E[x2]E[|x|]\le \sqrt{E[x^2]}E[∣x∣]≤E[x2] 。
记第 iii 步 xxx 移动的决策是 pip_ipi （也就是 xxx 在第 iii 次操作中移动到了 x+pix+p_ix+pi 位置）。则显然有 x2=(p1+p2+…+pn)2x^2=(p_1+p_2+\ldots+p_n)^2x2=(p1 +p2 +…+pn )2，也就可以得到
E[x2]=∑i=1nE[pi2]+2∑i=1n∑j=i+1nE[pipj]=n+2∑i=1n∑j=i+1nE[pipj]E[x^2]=\sum\limits_{i=1}^nE[p_i^2]+2\sum\limits_{i=1}^n\sum\limits_{j=i+1}^nE[p_ip_j]=n+2\sum\limits_{i=1}^n\sum\limits_{j=i+1}^nE[p_ip_j]E[x2]=i=1∑n E[pi2 ]+2i=1∑n j=i+1∑n E[pi pj ]=n+2i=1∑n j=i+1∑n E[pi pj ]。又因为决策之间是两两独立的，所以直接分类
pi,pjp_i,p_jpi ,pj 的取值分别算期望，可以得到 E[pipj]=0E[p_ip_j]=0E[pi pj ]=0，也就得到了 E[x2]=n⇒E[x]≤O(n)E[x^2]=n\Rightarrow E[x]\le O(\sqrt n)E[x2]=n⇒E[x]≤O(n )。
现在在上面的问题上扩展，考虑另外一个与其相似的问题：
> 一个数轴，初始有一个点在 000 位置。现在这个点会移动 nnn 次，每一次有 12\frac1221 的概率点从 xxx 移动到 x+1x+1x+1，另外 12\frac1221 的概率点从 xxx 移动到 x−1x-1x−1。问移动完 nnn 次后，xxx 移动到的全部 n+1n+1n+1 个位置中绝对值最大的点的期望值是多少。
解决完上一个问题之后容易猜测答案还是 O(n)O(\sqrt n)O(n ) 级别的。下面给出一个证明：
设随机游走位置为 S0=0,Sk=ξ1+ξ2+⋯+ξkS_0=0,S_k=\xi_1+\xi_2+\cdots+\xi_kS0 =0,Sk =ξ1 +ξ2 +⋯+ξk ，其中每个 ξi\xi_iξi 有 12\frac1221 的概率为 111，另外 12\frac1221 的概率为 −1-1−1。为了方便，记 Mi=maxj=0i∣Sj∣M_i=\max\limits_{j=0}^i|S_j|Mi =j=0maxi ∣Sj ∣ 即前 iii 次移动中距离原点最远的距离是多少。
因为 MnM_nMn 是非负整数，所以 E[Mn]=∑t≥1Pr(Mn≥t)\mathbb E[M_n]=\sum_{t\ge1}\Pr(M_n\ge t)E[Mn ]=∑t≥1 Pr(Mn ≥t)。
所以只要我们能证明 Pr(Mn≥t)≤Ce−ct2/n\Pr(M_n\ge t)\le C e^{-c t^2/n}Pr(Mn ≥t)≤Ce−ct2/n，把这个式子对 ttt 求和，就会得到 E[Mn]=O(n)\mathbb E[M_n]=O(\sqrt n)E[Mn ]=O(n )。
事件 Mn≥tM_n\ge tMn ≥t 的意思是：在前 nnn 步里，曾经到过 ttt 或者 −t-t−t。所以 Pr(Mn≥t)≤Pr(max0≤k≤nSk≥t)+Pr(min0≤k≤nSk≤−t) \Pr(M_n\ge t) \le \Pr\Bigl(\max_{0\le k\le n}S_k\ge t\Bigr) + \Pr\Bigl(\min_{0\le k\le n}S_k\le -t\Bigr)Pr(Mn ≥t)≤Pr(max0≤k≤n Sk ≥t)+Pr(min0≤k≤n Sk ≤−t)。
由于对称性，这两项相等，因此有：Pr(Mn≥t)≤2Pr(max0≤k≤nSk≥t)\Pr(M_n\ge t)\le 2\Pr\Bigl(\max_{0\le k\le n}S_k\ge t\Bigr)Pr(Mn ≥t)≤2Pr(max0≤k≤n Sk ≥t)。
现在用一维随机游走最经典的“反射法”结论：Pr(max0≤k≤nSk≥t)≤2Pr(Sn≥t)\Pr\Bigl(\max_{0\le k\le n}S_k\ge t\Bigr)\le 2\Pr(S_n\ge t)Pr(max0≤k≤n Sk ≥t)≤2Pr(Sn ≥t)，结合一下就可以得到 Pr(Mn≥t)≤4Pr(Sn≥t)\Pr(M_n\ge t)\le 4\Pr(S_n\ge t)Pr(Mn ≥t)≤4Pr(Sn ≥t)。
此时又因为 Sn=ξ1+⋯+ξnS_n=\xi_1+\cdots+\xi_nSn =ξ1 +⋯+ξn 是 nnn 个独立 ±1\pm1±1 的和，所以它的方差是 nnn，标准差是 n\sqrt nn 。更进一步，SnS_nSn 有高斯型尾估计：Pr(Sn≥t)≤e−t2/(2n)\Pr(S_n\ge t)\le e^{-t^2/(2n)}Pr(Sn ≥t)≤e−t2/(2n)，因此 Pr(Mn≥t)≤4e−t2/(2n)\Pr(M_n\ge t)\le 4e^{-t^2/(2n)}Pr(Mn ≥t)≤4e−t2/(2n)。
结合一开始得到的式子，有：
E[Mn]=∑t≥1Pr(Mn≥t)≤∑t≥14e−t2/(2n)\mathbb E[M_n]= \sum_{t\ge1}\Pr(M_n\ge t)\le\sum_{t\ge1}4e^{-t^2/(2n)}E[Mn ]=t≥1∑ Pr(Mn ≥t)≤t≥1∑ 4e−t2/(2n)
而这个和的量级就是 n\sqrt nn 。最简单的看法是把它和积分比较：
∑t≥1e−t2/(2n)≤∫0∞e−x2/(2n)dx=n∫0∞e−u2/2du=Cn\sum_{t\ge1}e^{-t^2/(2n)} \le \int_0^\infty e^{-x^2/(2n)}{dx}= \sqrt n\int_0^\infty e^{-u^2/2}du= C\sqrt n t≥1∑ e−t2/(2n)≤∫0∞ e−x2/(2n)dx=n ∫0∞ e−u2/2du=Cn
所以有 E[Mn]≤4Cn\mathbb E[M_n]\le 4C\sqrt nE[Mn ]≤4Cn 。于是得到最终结论：
E[Mn]=O(n)\boxed{\mathbb E[M_n]=O(\sqrt n)} E[Mn ]=O(n )
事实上，可以继续收紧上下界得到 E[Mn]∼πn2\mathbb E[M_n]\sim\sqrt{\frac{\pi n}2}E[Mn ]∼2πn ，但是我不会证，而且在实际题目中并不需要这么紧的上界，因此这里直接给出一个由 ChatGPT 5.4 Thinking 给出的证明过程：
:::info[证明过程]
设随机游走的过程为：
S0=0,Sk=∑i=1kξi,Pr(ξi=1)=Pr(ξi=−1)=12,S_0=0,\qquad S_k=\sum_{i=1}^k \xi_i,\qquad \Pr(\xi_i=1)=\Pr(\xi_i=-1)=\frac12, S0 =0,Sk =i=1∑k ξi ,Pr(ξi =1)=Pr(ξi =−1)=21 ,
题目要求的是 Mn:=max0≤k≤n∣Sk∣M_n:=\max_{0\le k\le n}|S_k|Mn :=max0≤k≤n ∣Sk ∣ 的期望 E[Mn]\mathbb E[M_n]E[Mn ]。
1. 先写成尾和公式
因为 MnM_nMn 是非负整数值随机变量，所以：
E[Mn]=∑m≥1Pr(Mn≥m).\mathbb E[M_n]=\sum_{m\ge1}\Pr(M_n\ge m). E[Mn ]=m≥1∑ Pr(Mn ≥m).
而 nnn 步最多走到距离 nnn，所以实际上：
E[Mn]=∑m=1nPr(Mn≥m)\boxed{\mathbb E[M_n]=\sum_{m=1}^n \Pr(M_n\ge m)} E[Mn ]=m=1∑n Pr(Mn ≥m)
也就是：
E[Mn]=∑m=1n(1−Pr(Mn<m))\boxed{\mathbb E[M_n]=\sum_{m=1}^n \Bigl(1-\Pr(M_n<m)\Bigr)} E[Mn ]=m=1∑n (1−Pr(Mn <m))
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2. 精确公式
事件 Mn<mM_n<mMn <m 就是“前 nnn 步始终没有碰到 ±m\pm m±m”，也就是随机游走在区间 −m+1,−m+2,…,m−1{-m+1,-m+2,\dots,m-1}−m+1,−m+2,…,m−1
内存活到第 nnn 步。
这是经典吸收随机游走，谱分解可得：
Pr(Mn<m)=1m∑j=0m−1(−1)jcot(2j+1)π4m,(cos(2j+1)π2m)n.\Pr(M_n<m) = \frac1m\sum_{j=0}^{m-1} (-1)^j \cot\frac{(2j+1)\pi}{4m}, \Bigl(\cos\frac{(2j+1)\pi}{2m}\Bigr)^n. Pr(Mn <m)=m1 j=0∑m−1 (−1)jcot4m(2j+1)π ,(cos2m(2j+1)π )n.
因此：
E[Mn]=∑m=1n[1−1m∑j=0m−1(−1)jcot(2j+1)π4m,(cos(2j+1)π2m)n].\boxed{ \mathbb E[M_n] = \sum_{m=1}^n \left[ 1- \frac1m\sum_{j=0}^{m-1} (-1)^j \cot\frac{(2j+1)\pi}{4m}, \Bigl(\cos\frac{(2j+1)\pi}{2m}\Bigr)^n \right]. } E[Mn ]=m=1∑n [1−m1 j=0∑m−1 (−1)jcot4m(2j+1)π ,(cos2m(2j+1)π )n].
这就是这个期望的一个标准精确表达式。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
3. 渐近结果
当 n→∞n\to\inftyn→∞ 时，有经典极限定理：
Mnn ⟹ sup0≤t≤1∣Bt∣\frac{M_n}{\sqrt n}\ \Longrightarrow\ \sup_{0\le t\le 1}|B_t| n Mn ⟹ 0≤t≤1sup ∣Bt ∣
其中 BtB_tBt 是标准布朗运动。并且该极限随机变量的期望是：
E[sup0≤t≤1∣Bt∣]=π2\mathbb E\Bigl[\sup_{0\le t\le 1}|B_t|\Bigr] = \sqrt{\frac{\pi}{2}} E[0≤t≤1sup ∣Bt ∣]=2π
所以：
E[Mn]∼πn2\boxed{\mathbb E[M_n]\sim \sqrt{\frac{\pi n}{2}}} E[Mn ]∼2πn
也就是主项约为：
E[Mn]≈1.253314n.\mathbb E[M_n]\approx 1.253314\sqrt n. E[Mn ]≈1.253314n .
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
4. 对比一下末位置
注意这不是最后位置 ∣Sn∣|S_n|∣Sn ∣ 的期望。后者是 E∣Sn∣∼2nπ,\mathbb E|S_n|\sim \sqrt{\frac{2n}{\pi}},E∣Sn ∣∼π2n ,，而这里取的是全过程的最大绝对值，所以更大，主常数变成了 π2\sqrt{\frac{\pi}{2}}2π 。
5. 最终结论
精确值：
E![max0≤k≤n∣Sk∣]=∑m=1n[1−1m∑j=0m−1(−1)jcot!(2j+1)π4m,(cos!(2j+1)π2m)n].\boxed{ \mathbb E!\left[\max_{0\le k\le n}|S_k|\right] = \sum_{m=1}^n \left[ 1- \frac1m\sum_{j=0}^{m-1} (-1)^j \cot!\frac{(2j+1)\pi}{4m}, \Bigl(\cos!\frac{(2j+1)\pi}{2m}\Bigr)^n \right]. } E![0≤k≤nmax ∣Sk ∣]=m=1∑n [1−m1
j=0∑m−1 (−1)jcot!4m(2j+1)π ,(cos!2m(2j+1)π )n].
渐近值：
E![max0≤k≤n∣Sk∣]∼πn2\boxed{ \mathbb E!\left[\max_{0\le k\le n}|S_k|\right] \sim \sqrt{\frac{\pi n}{2}}} E![0≤k≤nmax ∣Sk ∣]∼2πn
:::
解决问题
考虑用上面给出的 trick 解决一道经典题目！
题目给出的六边形网格不太好处理，因此容易想到把这个东西压扁，将六个方向修改为上，下，左，右，右上，左下。此时容易想到直接 dp。设 fi,x,y,j,kf_{i,x,y,j,k}fi,x,y,j,k 表示当前处理了前 iii 个 idea，L=j,G=kL=j,G=kL=j,G=k，当前网格的横坐标是 xxx，纵坐标是 yyy，是否是可行的状态。
考虑优化这个 dp。可行性 dp 通常有下面两种优化方法：
* 把一维状态写到答案里。
* 用 bitset 优化。
这个问题看着很不能把状态写到答案里，因此考虑用 bitset 优化。发现 yyy 这个 dp 维度其实就是在做一次循环移位操作，用 bitset 优化可以让时间复杂度除一个 www，但是仍然难以通过。
考虑利用上面的 trick。注意到最后需要让所在的位置 (x,y)(x,y)(x,y) 回到 (0,0)(0,0)(0,0)，而上面的 trick 在更高维度上也同样满足距离 (0,0)(0,0)(0,0) 的曼哈顿距离期望为 O(n)O(\sqrt n)O(n ) 级别。因此考虑直接随机打乱输入的 idea 顺序，此时对于距离原点超过 O(n)O(\sqrt n)O(n ) 的位置，其很大概率是可以被不超过 O(n)O(\sqrt n)O(n ) 的位置所替代的，因此只需要处理 x,y∈[−O(n),O(n)]\boldsymbol{x,y\in[-O(\sqrt n),O(\sqrt
n)]}x,y∈[−O(n ),O(n )] 的部分，范围以外的 dp 值直接截断处理即可。此时算法的时间复杂度被优化到 O(n2p2w)O(\frac{n^2p^2}w)O(wn2p2 )，卡常后可以通过该题。
:::success[代码]
因为作者不太会卡常所以目前只有用 C++98 提交才能通过/kel
:::
练习
> 给定一个 nnn 个结点的树，每条边都有边权（边权可能为负）。你需要选择若干条有 444 条边组成的简单路径（可以不选），使得没有一条边被超过一条路径覆盖。问所有被路径覆盖的边的边权的和最大是多少。
>
> 数据范围：2≤n≤2×1052\le n\le 2\times 10^52≤n≤2×105。
考虑一个暴力的 dp 做法。设 fi,0/1/2/3f_{i,0/1/2/3}fi,0/1/2/3 表示当前只处理 iii 结点为根的子树，iii 结点没有挂长度不为 444 的链 / 在子树里挂了一条长度为 1/2/31/2/31/2/3 的链，边权之和最大是多少。转移过程需要合并儿子结点的 dp 信息，考虑再记一个 dp 数组辅助转移：设 gi,0/1g_{i,0/1}gi,0/1 表示当前合并了若干个儿子结点的信息，其中儿子结点里长度为 000 的链比长度为 222 的链多 iii 条，长度为 111 的链数量 mod 2=0,1\bmod\
2=0,1mod 2=0,1，边权和最大是多少（只记录这些信息是因为子树内合并链只能是长度为 0,20,20,2 的链对应匹配，长度为 111 的链单独匹配）。此时合并信息是简单的。
直接做转移时间复杂度为 O(n2)O(n^2)O(n2)。注意到辅助转移的 ggg 数组中 iii 维度维护的是两类儿子结点的链的差值，而一个儿子结点只能有最多一条连向父亲结点的链，最后可以转移到 fff 数组里的 ggg 也只有 g−1,∗,g0,∗,g1,∗g_{-1,*},g_{0,*},g_{1,*}g−1,∗ ,g0,∗ ,g1,∗ 三类。因此考虑把长度为 000 的链看作 111，长度为 222 的链看作 −1-1−1，则可以看作是在数轴上做随机游走，打乱儿子结点顺序后 gig_igi 这个维度只需要维护 O(n)O(\sqrt n)O(n ) 个 iii
的信息即可。此时算法的时间复杂度优化到 O(nn)O(n\sqrt n)O(nn )，可以通过该题。
:::success[代码]
:::
，是因为老师写板书的时候，它正好卡在黑板上以前写过字留下的“粉笔沟”里。就像你骑自行车突然掉进马路牙子缝里，吓一跳，本能地“吱——”一声。
，齐刷刷看向老师
。老师只能尴尬地
换一根新粉笔
，嘴里嘟囔：“这破黑板……”——其实心里清楚，是自己力气用歪了
。粉笔呢？已经断成两截
，在粉笔槽里默默背锅。
有帮助，赞一个