[bzoj 4318] OSU!

对于一个 01 串, 极大连续 x 个 1 加 x^3 分. 给出长度 n 和每个位置出现 1 的概率, 求该 01 串的期望得分, 保留1位小数. (n ≤ 10^5) 一段段地考虑不好做......由期望的线性性质, 我们可以分开考虑每个位置的贡献. 设 对答案的增加量为 , 前缀 末尾连续 1 的数目为 , 则 不一定相等, 但是 作为随机变量, 它的运算是正常的.

用 全期望公式 + 期望的线性性质 维护 , 并更新答案.

int main()
{
	int n;
	double x = 0, y = 0, ans = 0, p;
	scanf("%d", &n);
	rep (i, 0, n)
	{
		scanf("%lf", &p);
		ans += (3*x + 3*y + 1) * p;
		y = (y + 2*x + 1) * p;
		x = (x + 1) * p;
	}
	printf("%.1f\n", ans);
	return 0;
}