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