Luogu P1654 OSU!

题目描述

https://www.luogu.com.cn/problem/P1654

简要题意：给定 $n$，以及每个位置出现 $1$ 的概率 $p_i$，求整个 $01$ 串的期望价值

一个 $01$ 串的价值定义为极长的连续 $1$​ 的个数的三次方的和

$n\le 10^5$

Solution

我们考虑求每个位置作为起点的极长的连续 $1$ 的长度的三次方的期望

$f$ 表示一次方，$g$ 表示二次方，$h$ 表示三次方

其中 $f$ 维护的相当于 $\sum ip_i$，$g$ 维护的相当于 $\sum i^2p_i$，$h$ 维护的相当于 $\sum i^3p_i$，其中 $p_i$ 表示极长的连续 $1$ 的个数为 $i$ 的期望

转移时 $i$ 要变成 $(i+1)$，$i^2$ 要变成 $(i+1)^2$，$i^3$ 要变成 $(i+1)^3$，我们将平方和次方拆开可以得到递推式

最终答案等于 $ans=\sum_{i=1}^n h_i\times (1-p_{i-1})$

#include <iostream>
#include <iomanip>
#define maxn 100010
using namespace std;

int n;

double p[maxn];

double f[maxn], g[maxn], h[maxn];

int main() { 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n; double ans = 0; 
    for (int i = 1; i <= n; ++i) cin >> p[i];
    f[n] = g[n] = h[n] = p[n];
    for (int i = n - 1; i; --i) {
        f[i] = (f[i + 1] + 1) * p[i];
        g[i] = (g[i + 1] + 2 * f[i + 1] + 1) * p[i];
        h[i] = (h[i + 1] + 3 * g[i + 1] + 3 * f[i + 1] + 1) * p[i];
        ans += h[i + 1] * (1 - p[i]);
    } ans += h[1];
    cout << fixed << setprecision(1) << ans << "\n";
    return 0;
}