自动搬运

查看原文

来自洛谷，原作者为

	feecle6418 **

搬运于2025-08-24 22:35:34，当前版本为作者最后更新于2023-02-28 11:00:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

最初的观察是可以认为 $N=1$，最后输出时答案乘上 $(N+1)\div 2$。以下都认为 $N=1$。

首先注意到，虽然询问顺序与 Toptree 的输出有关，但询问顺序与 Toptree 输出的期望无关。下面说明原因。

考察对 $a_x$ 进行的所有操作，采用以下方式计算期望。

首先枚举 $a_x$ 被做了哪些操作及其顺序，不妨设其按顺序被做了第 $b_1,b_2,\dots,b_k$ 次操作。

在这种情况下 $a_x$ 的终值期望是多少呢？发现，$a_x$ 的值期望只与最后一次赋值操作的位置有关。枚举这是第几次操作，可得答案是

$$F(k)=\dfrac{1}{2^{k}}k+\sum_{i=1}^k\dfrac{1}{2^{i}}i=2-\dfrac{1}{2^{k-1}} $$

枚举最后一次赋值操作是 $b_{k-i+1}$ 即得上式。前面那坨是不存在赋值操作的情况。

显然，上式与 $b$ 的具体值无关，在确定操作顺序的情况下，最终期望只与 $k$（总操作次数）有关。设 $B$ 为操作序列，最终答案可以写成

$$\sum_{B}\Pr(\texttt{the sequence of operations is }B)F(|B|) $$$$=\sum_{i=|B|}\Pr(\texttt{in total there are }i\texttt{ operations related to }a_x )F(i) $$

设某一次操作与 $a_x$ 有关的概率是 $p=\dfrac{x(n-x+1)}{n(n+1)\div 2}$，则上式为（$F(i)$ 显然易算，以下视为常数）

$$\sum_{i}F(i)p^i(1-p)^{q-i}\binom{q}i$$ $$=2\cdot \sum_{i}p^i(1-p)^{q-i}\binom qi-2\sum_{i}\left(\dfrac{p}{2}\right)^i(1-p)^{q-i}\binom qi $$$$=2-2\left(1-\frac p2\right)^q$$

用快速幂计算即可。时间复杂度 $O(m\log q)$。