有一个由o,x,?组成的长度为n的序列，?等概率变为o,x，定义序列权值为连续o的长度o的平方之和，询问权值的期望，

解

注意到权值不是简单的累加关系，存在平方，所以我们需要变式，而递推的权值必须是连续的，于是我们得设\(g\)表示以x-1结尾的连续o的期望长度，设\(f[x]\)表示前x个的权值期望，设s[x]为x处的字符，因此我们不难有

\[if(s[x]==o)f[x]=f[x-1]+2g+1,g=g+1\]

\[if(s[x]==x)f[x]=f[x-1],g=0\]

\[if(s[x]==?)f[x]=f[x-1])+g+0.5,g=g/2+0.5\]

注意到数据范围缺失，于是开滚动数组即可。

参考代码：

#include 
    
     #include 
     
      #define il inline#define ri registerusing namespace std;double f[2],g[2];il void get(char&);int main(){    int n;char c;    bool now(false);    scanf("%d",&n);    while(n--){        get(c),now^=1;        switch(c){        case 'o':            f[now]=f[now^1]+2*g[now^1]+1;            g[now]=g[now^1]+1;            break;        case 'x':            f[now]=f[now^1],g[now]=0;            break;        case '?':            f[now]=f[now^1]+g[now^1]+0.5;            g[now]=g[now^1]/2+0.5;            break;        }    }printf("%.4lf",f[now]);    return 0;}il void get(char &c){    while(c=getchar(),c==' '||c=='\n'||c=='\r');}