AT_agc030_d [AGC030D] Inversion Sum

给定一个长度为 $N$ 的整数序列 $A_1,A_2,\ldots,A_N$。你需要依次进行 $Q$ 次操作。第 $i$ 次操作由两个整数 $X_i,Y_i$ 给出，你可以从以下两种操作中恰好选择一种执行： - 交换 $A_{X_i}$ 和 $A_{Y_i}$ 的值； - 什么都不做。 所有操作的执行方式共有 $2^Q$ 种。请你求出对于所有可能的操作方式，最终得到的序列的逆序对数之和，并对 $10^9+7$ 取模。 其中，序列 $P_1,P_2,\ldots,P_M$ 的逆序对数定义为满足 $1\leq iP_j$ 的整数对 $(i,j)$ 的个数。

输入从标准输入读入，格式如下： > $N$ $Q$ > $A_1$ $A_2$ $\ldots$ $A_N$ > $X_1$ $Y_1$ > $\vdots$ > $X_Q$ $Y_Q$

输出所有可能的最终序列的逆序对数之和对 $10^9+7$ 取模的结果。

## 限制条件 - $1\leq N\leq 3000$ - $0\leq Q\leq 3000$ - $0\leq A_i\leq 10^9\ (1\leq i\leq N)$ - $1\leq X_i,Y_i\leq N\ (1\leq i\leq Q)$ - $X_i\neq Y_i\ (1\leq i\leq Q)$ - 输入均为整数 ## 样例说明 1 所有可能的操作方式如下，共有 $4$ 种： - 第 $1$ 次和第 $2$ 次都什么都不做。最终序列为 $1,2,3$，逆序对数为 $0$。 - 第 $1$ 次什么都不做，第 $2$ 次交换。最终序列为 $3,2,1$，逆序对数为 $3$。 - 第 $1$ 次交换，第 $2$ 次什么都不做。最终序列为 $2,1,3$，逆序对数为 $1$。 - 第 $1$ 次和第 $2$ 次都交换。最终序列为 $3,1,2$，逆序对数为 $2$。 这几种情况下逆序对数之和为 $0+3+1+2=6$，输出 $6$。 由 ChatGPT 4.1 翻译