跳到主要内容

P1654 OSU!

难度算法s日期题目链接
提高+/省选−数学期望、递推2025-07-21~22https://luogu.com.cn/problem/P1654

似乎是一道蛮经典的期望递推题。

洛谷上的题解看不懂，老师讲的也很简略。只有自己推起来感觉很复杂。。。心累。

题意简述​

一共有 nn 次操作，第 kk 次操作（1≤k≤n1\le k\le n）成功的概率是 pip_i。成功记作 11，失败记作 00，那么所有操作的结构依次连起来就可以得到一个 0/10/1 串。在这个串中，每个极大的、连续的 XX 个 11 会对分数产生 X3X^3 的贡献，每个全为 11 的子段的贡献线性累加。

求：贡献总和的期望 EE。

范围：1≤n≤1051\le n\le10^5。

思路​

考虑线性递推。

  • 我们把以位置 kk 结尾的一串 11 的长度记为 XkX_k。

  • 让我们先试着求长度一次方的期望。我们把 XkX_k 的期望记为 E(Xk)E(X_k)。在这个位置 kk，我们向串尾追加第 k+1k+1 个操作结果，有两种情况：

    • 有 pk+1p_{k+1} 的概率第 k+1k+1 次操作成功。成功后 Xk+1X_{k+1} 的期望为 E(Xk)+1E(X_k)+1。（也就是 11 串的长度 +1+1）

    • 另外 1−pk+11-p_{k+1} 的概率第 k+1k+1 次操作失败。失败后串尾就没有 11 了，所以 E(Xk)=0E(X_k)=0。

    所以：

    E(Xk+1)=pk+1E(Xk+1)+(1−pk+1)×0.E(X_{k+1})=p_{k+1}E(X_k+1)+(1-p_{k+1})\times0.

    由期望的线性性，

    E(Xk+1)=E(Xk)+E(1)=E(Xk)+1,E(X_k+1)=E(X_k)+E(1)=E(X_k)+1,

    这里常数 CC 的期望 E(C)E(C) 当然就是 CC 了，不然还能有别的取值吗。进一步化简，得：

    E(Xk+1)=pk+1[E(Xk)+1].(1)E(X_{k+1})=p_{k+1}[E(X_k)+1].(1)

  • 类似地，记 Xk2X_k^2 的期望为 E(Xk2)E(X_k^2)。我们尝试求一下长度二次方的期望的递推式：

    E(Xk+12)=pk+1E[(Xk+1)2]+(1−pk+1)×0E(X_{k+1}^2)=p_{k+1}E[(X_k+1)^2]+(1-p_{k+1})\times0

    请注意： 此处是 E[(Xk+1)2]E[(X_k+1)^2] 而不是 [E(Xk)+1]2[E(X_k)+1]^2，写成后面那个就推不出来了。（而且也是错的）。

    化简 E[(Xk+1)2]E[(X_k+1)^2]，依旧是利用期望的线性性：

    E[(Xk+1)2]=E(Xk2+2Xk+1)=E(Xk2)+2E(Xk)+1.E[(X_k+1)^2]=E(X_k^2+2X_k+1)=E(X_k^2)+2E(X_k)+1.

    化简整个式子：

    E(Xk+12)=pk+1[E(Xk2)+2E(Xk)+1].(2)E(X_{k+1}^2)=p_{k+1}[E(X_k^2)+2E(X_k)+1].(2)

  • 类似地，记 Xk3X_k^3 的期望为 E(Xk3)E(X_k^3)。那么长度三次方的期望的递推式：

    E(Xk+13)=pk+1E[(Xk+1)3]+(1−pk+1)×0,E(X_{k+1}^3)=p_{k+1}E[(X_k+1)^3]+(1-p_{k+1})\times0,

    化简（过程略）：

    E(Xk+13)=pk+1[E(Xk3)+3E(Xk2)+3E(Xk)+1].E(X_{k+1}^3)=p_{k+1}[E(X_k^3)+3E(X_k^2)+3E(X_k)+1].

期望推过瘾了，那我们怎么求答案呢？我们假设 [1,k][1,k] 上的分数的期望为 EkE_k，那么EnE_n 就是答案了，接下来考虑如何递推：

  • 有 pk+1p_{k+1} 的概率第 k+1k+1 次操作成功，那么 11 串继续累加，Ek+1=pk+1[Ek+3E(Xk2)+3E(Xk)+1]E_{k+1}=p_{k+1}[E_k+3E(X_k^2)+3E(X_k)+1]。这一部分和长度三次方的期望是一样的（只不过我们把 E(Xk3)E(X_k^3) 换成了 EkE_k）。

  • 另外 1−pk+11-p_{k+1} 的概率第 k+1k+1 次操作失败，那么期望不变， Ek+1=EkE_{k+1}=E_{k}。注意，这里就和上面长度三次方的递推式不同了。因为上面我们规定 XkX_k 是以 kk 结尾的 11 串的长度，如果操作失败，长度和期望都清零了。但是这里我们是要统计累积的期望分数，所以期望不清零。

加起来就得到：

Ek+1=Ek+pk+1[3E(Xk2)+3E(Xk)+1].(3)E_{k+1}=E_{k}+p_{k+1}[3E(X_{k}^2)+3E(X_{k})+1].(3)

结合 (1)(2)(3)(1)(2)(3)，就容易设计递推了。

补充​

请注意： E(Xk3)≠[E(Xk)]3E(X_k^3)\not=[E(X_k)]^3，即三次方的期望 ≠\not= 期望的三次方。这也解释了我们为什么要大费周章地推式子，而不是直接推出 E(Xn)E(X_n) 然后取三次方。

为了避免这个混淆，上面我不辞辛苦地把一个个期望都严格写成 E(Xk)E(X_k) 而不是 E(k)E(k)。TwT