- 有一个长度为(n)的序列，其中第(i)个位置有(a_i)的概率为(1)。
- 问所有极长的连续的(1)的长度立方和的期望。
- (nle10^5)
期望
立方的期望显然不等于期望的立方，这种东西自己举几个例子就知道了。
考虑我们维护到第(i)个位置为止的答案为(ans_i)，连续长度期望为(A_i)，连续长度平方期望为(B_i)，连续长度立方期望为(C_i)。
一次期望的长度转移是显然的：
[A_i=a_i(A_{i-1}+1)
]
对于二次期望，考虑((x+1)^2=x^2+2x+1)，可以借助一次期望一同计算：
[B_i=a_i(B_{i-1}+2A_{i-1}+1)
]
知道二次期望，三次期望就同理了：
[C_i=a_i(C_{i-1}+3B_{i-1}+3A_{i-1}+1)
]
至于答案，由于它求的是极长连续段，所以我们有：（只有不连续了才能算答案）
[ans_i=ans_{i-1}+(1-a_i)C_{i-1}
]
但注意这样没有计算最后一个连续段，因此最终的答案为(ans_n+C_n)。
具体实现时没必要开数组。
代码：(O(n))
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 100000
#define DB double
using namespace std;
int n;
int main()
{
RI i;DB x,A=0,B=0,C=0,S=0;for(scanf("%d",&n),i=1;i<=n;++i)
scanf("%lf",&x),S+=(1-x)*C,C=x*(C+3*B+3*A+1),B=x*(B+2*A+1),A=x*(A+1);//注意转移的先后顺序
return printf("%.1lf
",S+C),0;//输出答案时要算上最后一个连续段
}