题解 CF1187F 【Expected Square Beauty】

**更好的阅读体验$\Longrightarrow$[My Blog](https://www.cnblogs.com/y2823774827y/p/11125415.html)** ## 题目 [CF1187F Expected Square Beauty](https://www.luogu.org/problemnew/show/CF1187F) ## 做法 $B(x)=\sum\limits_{i=1}^n I_i(x),I_i(x)=\begin{cases}1&x_i≠x_{i-1}\\0&x_i=x_{i-1}\end{cases}$ $E(B(x)^2)=E(\sum\limits_{i=1}^n I_i(x)\sum\limits_{j=1}^n I_j(x))=E(\sum\limits_{i=1}^n\sum\limits_{j=1}^n I_i(x)I_j(x))=\sum\limits_{i=1}^n\sum\limits_{j=1}^n E(I_i(x)I_j(x))$ 分类讨论一下$E(I_i(x)I_j(x))$ - $|i-j|>1$，这两个互不影响，则$E(I_i(x)I_j(x))=E(l_i(x))E(l_j(x))$ - $i=j$，因为$l(x)$函数仅为$1$和$0$，故$E(I_i(x)I_j(x))=E(l_i(x))$ - $|i-j|=1$详细讨论一下： $q_i=P(x_{i-1}=x_i)=E(x_{i-1}=x_i)=max(0,\frac{min(r_{i-1},r_i)-max(l_{i-1},l_i)}{(r_{i-1}-l_{i-1})(r_i-l_i)})$ $E(I_i(x))=1-q_i$ 则$E(I_i(x)I_{i+1}(x))=E(x_{i-1}≠x_i\And x_i≠x_{i+1})$ 故等于$1-q_i-q_{i+1}+E(x_{i-1}=x_i\And x_i=x_{i+1})$ 其中$E(x_{i-1}=x_i\And x_i=x_{i+1})=\frac{min(r_{i-1},r_i,r_{i+1})-max(l_{i-1},l_i,l_{i+1})}{(r_{i-1}-l_{i-1})(r_i-l_i)(r_{i+1}-l_{i+1})})$ 可以用$O(n)$算出来 ## [Code](https://www.cnblogs.com/y2823774827y/p/11125415.html)