「BZOJ 4318」OSU! - 概率与期望

我们可以把 osu! 的规则简化与改编成以下的样子:

一共有 n n 次操作,每次操作只有成功与失败之分,成功对应 1 1 ,失败对应 0 0 n n 次操作对应为 1 1 个长度为 n n 的 01 串。在这个串中连续的 x x 1 1 可以贡献 x3 x ^ 3 的分数,这 x x 1 1 不能被其他连续的 1 1 所包含(也就是极长的一串 1 1 )。

现在给出 n n ,以及每个操作的成功率,请你输出期望分数。

链接

BZOJ 4318

题解

f(i) f(i) 表示前 i i 次操作后的期望得分,p(i) p(i) 表示第 i i 次操作成功的概率。

考虑连续 1 1 的长度 x x 的变化,如果第 i i 次成功,则 xi=xi1+1 x_i = x_{i - 1} + 1 ,考虑其对得分 x3 x ^ 3 的影响。

(x+1)3x3=3x2+3x+1 (x + 1) ^ 3 - x ^ 3 = 3x ^ 2 + 3x + 1

根据期望的线性性,我们只需要求出 Ex2 E_{x ^ 2} Ex E_x ,即可得到

E(x+1)3x3=3Ex2+3Ex+1 E_{(x + 1) ^ 3 - x ^ 3} = 3E_{x ^ 2} + 3E_x + 1

乘上成功的概率,即为该次操作的期望分数增量(相对于第 i1 i - 1 次)。

f(i)=f(i1)+(3Ex2(i)+3Ex(i)+1)×p(i) f(i) = f(i - 1) + (3E_{x ^ 2}(i) + 3E_x(i) + 1) \times p(i)

考虑如何维护 Ex2(i) E_{x ^ 2}(i) Ex(i) E_x(i) ,仍旧是考虑期望的线性性,将式子展开。

首先,显然

Ex+1=Ex+1 E_{x + 1} = E_x + 1

p(i) p(i) 的概率比上一次操作多 1 1 次,有 1p(i) 1 - p(i) 的概率直接成为 0 0 ,即

Ex(i)=(Ex(i1)+1)×p(i) E_x(i) = (E_x(i - 1) + 1) \times p(i)

类似的,有

E(x+1)2=Ex2+2Ex+1 E_{(x + 1) ^ 2} = E_{x ^ 2} + 2E_{x} + 1

Ex2(i)=Ex2(i1)+2Ex(i1)+1 E_{x ^ 2}(i) = E_{x ^ 2}(i - 1) + 2E_{x}(i - 1) + 1

至此,Ex2(i) E_{x ^ 2}(i) Ex(i) E_{x}(i) f(i) f(i) 均可在线性时间内递推得到。

代码

#include <cstdio>
#include <cmath>

const int MAXN = 100000;

int n;
double p[MAXN + 1], f[MAXN + 1];
double ex1[MAXN + 1], ex2[MAXN + 1];

inline void dp() {
    f[0] = 0;
    for (int i = 1; i <= n; i++) {
        ex1[i] = (ex1[i - 1] + 1) * p[i];
        ex2[i] = (ex2[i - 1] + 2 * ex1[i - 1] + 1) * p[i];
        double t = (3 * ex2[i - 1] + 3 * ex1[i - 1] + 1) * p[i];
        f[i] = f[i - 1] + t;
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%lf", &p[i]);

    dp();

    printf("%.1lf\n", floor(f[n] * 10 + 0.5) / 10);

    return 0;
}