\(\\\)
\(Description\)
一共进行\(N\)次操作，生成一个长度为\(N\)的\(01\)序列，成功对应\(1\)，失败对应\(0\)，已知每一次操作的成功率\(p_i\)。
在这个序列中连续且极长的\(X\)个\(1\)可以贡献\(X^2\)的分数，求期望总分。
- \(N\in [1,10^5]\)
\(\\\)
\(Solution\)
考虑增量的思路很可以啊。长度平方的期望并不等于期望长度的平方。所以需要直接考虑长度平方的期望变化。
当长度从\(X\)增加到\(X+1\)，\(\Delta X^2=(X+1)^2-X^2=2X+1\)，所以维护答案只需要考虑长度的期望。
考虑一次的答案期望\(x_1[i]\)表示到第\(i\)个位置为止的长度期望，有\(x_1[i]=(x_1[i-1]+1)\times p_i\)，代表继承上一个为止的期望长度会\(+1\)，但保证第\(i\)位合法，需要乘上\(p_i\)。
-
然后到第\(i\)个位置的平方期望就可以转移自第\(i-1\)个位置，注意增量是有概率的。
\[ans[i]=ans[i-1]+(2x_1[i]+1)\times p_i
\]
\(\\\)
\(Code\)
#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define N 300010
#define R register
#define gc getchar
using namespace std;
int n;
double p[N],x1[N],ans[N];
inline double calc(char x){
return x=='x'?0.0:(x=='o'?1.0:0.5);
}
int main(){
scanf("%d",&n);
char c=gc();
while(c!='o'&&c!='x'&&c!='?') c=gc();
p[1]=calc(c);
for(R int i=2;i<=n;++i) p[i]=calc(gc());
for(R int i=1;i<=n;++i){
x1[i]=(x1[i-1]+1)*p[i];
ans[i]=ans[i-1]+(x1[i-1]*2+1)*p[i];
}
printf("%.4lf",ans[n]);
return 0;
}
\(\\\)
\(Extra\)
得分改为\(X^3\)，求分数的期望。
\(\\\)
\(Solution\)
同样考虑增量，有\(\Delta X^3=(X+1)^3-X^3=X^3+3X^2+3X+1-X^3=3X^2+3X+1\)
-
于是维护\(x_1[i]\)代表长度的期望，\(x_2[i]\)表示长度平方的期望，有：
\[x_1[i]=(x_1[i-1]+1)\times p_i
\]\[x_2[i]=x_2[i-1]+2x_1[i]+1\times p_i
\] 更新答案方式相同，有\(ans[i]=ans[i-1]+(3x_2[i]+3x_1[i]+1)\times p_i\)。
解释一下\(ans[i-1]\)的部分，它代表的是前一位置的答案，这一位置是否对答案有贡献是有概率的，而增量是后面括起来的部分。
\(\\\)
\(Code\)
#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define N 100010
#define R register
#define gc getchar
using namespace std;
inline int rd(){
int x=0; bool f=0; char c=gc();
while(!isdigit(c)){if(c=='-')f=1;c=gc();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc();}
return f?-x:x;
}
inline double rdd(){
double x=0,base=1; bool f=0; char c=gc();
while(!isdigit(c)){if(c=='-')f=1;c=gc();}
while(isdigit(c)){x=x*10+(c^48);c=gc();}
if(c=='.'){
c=gc();
while(isdigit(c)){x+=(base/=10)*(c^48);c=gc();}
}
return f?-x:x;
}
int n;
double p[N],x1[N],x2[N],ans[N];
int main(){
n=rd();
for(R int i=1;i<=n;++i) p[i]=rdd();
for(R int i=1;i<=n;++i){
x1[i]=(x1[i-1]+1)*p[i];
x2[i]=(x2[i-1]+x1[i-1]*2+1)*p[i];
ans[i]=ans[i-1]+(x2[i-1]*3+x1[i-1]*3+1)*p[i];
}
printf("%.1lf",ans[n]);
return 0;
}