期望DP学习记录_高次期望

luogu1654

一个01串中每个长度为\(X\)的全1子串可贡献\(X^3\)的分数。

给出n次操作的成功率（在01串后附加1的概率）\(p[i]\)，求分数的期望。

设\(a[i]\)表示前i位中第i位为1的长度的期望：

\(a[i]=(a[i−1]+1)×p[i]\)

即为在i-1的末尾加一个概率为\(p[i]\)出现的1

设\(b[i]\)表示前i位中第i位为1的长度的平方的期望，\((x+1)^2=x^2+2x+1\),故

\(b[i]=(b[i−1]+2×a[i−1]+1)×p[i]\)

同理，设\(c[i]\)表示前i位中第i位为1的长度的立方的期望：(\((x+1)^3=x^3+3x^2+3x+1\))

\(c[i]=(c[i−1]+3×b[i−1]+3×a[i−1]+1)×p[i]\)

但本题求的是前n位（而不是第n）的得分期望，故

\(f[i]=(f[i−1]+3×b[i−1]+3×a[i−1]+1)×p[i]+f[i-1]×(1-p[i])\)

\(=f[i-1]+(3×b[i−1]+3×a[i−1]+1)×p[i])\)

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

const int N=100005;
double a[N],b[N],f[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]+a[i-1]*2+1)*p;
		f[i]=f[i-1]+(3*b[i-1]+3*a[i-1]+1)*p;
	}
	printf("%.1lf",f[n]);
	return 0;
}