前言

随机变量 XX 的期望定义如下：

E[X]=∑xxPr⁡(X=x)\mathbb E[X]=\sum_x x\Pr(X=x)

在事件 Y=yY=y 发生的情况下，条件期望的定义：

E[X∣Y=y]=∑xxPr⁡(X=x∣Y=y)\mathbb E[X\mid Y=y]=\sum_x x\Pr(X=x\mid Y=y)

注意，此时 E[X∣Y=y]\mathbb E[X\mid Y=y] 是 yy 的函数，不再是一个常数。

根据全概率公式，我们可以推出全期望公式：

E[X]=∑xxPr⁡(X=x)=∑x∑yxPr⁡(X=x∣Y=y)Pr⁡(Y=y)=∑yPr⁡(Y=y)(∑xxPr⁡(X=x∣Y=y))=∑iPr⁡(Y=y)E[X∣Y=y]=E[E[X∣Y]]\begin{aligned} \mathbb E[X]&=\sum_x x\Pr(X=x)\\ &=\sum_x\sum_y x\Pr(X=x\mid Y=y)\Pr(Y=y)\\ &=\sum_y \Pr(Y=y)\left(\sum_xx\Pr(X=x\mid Y=y)\right)\\ &=\sum_i \Pr(Y=y)\mathbb E[X\mid Y=y]\\ &=\mathbb E[\mathbb E[X\mid Y]]\\ \end{aligned}

对若干步递推中的事件划分出合适的随机变量，可以帮助我们更方便地推导期望相关公式。

P1654

记随机变量 XiX_i 为 ii 轮后的得分，TiT_i 表示 ii 轮后末尾连续段的长度。

那么就可以得到：

E[Xi−Xi−1∣Ti−1]=(1−pi)×0+pi[(Ti−1+1)3−Ti−13]=3piTi−12+3piTi−1+pi\begin{aligned} \mathbb E[X_i-X_{i-1}\mid T_{i-1}] &=(1-p_i)\times 0+p_i[(T_{i-1}+1)^3-T_{i-1}^3]\\ &=3p_i T_{i-1}^2+3p_i T_{i-1}+p_i \end{aligned}

紧接着，我们给出 Ti2T_i^2 与 TiT_i 的期望递推公式：

E[Ti∣Ti−1]=(1−pi)×0+pi(Ti−1+1)=piTi−1+piE[Ti2∣Ti−1]=(1−pi)×0+pi(Ti−1+1)2=piTi−12+2piTi−1+pi\begin{aligned} \mathbb E[T_i\mid T_{i-1}]&=(1-p_i)\times 0 + p_i(T_{i-1}+1)\\ &=p_iT_{i-1}+p_i\\ \mathbb E[T_i^2\mid T_{i-1}]&=(1-p_i)\times 0 + p_i(T_{i-1}+1)^2\\ &=p_iT_{i-1}^2+2p_iT_{i-1}+p_i\\ \end{aligned}

核心的思想是定义合适的随机变量，使得能够根据描述写出条件期望的式子。

复杂度 O(n)O(n)。

[CCPC 2023 Shenzhen] Rooted Tree

记执行 ii 次操作后的树为 TiT_i，并且定义节点深度之和 Xi=f(Ti)X_i=f(T_i)，叶子深度之和 Yi=g(Ti)Y_i=g(T_i)，并且叶子数量 Li=1+(M−1)iL_i=1+(M-1)i。

考虑执行一次操作后 XiX_i 的变化：

E[Xi−Xi−1∣Ti−1]=∑u∈leaf⁡(Ti−1)(du+1)MLi−1=MYi−1Li−1+M\begin{aligned} \mathbb E[X_i-X_{i-1}\mid T_{i-1}] &= \sum_{u\in \operatorname{leaf}(T_{i-1})}\frac{(d_u+1)M}{L_{i-1}}\\ &=\frac{MY_{i-1}}{L_{i-1}}+M \end{aligned}

同时，我们也需要递推 YiY_i 的变化：

E[Yi−Yi−1∣Ti−1]=∑u∈leaf⁡(Ti−1)(du+1)M−duLi−1=(M−1)Yi−1Li−1+M\begin{aligned} \mathbb E[Y_i-Y_{i-1}\mid T_{i-1}]&=\sum_{u\in\operatorname{leaf}(T_{i-1})}\frac{(d_u+1)M-d_u}{L_{i-1}}\\ &=\frac{(M-1)Y_{i-1}}{L_{i-1}}+M \end{aligned}

整理可以得到：

