题面
一序列(a), 对于每一个(i)均有(a_i)有(p_i)的几率为1, 否则为(0)
求: (a)中极长全(1)子序列长度三次方之和的期望
前置知识
- 基本期望(期望的概念总得会吧...
- 脑子
解法
可以设(f(x))表示 操作是否成功序列 (以下简称序列(a))前(x)位以(x)结尾极长全(1)子序列长度的期望, (g(x))表示(a)前(x)位以(x)结尾极长全(1)子序列长度平方的期望, (r(x))表示(a)前(x)位以(x)结尾极长全(1)子序列长度三次方的期望(以下简称"期望")， (h(x))表示(a)前(x)位极长全(1)子序列长度三次方之和的期望(即原题所求量)
为了叙述方便以下称原题给出的序列为(p)
由期望的定义(E(x) = sum v_ip_i), 有
[f(x) = (f(x-1)+1) imes p_i + 0 imes (1-p_i) = (f(x-1)+1) imes p_i
]
同样有:
[g(x) = (sqrt{g(x-1)}+1)^2 imes p_i + 0 imes (1-p_i) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
]
[ = (g(x-1)+2f(x)+1) imes p_i( ext{由定义易知}g(x)=f^2(x))
]
以及
[r(x) = (r(x-1)+3g(x)+3f(x)+1) imes p_i
]
然后有
[h(x) = h(x-1) imes (1-p_i) + (h(x-1)+r(x)-r(x-1)) imes p_i
]
这里稍微解释一下, 因为(h(x)+r(x))包括了以(x-1)结尾的期望两次((h(x))包括了([1, n-1])的期望, (r(x))包括了([lst, n])的期望(此处(lst)为以(x-1)(即(x), 因为开头不变)结尾的极长全(1)子序列的开头的期望)), 所以要减去([lst, n-1])的期望, 即(r(x-1))
展开原式得
[h(x) = h(x-1) + (3g(x-1)+3f(x-1)+1) imes p_i
]
(发现(p)完全没有用呢)
接下来暴力扫一遍序列(p)求出(f, g, h)即可, 时间复杂度为(O(n))
萌新求通过qwq
Code
/*code by tyqtyq*/
#include<bits/stdc++.h>
#define f(i,x,y) for(register int i=x, i##end=y; i<=i##end; ++i)
#define d(i,x,y) for(register int i=y, i##end=x; i>=i##end; --i)
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
using namespace std;
int read(int& x){x=0; int f=1, ch=getchar(); while(!isdigit(ch)) f=ch=='-'?-1:f, ch=getchar(); while(isdigit(ch)) x=x*10+ch-'0', ch=getchar(); return x*=f;}
int read(){int x=0, f=1, ch=getchar(); while(!isdigit(ch)) f=ch=='-'?-1:f, ch=getchar(); while(isdigit(ch)) x=x*10+ch-'0', ch=getchar(); return x*f;}
int max(int x, int y){return x>y?x:y;} int min(int x, int y){return x<y?x:y;}
#define _ 100005
#define read(X) scanf("%lf", &X)
#define print(X) printf("%.1lf
", X)
double px1[_], px2[_], ans[_], a[_];
int n;
int main(){
scanf("%d",&n); for(int i=1;i<=n;++i) scanf("%lf", &a[i]);
for(int i=1;i<=n;++i) {
px1[i]=(px1[i-1]+1)*a[i];
px2[i]=(px2[i-1]+2*px1[i-1]+1)*a[i];
ans[i]=ans[i-1]+(3*px2[i-1]+3*px1[i-1]+1)*a[i];
}
print(ans[n]);
return 0; //拜拜程序~
}