难度 | 算法s | 日期 | 题目链接 |
---|---|---|---|
提高+/省选− | 数学期望、递推 | 2025-07-21~22 | https://luogu.com.cn/problem/P1654 |
似乎是一道蛮经典的期望递推题。
洛谷上的题解看不懂,老师讲的也很简略。只有自己推起来感觉很复杂。。。心累。
题意简述
一共有 \(n\) 次操作,第 \(k\) 次操作(\(1\le k\le n\))成功的概率是 \(p_i\)。成功记作 \(1\),失败记作 \(0\),那么所有操作的结构依次连起来就可以得到一个 \(0/1\) 串。在这个串中,每个极大的、连续的 \(X\) 个 \(1\) 会对分数产生 \(X^3\) 的贡献,每个全为 \(1\) 的子段的贡献线性累加。
求:贡献总和的期望 \(E\)。
范围:\(1\le n\le10^5\)。
思路
考虑线性递推。
-
我们把以位置 \(k\) 结尾的一串 \(1\) 的长度记为 \(X_k\)。
-
让我们先试着求长度一次方的期望。我们把 \(X_k\) 的期望记为 \(E(X_k)\)。在这个位置 \(k\),我们向串尾追加第 \(k+1\) 个操作结果,有两种情况:
-
有 \(p_{k+1}\) 的概率第 \(k+1\) 次操作成功。成功后 \(X_{k+1}\) 的期望为 \(E(X_k)+1\)。(也就是 \(1\) 串的长度 \(+1\))
-
另外 \(1-p_{k+1}\) 的概率第 \(k+1\) 次操作失败。失败后串尾就没有 \(1\) 了,所以 \(E(X_k)=0\)。
所以:
\[E(X_{k+1})=p_{k+1}E(X_k+1)+(1-p_{k+1})\times0. \]由期望的线性性,
\[E(X_k+1)=E(X_k)+E(1)=E(X_k)+1, \]这里常数 \(C\) 的期望 \(E(C)\) 当然就是 \(C\) 了,不然还能有别的取值吗。进一步化简,得:
\[E(X_{k+1})=p_{k+1}[E(X_k)+1].(1) \] -
-
类似地,记 \(X_k^2\) 的期望为 \(E(X_k^2)\)。我们尝试求一下长度二次方的期望的递推式:
\[E(X_{k+1}^2)=p_{k+1}E[(X_k+1)^2]+(1-p_{k+1})\times0 \]请注意: 此处是 \(E[(X_k+1)^2]\) 而不是 \([E(X_k)+1]^2\),写成后面那个就推不出来了。(而且也是错的)。
化简 \(E[(X_k+1)^2]\),依旧是利用期望的线性性:
\[E[(X_k+1)^2]=E(X_k^2+2X_k+1)=E(X_k^2)+2E(X_k)+1. \]化简整个式子:
\[E(X_{k+1}^2)=p_{k+1}[E(X_k^2)+2E(X_k)+1].(2) \]
-
类似地,记 \(X_k^3\) 的期望为 \(E(X_k^3)\)。那么长度三次方的期望的递推式:
\[E(X_{k+1}^3)=p_{k+1}E[(X_k+1)^3]+(1-p_{k+1})\times0, \]化简(过程略):
\[E(X_{k+1}^3)=p_{k+1}[E(X_k^3)+3E(X_k^2)+3E(X_k)+1]. \]
期望推过瘾了,那我们怎么求答案呢?我们假设 \([1,k]\) 上的分数的期望为 \(E_k\),那么\(E_n\) 就是答案了,接下来考虑如何递推:
-
有 \(p_{k+1}\) 的概率第 \(k+1\) 次操作成功,那么 \(1\) 串继续累加,\(E_{k+1}=p_{k+1}[E_k+3E(X_k^2)+3E(X_k)+1]\)。这一部分和长度三次方的期望是一样的(只不过我们把 \(E(X_k^3)\) 换成了 \(E_k\))。
-
另外 \(1-p_{k+1}\) 的概率第 \(k+1\) 次操作失败,那么期望不变, \(E_{k+1}=E_{k}\)。注意,这里就和上面长度三次方的递推式不同了。因为上面我们规定 \(X_k\) 是以 \(k\) 结尾的 \(1\) 串的长度,如果操作失败,长度和期望都清零了。但是这里我们是要统计累积的期望分数,所以期望不清零。
加起来就得到:
结合 \((1)(2)(3)\),就容易设计递推了。
补充
请注意: \(E(X_k^3)\not=[E(X_k)]^3\),即三次方的期望 \(\not=\) 期望的三次方。这也解释了我们为什么要大费周章地推式子,而不是直接推出 \(E(X_n)\) 然后取三次方。
为了避免这个混淆,上面我不辞辛苦地把一个个期望都严格写成 \(E(X_k)\) 而不是 \(E(k)\)。TwT