#P3450. Tyvj1952 Easy

    ID: 2650 传统题 1000ms 512MiB 尝试: 1185 已通过: 619 难度: 4 上传者: 标签>难度分类普及+/提高-动态规划期望 DP概率与期望期望线性性构造与建模差分转化滚动数组CF1600概率期望我们都爱GYZ杯

Tyvj1952 Easy

Easy

题目描述

WJMZBMR 在玩 osu!。一次游戏包含 nn 次点击,每次点击要么成功,要么失败。把一段极大的连续成功点击称为一段连击。如果某段连击的长度为 aa,它贡献 a2a^2 分。整场游戏的得分是所有连击的得分之和。

例如,ooxxxxooooxxx 有两段连击,长度分别为 22 和 44,总得分为 22+42=202^2+4^2=20。

有些点击一定成功,以字符 o 表示。有些一定失败,以 x 表示。其余以 ? 表示,成功与失败的概率各为 12\frac{1}{2}。各个 ? 的结果相互独立。

求整场游戏得分的期望值。

输入格式

第一行包含一个整数 nn,1≤n≤3000001\le n\le 300000。

第二行为一个长度为 nn 的字符串,字符均为 o、x 或 ?。

输出格式

输出一行一个实数,四舍五入保留小数点后四位。

样例 #1

5
oo?xx
6.5000

样例解释

若 ? 成功,得分为 32=93^2=9。若它失败,得分为 22=42^2=4。两种情况各占一半,期望为 9+42=6.5\frac{9+4}{2}=6.5。

样例 #2

4
????
4.1250