[Codeforces 235B]Let's Play Osu!

Description

题库链接

有一个长度为 (n) 的 "XO" 序列，其中第 (i) 个位置 "O" 出现的概率为 (p_i) 。一个序列的价值为这个序列中每段连续出现的 "O" 的长度的平方。求价值期望。

(1leq nleq10^5)

Solution

假设序列中所有 "O" 出现的概率都是 (1) 。那么考虑第 (i) 位新加的贡献为 (i^2-(i-1)^2=2i-1) 。

所以我们可以考虑计算以每一位结尾的期望纯 "O" 的长度，再用贡献法相加即可。

我们假设 (f_i) 表示以 (i) 位结尾的时候期望长度。显然 (f_i=(f_{i-1}+1)cdot p_i+(1-p_i)cdot 0) ，加号前面表示该位变为 "O" ，接上之前的 "O" ；后边的则表示这一位变为 "X" ，则新的长度为 (0) 。

对于每一位，其对答案的贡献是 (p_icdot(2(f_{i-1}+1)-1)) 。注意的是因为新增长度也是有概率的，所以不能用 (2f_i-1) 来算。

Code

//It is made by Awson on 2018.2.28
#include <bits/stdc++.h>
#define LL long long
#define dob complex<double>
#define Abs(a) ((a) < 0 ? (-(a)) : (a))
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) ((a) < (b) ? (a) : (b))
#define Swap(a, b) ((a) ^= (b), (b) ^= (a), (a) ^= (b))
#define writeln(x) (write(x), putchar('
'))
#define lowbit(x) ((x)&(-(x)))
using namespace std;
void read(int &x) {
    char ch; bool flag = 0;
    for (ch = getchar(); !isdigit(ch) && ((flag |= (ch == '-')) || 1); ch = getchar());
    for (x = 0; isdigit(ch); x = (x<<1)+(x<<3)+ch-48, ch = getchar());
    x *= 1-2*flag;
}
void print(int x) {if (x > 9) print(x/10); putchar(x%10+48); }
void write(int x) {if (x < 0) putchar('-'); print(Abs(x)); }

int n;
double p, ans, len;

void work() {
    read(n);
    for (int i = 1; i <= n; i++) {
    scanf("%lf", &p);
    len = (len+1)*p, ans += 2*len-p;
    }
    printf("%lf
", ans);
}
int main() {
    work(); return 0;
}