E[Yi]1+(M−1)i=E[Yi−1]1+(M−1)(i−1)+M1+M(i−1)\frac{\mathbb E[Y_i]}{1+(M-1)i}=\frac{\mathbb E[Y_{i-1}]}{1+(M-1)(i-1)}+\frac{M}{1+M(i-1)}

分别维护分子分母即可做到 O(1)O(1) 递推出所有 E[Yi]\mathbb E[Y_i]，也就能推出 E[Xi]\mathbb E[X_i]。

复杂度 O(K+log⁡P)O(K+\log P)。

[THUCAMP 2026 Day3] To Make You Cry

给定 n≤3×105n\le 3\times 10^5 个节点的树，每条边 ii 有相互独立的 xi%x_i\% 的概率不被删除，每个点 ii 有权值 wi(1≤wi≤10)w_i(1\le w_i\le 10)，求最大权独立集的期望，对 109+710^9+7 取模。

考虑不删边的时候怎么做。定义 dpu,0dp_{u,0} 表示不选 uu，dpu,1dp_{u,1} 表示选 uu，那么转移自然是：

dpu,0=∑v∈son⁡(u)max⁡(dpv,0,dpv,1)dpu,1=wu+∑v∈son⁡(u)dpv,0\begin{aligned} dp_{u,0} &= \sum_{v\in\operatorname{son}(u)} \max(dp_{v,0},dp_{v,1})\\ dp_{u,1} &= w_u+\sum_{v\in\operatorname{son}(u)} dp_{v,0} \end{aligned}

如果 (u,v)(u,v) 这条边被删掉，那么 dpu,1dp_{u,1} 也可以被 max⁡(dpv,0,dpv,1)\max(dp_{v,0},dp_{v,1}) 进行转移，于是题意目前就是 E[max⁡(dp1,0,dp1,1)]\mathbb E[\max(dp_{1,0},dp_{1,1})]。

一个众所周知的事实是，一般来讲 E[max⁡(X,Y)]≠max⁡(E[X],E[Y])\mathbb E[\max(X,Y)]\neq \max(\mathbb E[X],\mathbb E[Y])，所以我们需要把 max⁡\max 设计到期望里面去。

直接根据转移方程求出 E[dpu,0]\mathbb E[dp_{u,0}] 与 E[dpu,1]\mathbb E[dp_{u,1}] 即可，主要的问题是如何求出 E[max⁡(dpu,0,dpu,1)]\mathbb E[\max(dp_{u,0},dp_{u,1})]。

考虑到这里我们需要以某种方式比较 dpu,0dp_{u,0} 和 dpu,1dp_{u,1}，所以给它做个差：

dpu,1−dpu,0=wu−∑v∈son⁡(u)max⁡(0,dpv,1−dpv,0)dp_{u,1}-dp_{u,0}=w_u-\sum_{v\in\operatorname{son}(u)} \max(0,dp_{v,1}-dp_{v,0})

显然可以看出 dpu,1−dpu,0≤wu≤10dp_{u,1}-dp_{u,0}\le w_u\le 10，并且小于 00 的值我们是不关心的，所以记 fu,jf_{u,j} 表示 max⁡(0,dpu,1−dpu,0)=j\max(0,dp_{u,1}-dp_{u,0})=j 的概率。

初始 fu,wu=1f_{u,w_u}=1，枚举每个 (u,v)(u,v)，更新：

∀k,fu,max⁡(0,j−k)←fv,k×fu,j×x(u,v)100fu,j←fu,j×(1−x(u,v)100)\begin{aligned} \forall k, f_{u,\max(0,j-k)} &\gets f_{v,k} \times f_{u,j} \times \frac{x_{(u,v)}}{100}\\ f_{u,j}&\gets f_{u,j}\times \left(1-\frac{x_{(u,v)}}{100}\right) \end{aligned}

即枚举不删和删两种情况，如果删边则 max⁡(0,dpu,1−dpu,0)\max(0,dp_{u,1}-dp_{u,0}) 不变化，如果不删则需要枚举子节点 vv 的 max⁡(0,dpv,1−dpv,0)\max(0, dp_{v,1}-dp_{v,0}) 的值。

那么就有：

E[max⁡(dpu,0,dpu,1)]=E[max⁡(0,dpu,1−dpu,0)+dpu,0]=E[max⁡(0,dpu,1−dpu,0)]+E[dpu,0]=∑j=010jfu,j+E[dpu,0]\begin{aligned} \mathbb E[\max(dp_{u,0},dp_{u,1})]&=\mathbb E[\max(0,dp_{u,1}-dp_{u,0})+dp_{u,0}]\\ &=\mathbb E[\max(0,dp_{u,1}-dp_{u,0})]+\mathbb E[dp_{u,0}]\\ &=\sum_{j=0}^{10} jf_{u,j}+\mathbb E[dp_{u,0}] \end{aligned}

