Problem:
 Score : 1000 points    Problem Statement You are given an integer sequence of length N : A_1,A_2,...,A_N . Let us perform Q operations in order.
The i -th operation is described by two integers X_i and Y_i . In this operation, we will choose one of the following two actions and perform it:   Swap the values of A_{X_i} and A_{Y_i}  Do nothing   There are 2^Q ways to perform these operations. Find the sum of the inversion numbers of the final sequences for all of these ways to perform operations, modulo 10^9+7 .  Here, the inversion number of a sequence P_1,P_2,...,P_M is the number of pairs of integers (i,j) such that 1\leq i < j\leq M and P_i > P_j .      Constraints  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)  All values in input are integers.         Input Input is given from Standard Input in the following format:  N  Q  A_1  :  A_N  X_1  Y_1  :  X_Q  Y_Q       Output Print the sum of the inversion numbers of the final sequences, modulo 10^9+7 .        Sample Input 1 3 2
1
2
3
1 2
1 3      Sample Output 1 6  There are four ways to perform operations, as follows:   Do nothing, both in the first and second operations. The final sequence would be 1,2,3 , with the inversion number of 0 .  Do nothing in the first operation, then perform the swap in the second. The final sequence would be 3,2,1 , with the inversion number of 3 .  Perform the swap in the first operation, then do nothing in the second. The final sequence would be 2,1,3 , with the inversion number of 1 .  Perform the swap, both in the first and second operations. The final sequence would be 3,1,2 , with the inversion number of 2 .   The sum of these inversion numbers, 0+3+1+2=6 , should be printed.       Sample Input 2 5 3
3
2
3
1
4
1 5
2 3
4 2      Sample Output 2 36       Sample Input 3 9 5
3
1
4
1
5
9
2
6
5
3 5
8 9
7 9
3 2
3 8      Sample Output 3 425

Solution (Python):
import sys
readline = sys.stdin.readline

MOD = 10**9+7
N, Q = map(int, readline().split())
A = [int(readline()) for _ in range(N)]

dp = [[0]*N for _ in range(N)]

tinv = pow(2, MOD-2, MOD)
for i in range(N):
    for j in range(N):
        if A[i] > A[j]:
            dp[i][j] = 1

for q in range(Q):
    x, y = map(int, readline().split())
    x -= 1
    y -= 1
    dxy = dp[x][y]
    dyx = dp[y][x]
    ix = [None]*N
    iy = [None]*N
    xi = [None]*N
    yi = [None]*N
    for i in range(N):
        r1 = (dp[i][x] + dp[i][y])*tinv%MOD
        ix[i] = r1
        iy[i] = r1
        r2 = (dp[x][i] + dp[y][i])*tinv%MOD
        xi[i] = r2
        yi[i] = r2
    for i in range(N):
        dp[x][i] = xi[i]
        dp[y][i] = yi[i]
        dp[i][x] = ix[i]
        dp[i][y] = iy[i]
    dp[x][y] = (dxy + dyx)*tinv%MOD
    dp[y][x] = dp[x][y]
    dp[x][x] = 0
    dp[y][y] = 0

res = 0
for i in range(N):
    for j in range(i+1, N):
        res = (res+dp[i][j])%MOD
print(res*pow(2, Q, MOD)%MOD)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

"""
・逆再生
・各時点に対して、「(Ai,Aj)がjが右になって終わる確率」を計算していく
"""

import numpy as np

MOD = 10**9 + 7

N,Q = map(int,readline().split())
data = list(map(int,read().split()))
A = np.array(data[:N])
it = iter(data[N:])
XY = list(zip(it,it))

dp = np.triu(np.ones((N,N),np.int64),1)

for x,y in XY[::-1]:
    x -= 1; y -= 1
    p=dp[x,y]; q=dp[y,x]; r=p+q
    if r&1:
        r += MOD
    r //= 2
    if r>=MOD:
        r -= MOD
    temp = dp[x]
    temp += dp[y]
    temp[temp&1==1] += MOD; temp//=2; temp[temp>=MOD] -= MOD; dp[y] = temp
    temp = dp[:,x]
    temp += dp[:,y]
    temp[temp&1==1] += MOD; temp//=2; temp[temp>=MOD] -= MOD; dp[:,y] = temp
    dp[x,y]=r; dp[y,x]=r; dp[x,x]=0; dp[y,y]=0

select = A[:,None]>A[None,:]
answer = (dp*select).sum()%MOD*pow(2,Q,MOD)%MOD
print(answer)

Solution (Python):
import sys
import numpy as np

n, q = list(map(int, input().split()))
MOD = 10 ** 9 + 7
INV2 = (MOD + 1) // 2
lines = sys.stdin.readlines()
aaa = np.fromiter(map(int, lines[:n]), dtype=np.int)
mat = (aaa.reshape(1, -1) < aaa.reshape(-1, 1)).astype(np.int64)

for line in lines[n:]:
    x, y = map(int, line.split())
    x -= 1
    y -= 1
    tmp = (mat[x, y] + mat[y, x]) * INV2 % MOD
    mat[x] = mat[y] = (mat[x] + mat[y]) * INV2 % MOD
    mat[:, x] = mat[:, y] = (mat[:, x] + mat[:, y]) * INV2 % MOD
    mat[x, x] = mat[y, y] = 0
    mat[x, y] = mat[y, x] = tmp

ans = int(np.triu(mat).sum() % MOD)
ans = (ans << q) % MOD
print(ans)

Solution (Python):
import sys

n, q = list(map(int, input().split()))
MOD = 10 ** 9 + 7
INV2 = (MOD + 1) // 2
lines = sys.stdin.readlines()
aaa = list(map(int, lines[:n]))
mat = [[0] * n for _ in [0] * n]
for i in range(n):
    for j in range(n):
        mat[i][j] = int(aaa[i] < aaa[j])

for line in lines[n:]:
    x, y = map(int, line.split())
    x -= 1
    y -= 1
    mat[x][y] = mat[y][x] = (mat[x][y] + mat[y][x]) * INV2 % MOD
    for i in range(n):
        if i == x or i == y:
            continue
        mat[x][i] = mat[y][i] = (mat[x][i] + mat[y][i]) * INV2 % MOD
        mat[i][x] = mat[i][y] = (mat[i][x] + mat[i][y]) * INV2 % MOD
    
    

ans = sum(sum(row[:i]) for i, row in enumerate(mat)) % MOD
ans = (ans << q) % MOD
print(ans)