JZOJ 3468 OSU！题解

题目大意

一共有 \(n\) 次操作，每次操作只有成功与失败之分，成功对应 \(1\)，失败对应 \(0\)，\(n\) 次操作对应为 \(1\) 个长度为 \(n\) 的 \(01\)串。在这个串中连续的 \(x\) 个 \(1\) 可以贡献 \(x^3\) 的分数，这 \(x\)个 \(1\) 不能被其他连续的 \(1\) 所包含（也就是极长的一串 \(1\)，具体见样例解释）
现在给出 \(n\)，以及每个操作的成功率，请你输出期望分数，输出四舍五入后保留 \(1\) 位小数。

输入格式

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

输出格式

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

样例输入

3
0.5
0.5
0.5

样例输出

6.0

数据范围与提示

\(000\) 分数为 \(0\)，\(001\) 分数为 \(1\)，\(010\) 分数为 \(1\)，\(100\) 分数为 \(1\)，\(101\) 分数为 \(2\)，\(110\) 分数为 \(8\)，\(011\) 分数为 \(8\)，\(111\) 分数为 \(27\)，总和为 \(48\)，期望为 \(48/8=6.0\)
\(N\le100000\)

分析

• 我们先考虑一个简单的问题，如果连续 \(X\) 个 \(1\) 贡献的分数为 \(X\) 要怎么处理？其实很简单，我们考虑每多一个 \(1\) 最结果的贡献，这里因为连续长度从 \(x\) 增加到 \(x+1\)，得分也是加 \(1\)，而第 \(i\) 位为 \(1\) 的概率为 \(p_i\)，那么真正的贡献为 \(p_i\)，其实就是每个位置选取 \(1\) 的概率之和。
• 那么对与本题贡献值为 \(x^3\) 来说，也可以用同样的方法来考虑，设长度为 \(i\) 的 \(01\) 串的期望得分为 \(h[i]\)，那么 \(h[i+1]\) 怎么求？
  我们同样可以考虑增加一位对结果的贡献：
  • 如果该位为 \(0\)，肯定贡献为 \(0\)；
  • 如果该位为 \(1\)，那么这个 \(1\) 就要接在到第 \(i\) 位结尾连续的 \(x\) 个 \(1\) 的后面，变成长度为 \(x+1\) 的连续的 \(1\) 串，那么此时第 \(i+1\) 位上对结果的贡献为 \(\Delta=(x+1)^3-x^3=3x^2+3x+1\)
    最终的分数就是把每个 \(1\) 的贡献累加起来。因为第 \(i\) 位为 \(1\) 是有概率的，为 \(p_i\)，所以它真正对分数之和的贡献为 \(\Delta\times p_i\)。因此我们可以得到一个递推式 \(h[i+1]=h[i]+\Delta\times p_i\)。因为 \(\Delta\) 里面的 \(x\) 对应的是 \(01\) 串前 \(i\) 位结尾的连续 \(1\) 的长度的期望（可以理解为前 \(i\) 位的结尾 \(01\) 串的平均长度），所以我们还需要定义：
• \(f2[i]\) 表示前 \(i\) 为结尾连续 \(1\) 的长度的平方的期望
• \(f1[i]\) 表示前 \(i\) 为结尾连续 \(1\) 的长度的期望
  其中，\(f1[i+1]\) 我们可以这样理解，前 \(i\) 位结尾连续 \(1\) 的平均长度为 \(f1[i]\)，那么第 \(i+1\) 位有两种可能：
• \(0\)，那么此时连续 \(1\) 结尾长度为 \(0\)，概率为 \(1-p_{i+1}\)；
• \(1\)，那么此时连续 \(1\) 结尾长度为 \(f[i]+1\)，概率为 \(p_{i+1}\)。
  所以 \(f1[i+1]=0\times (1-p_{i+1})+(f1[i]+1)\times p_{i+1}=(f1[i]+1)\times p_{i+1}\)

再看 \(f2\)，因为 \((x+1)^2=x^2+2x+1\)，所以对于平方来说，当长度增加 \(1\)，实际增加量为 \(2x+1\)。如果放到 \(f2[i+1]\) 中，这里的 \(x\) 就对应前 \(i\) 位的结尾连续 \(1\) 的长度的期望，即 \(f1[i]\)。
因此，类似于上面的 \(f1\) 的求法，\(f2[i+1]=0\times (1-p_{i+1})+(f2[i]+2f1[i]+1)\times p_{i+1}=(f2[i]+2f1[i]+1)\times p_{i+1}\)。

综上所述，我们得到完整的递推式：

\[\begin{aligned} h[i]&=h[i-1]+(3f2[i]+3f1[i]+1)\times p_i\\ f2[i]&=(f2[i-1]+2f1[i-1]+1)\times p_i\\ f1[i]&=(f1[i-1]+1)\times p_i\\ \end{aligned} \]

根据这三个递推式，我们可以解决这道题了，代码很简单，略了。另外可以自己手模一下简单例子，看看是否跟上面的递推式一致