自己只能想到O(n^2)的:
dp[i][j] 表示 以i结尾,长度为j的o串的概率,然后在每次遇到x的时候算分数.
正解是:
dp[i]表示前i个的答案,d[i]表示以i结尾的期望长度.
推的时候它用d[i]*d[i]-d[i-1]*d[i-1]来算新增的贡献,有点不明白为什么可以这样(平方的期望应该不等于期望的平方才对吧).
哪天问问jason_yu.
bzoj 3405 期望分数
原文：http://www.cnblogs.com/idy002/p/4579278.html
