数论 期望 lgCF235B题解

简单期望/fad

题意明确,不说了。

对于高次期望,一个套路的方法是维护低次期望(?)

考虑 dp,设 \(dp1[i]\) 为前 \(i\) 次点击中 所有连续的 \(O\) 的长度之和,\(dp2[i]\) 为前 \(i\) 次点击中 所有连续的 \(O\) 的长度的平方和

很明显有:\(dp1[i]=(dp1[i-1]+1]) \times p[i]\)

然后能发现,dp2 其实就是 \(\sum E(len^2)\)

而:\(E((len+1)^2) = E(len^2 + 2 \times len +1) = E(len^2) + 2 \times E(len) + 1\)

但是由于有 p 的概率,再加上这只是 这一段的长度的平方 的期望,所以剩下 1-p 的概率,长度为 dp2[i-1]。

综合起来:

\[dp1[i]=p[i] \times (dp1[i-1]+1) \]

\[dp2[i]=dp2[i] + p[i] \times (2 \times dp2[i-1] +1) \]

然后可以滚动“数组”,使得空间为常数。

code:

#include<cstdio>
const int M=1e5+5;
double p,dp1,dp2;
int n;
signed main(){
    int i;
    scanf("%d",&n);
    for(i=1;i<=n;++i){
        scanf("%lf",&p);
        dp2+=(2*dp1+1)*p;
        dp1=(dp1+1)*p;
    }
    printf("%.15lf",dp2);
}
上一篇:动态规划3:连续子数组类问题


下一篇:leetcode【困难】132、分割回文串