Problem
Solution
- 期望的线性性质
设 (f[i]) 表示以 (i) 结尾的连续 (1) 区间的期望贡献（(x^1)），(g[i]) 表示以 (i) 结尾的连续 (1) 区间的期望贡献（(x^2))，则有：
[f[i]=p_i(f[i-1]+1)
]
[g[i]=p_i(g[i-1]+2f[i-1]+1)
]
（因为 ((x+1)^2=x^2+2x+1)）
类似的，可以设 (h[i]) 表示以 (i) 结尾的连续 (1) 区间的期望贡献（(x^3)），则有 (h[i]=p_i(h[i-1]+3g[i-1]+3f[i-1]+1))（因为 ((x+1)^3=x^3+3x^2+3x+1)）。由于不方便统计答案（直接加上去会有一些 ("1") 重复计算贡献），我们又可以根据期望的线性性质：
[E((x+1)^3) = E(x^3)+E(3x^2+3x+1)
]
计算每个位置上 (1) 的对答案增加的期望贡献。位置 (i) 上选 ("1") 对答案增加的期望贡献是：(p_i(3g[i-1]+3f[i-1]+1))，所以最后的答案是：
[sum p_i(3g[i-1]+3f[i-1]+1)
]
时间复杂度 (O(n))。
Code
Talk is cheap.Show me the code.
#include<bits/stdc++.h>
using namespace std;
inline int read() {
int x = 0, f = 1; char ch = getchar();
while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
while(ch>='0'&&ch<='9') { x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); }
return x * f;
}
const int N = 100007;
int n;
double p[N],f[N],g[N],h[N];
int main()
{
n = read();
for(int i=1;i<=n;++i) scanf("%lf",&p[i]);
double ans = 0;
for(int i=1;i<=n;++i) {
f[i] = p[i] * (f[i-1] + 1);
g[i] = p[i] * (g[i-1] + 2*f[i-1] + 1);
ans += p[i] * (3*g[i-1] + 3*f[i-1] + 1);
}
printf("%.1lf",ans);
return 0;
}
/*
3
0.5
0.5
0.5
6.0
*/
Summary
主要是期望的线性性质。注意想当然地加会重复计算贡献（自己手推一下会发现），要计算每个位置增加的期望贡献。