Solution

设状态 $f_i$ 表示以 $i$ 结尾的段的期望长度的立方。则如果 $i$ 为 $1$，对这个长度为 $x$ 的段的答案贡献为 $3x^2+3x+1$，如果 $i$ 为 $0$ 则不产生贡献。根据期望的线性性质，我们需要计算 $x^2$ 和 $x$ 的期望。

状态 $g_i$ 表示期望长度的平方，状态 $h_i$ 表示期望长度，则 $f_i=p_i(f_{i-1}+3g_{i-1}+3h_{i-1}+1)$。

同理有 $g_i=p_i(2h_{i-1}+1)$，$h_i=p_i(h_{i-1}+1)$。

将 $f_i$ 的方程式稍加改动变为 $f_i=p_i(f_{i-1}+3g_{i-1}+3h_{i-1}+1)+(1-p_i)f_{i-1}$ 即变成答案。那么我们发现 $f_i$ 的含义发生了变动。考虑如果以 $i-1$ 结尾的期望长度为 $x$，那么产生的贡献的期望也就是 $3E(x^2)+3E(x)+1$，跟 $f_i$ 的含义其实是无关的。我们初始的方程只是忽略了 $i$ 可以为 $0$ 的情况，而对于 $g_i, h_i$ 两个状态我们必须忽略 $i$ 可以为 $0$ 的情况，否则无法为 $f_i$ 提供转移。

其它感觉都还好理解吧。

Code

// Code by ajcxsu
// Problem: osu

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+10;
double f[N], f2[N], ans;

int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0), cout.setf(ios::fixed), cout<<setprecision(1);
    int n;
    cin>>n;
    double p;
    for(int i=1;i<=n;i++) {
        cin>>p;
        f[i]=(f[i-1]+1)*p;
        f2[i]=(f2[i-1]+2*f[i-1]+1)*p;
        ans+=(3*f2[i-1]+3*f[i-1]+1)*p;
    }
    cout<<ans<<endl;
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-luogu-1654.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