题意
给出一个$01$串,第$i$位上有$p_i$的概率为$1$,否则为$0$
极长的连续$x$个$1$贡献为$x^3$,求期望总贡献
数据范围:$1 \le N \le 100000$
题解
若前面已有$x$个连续$1$,当前位也为$1$,增加的贡献为$$(x+1)^3-x^3=3x^2+3x+1$$
现在我们加上概率,以$f[i]$表示前$i$位的期望,但是此时我们无法表示$2$次方项和$1$次方项,因为它们也是期望,需要以相似的方式计算
以$a[i]$表示第$i$位为$1$,前$i$位中的全$1$子串的长度的期望值,有$$a[i]=(a[i-1]+1) \cdot p[i]$$容易理解,在长$a[i-1]$的子串后有$p[i]$的概率长度$+1$
同理,以$b[i]$表示第$i$位为$1$,前$i$位中的全$1$子串的长度$^2$的期望值,有$$b[i]=(b[i-1]+1) \cdot p[i]$$是这样吗?不对,注意$b[i]$已经带上了平方,对应$$(x+1)^2=x^2+2x+1$$中的平方项,因此$$b[i]=(b[i-1]+2a[i-1]+1) \cdot p[i]$$
下面就可以计算答案$f[i]$了,因为题目要求求出期望总贡献,所以与上面两个数组的定义不同,按照最开始的式子计算即可$$f[i]=f[i-1]+(3b[i-1]+3a[i-1]+1) \cdot p[i]$$
最后输出$f[n]$
代码:
#include<iostream>
#include<cstdio>
using namespace std;
const int N=100000+10;
int n;
double p[N];
double a[N],b[N],f[N];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%lf",&p[i]);
a[i]=(a[i-1]+1)*p[i];
b[i]=(b[i-1]+2*a[i-1]+1)*p[i];
f[i]=f[i-1]+(3*b[i-1]+3*a[i-1]+1)*p[i];
}
printf("%.1f",f[n]);
return 0;
}