我们记\(pw3_i\)表示前\(i\)个位置,结尾为\(i\)的最长全1子串的期望长度的立方。
如果我们钦定\(p_{n+1}=0\),那么答案\(=\sum_{i=1}^npw3_i\times(1-p_{i+1})\)。乘上\((1-p_{i+1})\)意思是这一位要在下一位为\(0\)的时候才有贡献。
设当前位置为\(i\)。
这一位有\(p_i\)的概率为1。那么考虑如何从\(pw3_{i-1}\)转移到\(pw3_i\)。
发现\((x+1)^3=x^3+3x^2+3x+1\)。
我们记\(pw2_i\)表示前\(i\)个位置,结尾为\(i\)的最长全1子串的期望长度的平方,\(pw1_i\)表示前\(i\)个位置,结尾为\(i\)的最长全1子串的期望长度。
那么\(pw3_i=(pw3_{i-1}+3pw2_{i-1}+3pw1_{i-1}+1)\times p_i\)
然后我们还要转移\(pw2\)和\(pw1\)。
同理,\((x+1)^2=x^2+2x+1\)。
所以\(pw2_i=(pw2_{i-1}+2pw1_{i-1}+1)\times p_i\)。
剩下一个就很简单了,\(pw1_i=(pw1_{i-1}+1)\times p_i\)。
做完了。
code:
#include<bits/stdc++.h>
using namespace std;
int n;
double p[100010],pw1[100010],pw2[100010],pw3[100010],ans;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i)scanf("%lf",&p[i]);
for(int i=1;i<=n;++i)pw1[i]=(pw1[i-1]+1)*p[i],pw2[i]=(pw2[i-1]+2*pw1[i-1]+1)*p[i],pw3[i]=(pw3[i-1]+3*pw2[i-1]+3*pw1[i-1]+1)*p[i],ans+=pw3[i]*(1-p[i+1]);
printf("%.1lf",ans);
return 0;
}