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



Sample input:
3 2
1
2
3
1 2
1 3


Sample output:
6

Submission status: Wrong Answer

Solution code:
N,Q=map(int,input().split())
A=[int(input()) for i in range(N)]
DP=[[0]*(N-i-1) for i in range(N-1)]
mod=10**9+7
for i in range(N-1):
  for j in range(len(DP[i])):
    if A[i]>A[i+j+1]:
      DP[i][j]=1
x,y=0,0
v=(10**9+8)>>1
for q in range(Q):
  x,y=map(int,input().split())
  x,y=x-1,y-1
  if x>y:
    x,y=y,x
  for i in range(x+1,y+1):
    if A[i]!=A[x]:
      DP[x][i-x-1]=v
  for i in range(x+1,y):
    if A[i]!=A[y]:
      DP[i][y-i-1]=v
P=0
for i in range(N-1):
  P+=sum(DP[i])
P=P*pow(2,Q,mod)%mod
print(P)

Submission status: Wrong Answer

Solution code:
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()*pow(2,Q,MOD)%MOD
print(answer)

Submission status: Time Limit Exceeded

Solution code:

"""
Writer: SPD_9X2
https://atcoder.jp/contests/agc030/tasks/agc030_d

Nが小さいな…
→ NC2のすべての組み合わせに関して、反転する場合は何通りあるか数える？
→クエリの数を考えたら無理じゃね？

各クエリを行った場合、全ての場合での反転数の合計はどうなるかをO(N)で求める？
→わりとありそう
→だとしたらdpっぽい

反転数 = それより右にある小さい要素の数とする

反転数をうまくdp式に縮められない…

num[i][j] = A[i] > A[j]となる通り数とする。(i < j なら反転数)

index xとyが交換される場合、全てのv(!=y)に関して

num[y][v] += num[x][v]
num[x][v] += num[y][v]

num[v][x] += num[v][y]
num[v][y] += num[v][x]

num[x][y] += num[y][x]
num[y][x] += num[x][y]

更新は高々4*3000
なので、C++なら可能？

いじらない部分は2倍する操作が必要。
最後にまとめて処理するために、いじった部分は半分にしておく

"""

N,Q = map(int,input().split())

A = []

for i in range(N):

    a = int(input())
    A.append(a)

lis = []
mod = 10**9+7
half = 500000004

for i in range(N):
    now = []
    for j in range(N):
        if A[i] > A[j]:
            now.append(1)
        else:
            now.append(0)
    lis.append(now)

for loop in range(Q):

    #print (lis)

    q = []
    q2 = []
    x,y = map(int,input().split())
    x -= 1
    y -= 1

    for v in range(N):
        if v != x and v != y:
            q.append([y,v,lis[x][v]])
            q.append([x,v,lis[y][v]])
            q.append([v,y,lis[v][x]])
            q.append([v,x,lis[v][y]])
    q.append([x,y,lis[y][x]])
    q.append([y,x,lis[x][y]])

    for t in q:
        i,j,n = t
        lis[i][j] += n
        lis[i][j] *= half
        lis[i][j] %= mod

#print (lis)

ans = 0
for j in range(N):
    for i in range(j):
        ans += lis[i][j]
        ans %= mod
print (ans * pow(2,Q,mod) % mod)

Submission status: Time Limit Exceeded

Solution code:
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])
# print(*mat, sep='\n')
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
    # print(x, y)
    # print(*mat, sep='\n')

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

Submission status: Time Limit Exceeded

Solution code:
# input
N, Q = map(int, input().split())
A = [int(input()) for _ in range(N)]
XY = []
for _ in range(Q):
    XY.append(tuple(map(int, input().split())))

dp = [[[None for _ in range(N)] for __ in range(N)] for ___ in range(Q+1)]
for i in range(N):
    for j in range(N):
        # inverse case
        dp[0][i][j] = 1 if A[i] > A[j] else 0


def get_past_value(dp, cur, i, j):
    past = 1
    while True:
        xprev = dp[cur-past][i][j]
        if xprev is not None:
            xprev *= pow(2, past-1)
            return xprev
        past += 1


