P1365 WJMZBMR打osu! / Easy
原题
一道不同寻常的期望\(dp\)题
我们定义\(f_i\)表示前\(i\)个数的答案，\(g_i\)表示前\(i\)个数的连续后缀\(o\)长度
可以得到转移：
\[f_i =
\begin{cases}
f_{i-1}+(g_{i-1}+1)^2-g_{i-1}^2 &(a_i='o') \\
f_{i-1} &(a_i='x') \\
f_{i-1} + \frac{(g_{i-1}+1)^2-g_{i-1}^2 + 0}{2} &(a_i='?') \\
\end{cases}
\]
\[g_i =
\begin{cases}
g_{i-1} + 1 &(a_i='o') \\
0 &(a_i='x') \\
\frac{g_{i-1}+1+0}{2} &(a_i='?') \\
\end{cases}
\]
最终复杂度\(O(n)\)