P8057

· · 题解

最初的观察是可以认为 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)。