for t in range(1, Q+1):
    x, y = tuple(b-1 for b in XY[t-1])

    # dp[t] = [[v * 2 for v in r] for r in dp[t-1]]

    for j in range(N):
        if j != x and j != y:
            dpx, dpy = (get_past_value(dp, t, xy, j) for xy in (x, y))
            dp[t][x][j] = dp[t][y][j] = dpx + dpy
            # dp[t][x][j] = dp[t-1][x][j] + dp[t-1][y][j]
            # dp[t][y][j] = dp[t-1][y][j] + dp[t-1][x][j]

    for i in range(N):
        if i != x and i != y:
            dpx, dpy = (get_past_value(dp, t, i, xy) for xy in (x, y))
            dp[t][i][x] = dp[t][i][y] = dpx + dpy
            # dp[t][i][x] = dp[t-1][i][x] + dp[t-1][i][y]
            # dp[t][i][y] = dp[t-1][i][y] + dp[t-1][i][x]

    dpx, dpy = (get_past_value(dp, t, a, b) for (a, b) in zip((x, y), (y, x)))
    dp[t][x][y] = dp[t][y][x] = dpx + dpy
    # dp[t][x][y] = dp[t-1][x][y] + dp[t-1][y][x]
    # dp[t][y][x] = dp[t-1][y][x] + dp[t-1][x][y]

    # for i in range(N):
    #     for j in range(N):
    #         dp[t][i][j] = dp[t-1][i][j] * 2
    #         if i == j:
    #             dp[t][i][j] = 0
    #             continue
    #         if i in xy and j in xy:
    #             dp[t][i][j] = dp[t-1][i][j] + dp[t-1][j][i]
    #             continue
    #         if i in xy and j not in xy:
    #             a = xy[0] if xy[1] == i else xy[1]
    #             dp[t][i][j] = dp[t-1][i][j] + dp[t-1][a][j]
    #             continue
    #         if i not in xy and j in xy:
    #             a = xy[0] if xy[1] == j else xy[1]
    #             dp[t][i][j] = dp[t-1][i][j] + dp[t-1][i][a]
    #             continue

res = 0
for i, r in enumerate(dp[-1]):
    for j, v in enumerate(r[i+1:]):
        tmp = 0
        if v is not None:
            tmp = v
            # res += v
        else:
            tmp = get_past_value(dp, -1, i, i+j+1) * 2
            # res += get_past_value(dp, -1, i, j) * 2
        res += tmp

print(res)

# print(sum(v for i, r in enumerate(dp[-1]) for v in r[i+1:]))

# dp = [[[] for __ in range(N)] for ___ in range(N)]
# for i in range(N):
#     for j in range(N):
#         # inverse case
#         dp[i][j].append(1 if A[i] > A[j] else 0)

# for t in range(1, Q+1):
#     x, y = tuple(b-1 for b in XY[t-1])
#     for j in range(N):
#         if j != x and j != y:
#             dp[x][j].append(dp[x][j][-1] + dp[y][j][-1])
#             dp[y][j].append(dp[y][j][-1] + dp[x][j][-1])

#     for i in range(N):
#         if i != x and i != y:
#             dp[i][x].append(dp[i][x][-1] + dp[i][y][-1])
#             dp[i][y].append(dp[i][y][-1] + dp[i][x][-1])

#     dp[x][y].append(dp[x][y][-1] + dp[y][x][-1])
#     dp[y][x].append(dp[y][x][-1] + dp[x][y][-1])

# print(sum(v[-1] for i, r in enumerate(dp) for v in r[i+1:]))

Submission status: Time Limit Exceeded

Solution code:
# input
N, Q = map(int, input().split())
A = [int(input()) for _ in range(N)]
XY = []
for _ in range(Q):
    XY.append(tuple(map(int, input().split())))

dp = [[[None for _ in range(N)] for __ in range(N)] for ___ in range(Q+1)]
for i in range(N):
    for j in range(N):
        # inverse case
        dp[0][i][j] = 1 if A[i] > A[j] else 0

for t in range(1, Q+1):
    x, y = tuple(b-1 for b in XY[t-1])
    dp[t] = [[v * 2 for v in r] for r in dp[t-1]]

    for j in range(N):
        if j != x and j != y:
            dp[t][x][j] = dp[t-1][x][j] + dp[t-1][y][j]
            dp[t][y][j] = dp[t-1][y][j] + dp[t-1][x][j]

    for i in range(N):
        if i != x and i != y:
            dp[t][i][x] = dp[t-1][i][x] + dp[t-1][i][y]
            dp[t][i][y] = dp[t-1][i][y] + dp[t-1][i][x]

    dp[t][x][y] = dp[t-1][x][y] + dp[t-1][y][x]
    dp[t][y][x] = dp[t-1][y][x] + dp[t-1][x][y]

print(sum(v for i, r in enumerate(dp[-1]) for v in r[i+1:]))

Submission status: Time Limit Exceeded

Solution code:
# input
N, Q = map(int, input().split())
A = [int(input()) for _ in range(N)]
XY = []
for _ in range(Q):
    XY.append(tuple(map(int, input().split())))

dp = [[[None for _ in range(N)] for __ in range(N)] for ___ in range(Q+1)]
for i in range(N):
    for j in range(N):
        # inverse case
        dp[0][i][j] = 1 if A[i] > A[j] else 0