复杂度 O(n(max⁡w)2)O(n(\max w)^2)。

[ZJCPC2026] PalindromemordnilaP

首先，每一种操作相当于在 n!n! 个排列中等概率选择一种，并且当 ss 成为回文串时停止操作，并且其权值是停止之前的操作次数。

对一个 (i,n−i+1)(i,n-i+1) 的 Pair 进行分类讨论：

  1. 若 nn 为奇数，那么中心位置改不改都可以。
  2. 若 si=sn−i+1s_i=s_{n-i+1}，那么 si=cs_i=c 时，这两个位置改不改都可以；si≠cs_i\neq c 时，这两个位置要么都改、要么都不改。
  3. 若 si≠sn−i+1s_i\neq s_{n-i+1}，那么当两个位置都不为 cc 时，这两个位置都必须改；当其中一个位置是 cc 时，另一个位置必须改，这个位置改不改都可以。

我们设改不改都可以的位置数量为 pp，必须改的位置数量为 aa，两个位置要么都改、要么都不改的 Pair 数量为 bb。

这样一来，一个排列的权值就是 aa 类位置出现的最后一个下标，并且要保证此时 bb 类 Pair 要么都改、要么都不改。

由于一个排列删掉改不改都可以的 pp 个位置后不会影响停止操作的相对位置，所以我们不妨先把这些位置删掉，最后再加回来。

现在的问题是，对于这 (a+2b)!(a+2b)! 个排列中，统计权值为 a,a+2,…,a+2ba,a+2,\dots,a+2b 的排列的数量。

设 fif_i 表示给定 ii 个 Pair，长度为 a+2ia+2i 且在最后一个位置终止的排列的数量，注意这里是 aa 个必改位置和给定的 2i2i 个位置。

于是我们对这 (a+2i)!(a+2i)! 个排列的终止位置进行划分：

(a+2i)!=∑j=0i(ij)fj(2i−2j)!(a+2i)!i!=∑j=0ifjj!(2i−2j)!(i−j)!\begin{aligned} (a+2i)!&=\sum_{j=0}^i \binom{i}{j} f_j(2i-2j)!\\ \frac{(a+2i)!}{i!}&=\sum_{j=0}^i \frac{f_j}{j!}\frac{(2i-2j)!}{(i-j)!} \end{aligned}

右侧是一个卷积的形式，所以我们定义 fi/i!f_i/i! 的生成函数为 FF，2i!/i!2i!/i! 的生成函数为 GG，(a+2i)!/i!(a+2i)!/i! 的生成函数为 HH，就有：

F=HGF=\frac{H}{G}

于是只需要多项式求逆即可求出所有 fif_i。

但是我们仍然需要最后把 pp 个位置插回原排列，这就用到了我们之前提到的条件期望。

具体地说，设 KK 是删掉 pp 个位置后排列的权值，XX 是加回来后排列的权值，那么可以列出表达式：

E[X∣K=k]=k+E[∑i=0k−1xi]\mathbb E[X\mid K=k]=k+\mathbb E\left[\sum_{i=0}^{k-1} x_i\right]

其中 xix_i 表示在 a+2ba+2b 个位置中，第 ii 个位置后面插入的 pp 类位置的数量。

由对称性，我们得到 E[x0]=E[x1]=⋯=E[xa+2b]\mathbb E[x_0]=\mathbb E[x_1]=\cdots=\mathbb E[x_{a+2b}]，又因为 ∑i=0a+2bxi=p\sum_{i=0}^{a+2b} x_i=p，因此就有：

E[X∣K=k]=k+E[∑i=0k−1xi]=k+kE[x0]=k(1+pa+2b+1)\begin{aligned} \mathbb E[X\mid K=k]&=k+\mathbb E\left[\sum_{i=0}^{k-1} x_i\right]\\ &=k+k\mathbb E[x_0]\\ &=k\left(1+\frac{p}{a+2b+1}\right) \end{aligned}

最后给出 E[K]\mathbb E[K] 的表达式：

E[K]=∑j=0b1(a+2b)!(bj)fj(2b−2j)!(a+2j)\mathbb E[K]=\sum_{j=0}^{b}\frac{1}{(a+2b)!}\binom{b}{j}f_j(2b-2j)!(a+2j)

复杂度 O(nlog⁡n)O(n\log n)。