题意
给出一个长度为(n)的随机序列,进行(q)次操作,每次操作等概率选择一个区间((i,j)),将区间内的元素修改为区间内的最大值。求最后每个元素的期望( imes (frac{(n+1)n}{2})^q)。(n,qle 400)
做法一
令(sum_{i,j})为第(i)个位置最后为第(j)个初始元素的值的方案数,那(ans_i=sumlimits_{k=1}^n a_k sum_{i,k})
考虑每个元素对序列上各个位置的贡献,(i)能贡献的极大区间([L,R]),满足其是区间内的最大值。
单独考虑这个位置,令其为(now),令(f_{i,j,k})为前(i)次操作后恰好([j,k])小于(a_{now})的方案数,边界为(f_{0,L,R}=1)
[f_{i,l,r}=sum_{u=L}^{l-1}f_{i-1,u,l}*(u-1)+sum_{u=r+1}^R f_{i-1,l,u}*(n-u)+f_{i-1,l,r}*(cnt_{l-1}+cnt_{r-l+1}+cnt_{n-r})
]
其中(cnt_i=frac{i(i-1)}{2})
(f_q)可以用前缀和在(q imes len^2)的时间算出来
因为序列是随机的,跑得过
做法二
令(g_x)为(i)位置最终(le x)的方案数,(ans_i=sumlimits_x x(g_x-g_{x-1}))
将原序列离散化,(ans_i=sumlimits_{j=1}^{tot}v_{j}(g_{v_j}-g_{v_{j-1}})),若令(v_{tot+1}=0),则(ans_i=sumlimits_{j=1}^{tot}g_{v_j}(v_j-v_{j+1}))
观察到做法一里的(f)仅边界不同,换言之,枚举所有区间,该区间能对边界产生的贡献为(sumlimits_{j=max{a_l,...,a_r}}^{min(a_{l-1},a_{r+1})-1}(v_{j}-v_{j+1}))((a_0=a_{n+1}=tot+1))
(O(q imes n^2))