洛谷 P 1654 P1654 P1654 题解

数学期望这一块不太好，每次考试都想不出期望的题，打几道练习题练练手。

题目简述

给一个长度为 n n n的 01 01 01串的每一位为 1 1 1的概率,一个串的分数为其中每一个长度为 x x x的全 1 1 1串的长度的立方和,即 x 3 x^3 x3,求期望分数。（每一个 1 1 1只会作为一个全 1 1 1串的一部分而只被算一次)

解题方法

考虑先从分数为 x x x来下手，设 f i f_i fi​表示前 i i i个数中第 i i i位为 1 1 1的长度的期望，则有 f i = ( f i − 1 + 1 ) × p i f_i=(f_{i-1}+1) \times p_i fi​=(fi−1​+1)×pi​
考虑分数为 x 2 x^2 x2,设 g i g_i gi​表示前 i i i个数中第 i i i位为 1 1 1的长度的期望，则有 g i = ( g i − 1 + 2 f i − 1 + 1 ) × p i g_i=(g_{i-1}+2f_{i-1}+1)\times p_i gi​=(gi−1​+2fi−1​+1)×pi​
设分数为 x 3 x^3 x3时， h i h_i hi​表示前 i i i个数中分数的期望，则有
h i = h i − 1 × ( 1 − p i ) + ( h i − 1 + 3 g i − 1 + 3 f i − 1 + 1 ) × p i h_i=h_{i-1}\times(1-p_i)+(h_{i-1}+3g_{i-1}+3f_{i-1}+1)\times p_i hi​=hi−1​×(1−pi​)+(hi−1​+3gi−1​+3fi−1​+1)×pi​

代码

/******************************* Author:galaxy yr LANG:C++ Created Time:2019年09月14日 星期六 19时45分47秒 *******************************/
#include<iostream>
#include<cstdio>
#include<iomanip>
using namespace std;
const int maxn=1e5+10;
double a[maxn],b[maxn],f[maxn],p[maxn];
int n;
int main()
{
    //freopen("p1654.in","r",stdin);
    //freopen("p1654.out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>p[i];
    for(int i=1;i<=n;i++)
    {
        a[i]=(a[i-1]+1)*p[i];
        b[i]=(b[i-1]+2*a[i-1]+1)*p[i];
        f[i]=f[i-1]+(3*b[i-1]+3*a[i-1]+1)*p[i];
    }
    cout<<fixed<<setprecision(1)<<f[n]<<endl;
    return 0;
}