夢に僕らで帆を張って
来るべき日のために夜を超え

标签 期望 下的文章

September 26, 2019

洛谷P1654 OSU!

题意给出一个$01$串,第$i$位上有$p_i$的概率为$1$,否则为$0$极长的连续$x$个$1$贡献为$x^3$,求期望总贡献数据范围:$1 \le N \le 100000$题解若前面已有$x$个连续$1$,当前位也为$1$,增加的贡献为$$(x+1)^3-x^3=3x^2+3x+1$$现在我们加上概率,以$f[i]$表示前$i$位的期望,但是此时我们无法表示$2$次方项和$1$次方项...