inline">\(l_p,r_p,c_p\)，执行第

inline">\(b_i\gets\max(b_i,c_p)\)。

每次会等概率随机地选择一个操作执行，求使得对于每个

inline">\(\mathbb{E}[\max\limits_{1\leq

i\leq

inline">\(\sum\limits_{S\subseteq

[n]}(-1)^{|S|-1}\mathbb{E}[\min\limits_{i\in

inline">\(\mathbb{E}[\min\limits_{i\in

S}t_i]\)，设有

S\cap[l_p,r_p],c_p<a_i\)，则可以列出式子：

S}t_i]&=\sum_{x=1}^{+\infty}\left(\frac

{cnt_S}m\right)^{x-1}\frac{(m-cnt_S)x}m\\

&=\sum_{x=1}^{+\infty}\frac{cnt_S^{x-1}(m-cnt_S)x}{m^x}\\

\end{align*}

inline">\(\sum\limits_{S\subseteq

[n]}(-1)^{|S|-1}\dfrac{m}{m-cnt_S}\)。

class="math

inline">\(w_i=\sum\limits_{S\subseteq

[n]}[cnt_S=i](-1)^{|S|-1}\)，那么答案就是

inline">\(\sum\limits_{i=0}^{m-1}w_i\dfrac

inline">\(h_i=\begin{cases}a_i-1&i\in

S\\+\infty

inline">\([l_p,r_p]\)，则它们有贡献当且仅当

inline">\(x>i\)：

class="math

inline">\(a_p=i+1\)，则我们要钦定

inline">\(f_{i,l,l-1,0}=1\)。

对于每个区间

inline">\(f_{n,l,r,C}=1\)，其中

inline">\(\sum\limits_{i=0}^{m-1}-f_{0,1,n,i}\dfrac{m}{m-i}\)。

直接做时间复杂度为

inline">\(\mathcal{O}(n^3m^2)\)，空间上需要把

inline">\(\mathcal{O}(n^2m)\)。

感觉随便写都能过。

当然可以进一步优化。

发现瓶颈在于第二种转移，套路地构造出多项式

inline">\(F_{i,l,r}(x)=\sum\limits_{j=0}^m

f_{i,l,r,j}x^j\)，那么第二种转移就是令

inline">\(\mathcal{O}(n^3m)\)

暴力算出

inline">\(\mathcal{O}(n^3m)\)。

class="post-meta-container">