题意

给出一个长度为 \(n\) 的 \(0/1\) 字符串,第 \(i\) 位为 \(1\) 的概率为 \(p_i\) ,串中连续的 \(X\) 个 \(1\) 可以贡献 \(X^3\) 的分数,求字符串总分的期望。

分析

我们只需要考虑第 \(i\) 位成功的情况,因为失败的话是不会对总的期望产生影响的。

如果第 \(i\) 位成功,那么后缀的 \(1\) 长度 \(x_i=x_{i-1}+1\) 。

我们考虑 \(+1\) 以后对总期望的贡献 \((x+1)^3-x^3=3x^2+3x+1\) ,也就是对于总的期望的增量 \(\Delta E=3E_{x^2}+3E_x+1\) ,即 \(f(i)=f(i-1)+\Delta E \cdot p[i]\) 。

那么我们现在只需要考虑如何计算 \(E_x\) 和 \(E_{x^2}\) 。

显然 \(E_x=(E_{x-1}+1)\cdot p\)

同样利用期望可加性展开 \(E_{x^2}=E_{(x-1)^2}+2E_{x-1}+1\) 。

于是 \(E_x\) , \(E_{x^2}\) 和 \(f(i)\) 都可以线性得到了。

 


发表评论

电子邮件地址不会被公开。 必填项已用*标注