[文章目录]
Description
该你一个序列，要不为'x'要不为'o'。定义得分为每个极长的'o'长度的平方的和。然后有一些位置为？，表示o&x各有1/2的概率。询问得分的期望。序列长度<=300000
推了一篇的式子，然后发现状态直接哪一个变量存就行。
设L为含当前位向前极长的连续o的期望长度。ans为最终的答案。发现如果当前位为o，那么对答案的贡献就是2*L+1，如果为x，那么L=0。如果为？的话，就两边期望各取1/2
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
char st[301000];
double ans=0;
int main()
{
scanf("%d%s",&n,st+1); n++; st[n]='x';
double L=0;
for(int i=1;i<=n;i++)
{
if(st[i]=='x') L=0;
else if(st[i]=='o') ans+=2*L+1,L+=1.0;
else ans+=L+0.5,L=(L+1.0)/2;
}
printf("%.4lf",ans);
return 0;
}