洛谷 P1654 OSU! 解题报告

P1654 OSU!

题目描述

osu 是一款群众喜闻乐见的休闲软件。

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

一共有\(n\)次操作，每次操作只有成功与失败之分，成功对应\(1\)，失败对应\(0\)，\(n\)次操作对应为\(1\)个长度为\(n\)的\(01\)串。在这个串中连续的 \(X\) 个 \(1\) 可以贡献 \(X^3\) 的分数，这\(x\)个\(1\)不能被其他连续的\(1\)所包含（也就是极长的一串\(1\)，具体见样例解释）

现在给出\(n\)，以及每个操作的成功率，请你输出期望分数，输出四舍五入后保留1位小数。

输入输出格式

输入格式：

第一行有一个正整数\(n\),表示操作个数。接下去\(n\)行每行有一个\([0,1]\)之间的实数，表示每个操作的成功率。

输出格式：

只有一个实数，表示答案。答案四舍五入后保留1位小数。

---

其实有一个卷积的想法，注意到如果普通的\(f_{i,0/1}\)转移的话发现\(1\)的转移是\(1^3,2^3,\dots\)什么的和\(\prod p\)什么的错位的在弄，但是我猜会爆精度。

事实上这个题在求连续1长度的三次方的期望，考虑先求出连续1长度1次方和2次方的期望，然后递推过来

设\(a_i\)代表前\(i\)位第\(i\)位为\(1\)的长度的期望

\[a_i=p_i(a_{i-1}+1)
\]

即在末尾长度+1，成功的概率是\(p_i\)

然后\(b_i\)代表前\(i\)位第\(i\)位为\(1\)的长度的平方的期望

\[b_i=p_i(b_{i-1}+2a_{i-1}+1)
\]

因为期望是线性的，所以可以直接按式子\(x^2->x^2+2x+1\)延伸贡献

形象点理解，其实这个两个式子求的都是\(00\dots00111\dots11\)这样的东西的期望。

然后延伸到立方其实是差不多的，但是为了统计答案需要稍微变形一下，\(ans_i\)代表前\(i\)位的答案

\[ans_i=(ans_{i-1}+3b_{i-1}+3a_{i-1}+1)p_i+ans_{i-1}(1-p_i)
\]

\(ans_{i-1}=c_{i-1}+oth_{i-1}\)，事实上第一个式子应该这么拆开看，前面\(c_{i-1}\)是末尾极长\(1\)的答案，通过期望线性的方法和上面一样进行累加，\(oth_{i-1}\)的第\(i-1\)位是\(0\)，但它一样需要乘一下概率，后面的就是延长失败累加答案了。

化简一下式子就成了

\[ans_i=ans_{i-1}+(3b_{i-1}+3a_{i-1}+1)p_i
\]

---

Code:

#include <cstdio>

const int N=1e5+10;

double a[N],b[N],c[N];

int main()

{

    int n;scanf("%d",&n);

    for(int i=1;i<=n;i++)

    {

        double p;scanf("%lf",&p);

        a[i]=(a[i-1]+1)*p;

        b[i]=(b[i-1]+2*a[i-1]+1)*p;

        c[i]=c[i-1]+(3*b[i-1]+3*a[i-1]+1)*p;

    }

    printf("%.1lf\n",c[n]);

    return 0;

}

---

2019.1.13