1. 题目

传送门= ̄ω ̄=

2. 题解

又一道XZY不会的简单概率期望题。

首先可以轻松算出以$x$结尾的极大连续1的期望长度$g _ x$

$g _ x=p _ x \times (g _ {x – 1} + 1)$

$p _ x$表示在$x$这个位置打出1的概率

然后我们要注意到:

期望的平方不等于平方的期望

因为这里的期望中的两个事件是相关的(它们是同一件事情肯定相关呀),所以期望与概率不满足单纯的乘法关系。

那怎么办算期望长度的三次方呢?

连续长度为$l$的期望是$E(l)$,而我们要求的是$E(l ^ 3)$,我们先求出$E(l ^ 2)$吧。

设$E[(l + 1) ^ 2] = E(l) + \Delta$

则:

$\Delta = E[(l + 1) ^ 2] – E(l)$
$=E[(l + 1) ^ 2 – l]$
$=E(l ^ 2 + 2l + 1 – l)$
$=E(l ^ 2 + l + 1)$
$=E(l ^ 2) + E(l) + 1$

即:

$E[(l + 1) ^ 2] = E(l ^ 2) + 2 E(l) + 1$

也就是说,我们设$h _ x$为以$x$结尾的极大连续1的长度的平方的期望

有:

$h _ x = p _ x \times (h _ {x – 1} + 2 g _ {x – 1} + 1)$

接着我们再求出$E(l ^ 3)$:

设$E[(l + 1) ^ 3]=E(l ^ 2) + \Delta$

则:

$\Delta = E[(l + 1) ^ 3] – E(l ^ 2)$
$=E[(l + 1) ^ 3 – l ^ 2]$
$=E(l ^ 3 + 3 l ^ 2 + 3 l + 1 – l ^ 2)$
$=E(l ^ 3 + 2l ^ 2 + 3 l + 1)$
$=E(l ^ 3) + 2 E(l ^ 2) + 3 E(l) + 1$

即:

$E[(l + 1) ^ 3] = E(l ^ 3) + 3 E(l ^ 2) + 3 E(l) + 1$

也就是说,我们设$f _ x$为以$x$结尾的极大连续1的长度的三次方的期望

有:

$f _ x = p _ x \times (f _ {x – 1} + 3 h _ {x – 1} + 3 g _ {x – 1} + 1)$

然后这题就做完惹。。。答案就是$f _ n$

(另外还有简化版的这一题,参见Easy BZOJ – 3450

(另另外还有简化版的这一题,参见CF235B Let’s Play Osu!

代码:

#include <bits/stdc++.h>

#define NS (100005)

using namespace std;

int n;

double p[NS], g[NS], h[NS], f[NS];

int main(int argc, char const* argv[])
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i += 1) scanf("%lf", &p[i]);
    for (int i = 1; i <= n; i += 1)
    {
        g[i] = p[i] * (g[i - 1] + 1);
        h[i] = p[i] * (h[i - 1] + 2 * g[i - 1] + 1);
        f[i] = p[i] * (f[i - 1] + 3 * h[i - 1] + 3 * g[i - 1] + 1)
            +(1 - p[i]) * f[i - 1];
    }
    printf("%.1f\n", f[n]);
    return 0;
}
分类: 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *