AT_agc030_d题解

考虑统计每一对数

(i,j)

对答案的贡献，记

f_{i,j}

表示经过了若干次操作，每次操作执行或不执行，

a_i>a_j

的概率，假设某次操作交换

x

和

y

，且

x \lt y

，则这次操作只会影响所有的

f_{i,x},f_{x,i},f_{i,y},f_{y,i},1 \leq i \leq n

共

O(n)

个数，我们可以暴力的对这些值进行修改。

具体地，对

i\neq x

以及

i \neq y

的情况，有

f_{i,x} \larr inv2*f_{i,x}+inv2*f_{i,y} \\ f_{i,y} \larr inv2*f_{i,y}+inv2*f_{i,x} \\ f_{x,i} \larr inv2*f_{x,i}+inv2*f_{y,i} \\ f_{y,i} \larr inv2*f_{y,i}+inv2*f_{x,i}

以及

f_{x,y} \larr inv2*f_{x,y}+inv2*f_{y,x} \\ f_{y,x} \larr inv2*f_{y,x}+inv2*f_{x,y}

其中

inv2

表示

2

的乘法逆元。

最终的答案即为

ans=\sum_{i,j,i \lt j}f_{i,j}*2^q

文章操作