【题解】ARC111F Do you like query problems?

· · 题解

给出一种简单一点的推式子的方法。

先把求和转化成期望，发现每一位对答案的贡献都是独立的。对于第 i 位，在一次操作中被选中的概率为：

p_i=\frac{i(n-i+1)}{\frac{n(n+1)}{2}}

考虑不同的操作对序列的影响。对于修改操作，将取 \max 和取 \min 一起考虑，其效果等价于：有一半概率将一个数修改成 0\sim m-1 中任意一个数，还有一半概率保持不变。设 a_{x,y} 为第 x 位第 y 次操作后的数的期望。则：

\begin{aligned} a_{x,0}&=0\\ a_{x,y}&=\frac{p_im}{2m+1}\cdot\frac{m-1}{2}+\left(1-\frac{p_im}{2m+1}\right)a_{x,y-1} \end{aligned}

设 r_i=1-\dfrac{p_im}{2m+1}，推出通项得：

a_{x,y}=\frac{1}{2}(m-1)(1-r_x^y)

最后的答案为：

\sum_{x=1}^n\frac{p_x}{2m+1}\sum_{y=0}^{q-1}a_{x,y}=\sum_{x=1}^n\frac{p_x}{2m+1}\cdot\frac{m-1}{2}\left(q-\frac{r_x^q-1}{r_x-1}\right)

时间复杂度 \mathcal{O}(n\log q)。代码非常简单，就不放了。