AT_agc030_d [AGC030D] Inversion Sum

[problemUrl]: https://atcoder.jp/contests/agc030/tasks/agc030_d 長さ $ N $ の整数列 $ A_1,A_2,...,A_N $ が与えられます。$ Q $ 回の操作を順に行います。 $ i $ 回目の操作は $ 2 $ つの整数 $ X_i,Y_i $ を用いて表され、以下の $ 2 $ つの操作からちょうど片方を選んで行います。 - $ A_{X_i} $ と $ A_{Y_i} $ の値を入れ替える - 何もしない 操作の行い方は $ 2^Q $ 通りあります。これらすべての操作の行い方に対する最終的な数列の反転数をすべて足し合わせたものを $ 10^9+7 $ で割ったあまりを求めてください。 ただし、数列 $ P_1,P_2,...,P_M $ の反転数とは、$ 1\leq\ i\ \ P_j $ を満たすような整数の組 $ (i,j) $ の個数です。

N/A

N/A

### 制約 - $ 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) $ - 入力はすべて整数である ### Sample Explanation 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 $ を出力します。