for t in range(1, Q+1):
    xy = tuple(b-1 for b in XY[t-1])
    for i in range(N):
        for j in range(N):
            dp[t][i][j] = dp[t-1][i][j] * 2
            if i == j:
                dp[t][i][j] = 0
                continue
            if i in xy and j in xy:
                dp[t][i][j] = dp[t-1][i][j] + dp[t-1][j][i]
                continue
            if i in xy and j not in xy:
                a = xy[0] if xy[1] == i else xy[1]
                dp[t][i][j] = dp[t-1][i][j] + dp[t-1][a][j]
                continue
            if i not in xy and j in xy:
                a = xy[0] if xy[1] == j else xy[1]
                dp[t][i][j] = dp[t-1][i][j] + dp[t-1][i][a]
                continue

print(sum(v for i, r in enumerate(dp[-1]) for v in r[i+1:]))

Submission status: Time Limit Exceeded

Solution code:
N = 3005
MOD = 1000 * 1000 * 1000 + 7
n , m = map(int, input().split())
a = [int(input()) for i in range(n)]
qu = [map(int, input().split()) for i in range(m)]

p2 = [1]
for i in range(N) : 
    p2.append(p2[i] * 2 % MOD)

f = [[0 for i in range(n)] for j in range(n)]

for i in range(n) :
    for j in range(n) : 
        f[i][j] = 1 if a[i] > a[j] else 0

rev2 = (MOD + 1) // 2

for use in range(m) :
    x, y = qu[use]
    x = x - 1
    y = y - 1
    for z in range(n) : 
        if (z != x and z != y) :
            sumzx = (f[z][x] + f[z][y]) * rev2 % MOD
            sumxz = (f[x][z] + f[y][z]) * rev2 % MOD
            f[z][x] = f[z][y] = sumzx
            f[x][z] = f[y][z] = sumxz
    sumxy = (f[x][y] + f[y][x]) * rev2 % MOD
    f[x][y] = f[y][x] = sumxy % MOD
ans = 0
for i in range(n) :
    for j in range(i) : 
        ans = (ans + f[j][i]) % MOD
print(ans * p2[m] % MOD)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)
# print(mat)
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)

Submission status: Runtime Error

Solution code:
def run(N, Q, A, XY):
    return rec_count(A, XY, 0)


def rec_count(A, XY, i):
    div = 10**9 + 7
    if i >= len(XY):
        return count_swap(A) % div
    A_swap = swap(A, XY[i])
    return (rec_count(A, XY, i+1) + rec_count(A_swap, XY, i+1)) % div


def swap(A, XY):
    A_swap = A.copy()
    X = XY[0] - 1
    Y = XY[1] - 1
    A_swap[X], A_swap[Y] = A[Y], A[X]
    return A_swap


def count_swap(A):
    cnt = 0
    for i in range(len(A)):
        for j in range(i+1, len(A)):
            if A[i] > A[j]:
                cnt += 1
    return cnt


def main():
    N, Q = map(int, input().split())
    A = []
    for _ in range(N):
        A.append(int(input()))
    XY = []
    for _ in range(Q):
        XY.append(list(map(int, input().split())))
    print(run(N, Q, A, XY))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def selection(elems, low, high):
  num_swap = 0
  ns_l = 0
  ns_r = 0
  if(low < high):
    pos, num_swap = partition(elems,low, high)
    ns_l = selection(elems, low, pos-1)
    ns_r = selection(elems, pos+1, high)
  return num_swap + ns_l + ns_r

def partition(elems, low, high):
  pivot = elems[low]
  num_swap = 0
  lower_end = low
  i = low+1
  while(i <= high):
    if(elems[i] < pivot):
      tmp = elems[lower_end]
      elems[lower_end] = elems[i]
      elems[i] = tmp
      #if(i != higher_start):
      num_swap += 1
      lower_end += 1
    i += 1
  elems[lower_end] = pivot
  
  return lower_end, num_swap

def swap_list(dl, idx1, idx2):
  tmp = dl[idx1]
  dl[idx1] = dl[idx2]
  dl[idx2] = tmp

def dec2binary(dec):
    q = dec//2
    r = dec % 2
    binary_list = [r]
    while(q != 0):
        r = q % 2
        q = q // 2
        binary_list.append(r)
    return binary_list # get the reserved binary_list
  
def main():
  N, Q =[int(each) for each in input().split()]
  dl = []
  
  operation = []
  for i in range(N):
    dl.append(int(input().strip()))
  for i in range(Q):
    operation.append([int(each) for each in input().split()])
  print('dl ', dl)
  total_num = 0
  for i in range(2**Q):
    valid_opr = dec2binary(i)
    swap_dl = []
    for m in range(N):
      swap_dl.append(dl[m])

    for j in range(len(operation)):
      idx1 = operation[j][0] - 1
      idx2 = operation[j][1] - 1 
      if(j < len(valid_opr) and valid_opr[j] == 1):
        swap_list(swap_dl, idx1, idx2)
      elif(j >= len(valid_opr)):
        break
    tmp_num = selection(swap_dl, 0, len(swap_dl)-1)
    #print('for {} , the inversion num {}'.format(swap_dl , tmp_num))
    total_num += tmp_num
  print(total_num)  
  return total_num

if __name__ == '__main__':
  main()