Problem:


Score : 300 points

Problem Statement

We have a sequence of N integers A~=~A_0,~A_1,~...,~A_{N - 1}.

Let B be a sequence of K \times N integers obtained by concatenating K copies of A. For example, if A~=~1,~3,~2 and K~=~2, B~=~1,~3,~2,~1,~3,~2.

Find the inversion number of B, modulo 10^9 + 7.

Here the inversion number of B is defined as the number of ordered pairs of integers (i,~j)~(0 \leq i < j \leq K \times N - 1) such that  B_i > B_j.

Constraints

All values in input are integers.

1 \leq N \leq 2000

1 \leq K \leq 10^9

1 \leq A_i \leq 2000

Input

Input is given from Standard Input in the following format:

N K
A_0 A_1 ... A_{N - 1}

Output

Print the inversion number of B, modulo 10^9 + 7.

Sample Input 1

2 2
2 1

Sample Output 1

3

In this case, B~=~2,~1,~2,~1. We have:

B_0 > B_1

B_0 > B_3

B_2 > B_3

Thus, the inversion number of B is 3.

Sample Input 2

3 5
1 1 1

Sample Output 2

0

A may contain multiple occurrences of the same number.

Sample Input 3

10 998244353
10 9 8 7 5 6 3 4 2 1

Sample Output 3

185297239

Be sure to print the output modulo 10^9 + 7.



Sample input:
2 2
2 1


Sample output:
3

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))

sum = 0
sum_K = K * (K+1) / 2
for i in range(N):
    before = 0
    after = 0
    Ai = A[i]
    # iより前を調べる
    for j in range(i):
        if Ai > A[j]:
            before += 1
    # iより後ろを調べる
    for j in range(i+1,N):
        if Ai > A[j]:
            after += 1
    all = before + after

    sum += after * sum_K + before * (sum_K - K)
    #print(before, after, all, sum)
    #print('{:100.3f}'.format(sum))
d = 1000000007
#print(d)
print(int(sum % d))

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = (10 ** 9) + 7

if k == 1:
	ans = 0
	for i in range(n):
		for num in a[i:]:
			if a[i] > num:
				ans += 1
	print(ans)
	exit()

a = a * 2

lis = [0] * n * 2

for i in range(2*n):
	for num in a[i:]:
		if a[i] > num:
			lis[i] += 1

a = sum(lis[n:])
d = sum(lis[:n]) - sum(lis[n:])

ans = (2 * a + ((k-1) * d)%mod) % mod
ans = (ans * k) % mod
print(ans//2)

Submission status: Wrong Answer

Solution code:
import numpy as np
N,K = map(int,input().split())
Alist = np.array(list(map(int,input().split())))
counter = 0
for i,A in enumerate(Alist,0):
    fir_tenti = np.count_nonzero(A>Alist[i:])
    counter += (K*fir_tenti*(K+1))/2
    second_tenti = np.count_nonzero(A>Alist[:i+1])
    counter += (second_tenti*K**2-second_tenti*(K))/2

print(int(counter%1000000007))

Submission status: Wrong Answer

Solution code:
import numpy as np
N,K = map(int, input().split())
A = list(map(int, input().split()))
result = 0
while A != []:
    A_max_index = np.argmax(A)
    A_max = max(A)
    result = (result + sum([a<A_max for a in A[A_max_index+1:]]) * K + sum([a<A_max for a in A]) * int(((K-1) * K) / 2)) % (10**9 + 7)
    A.remove(A_max)
print(result)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
t = [0]*n
ta = [0]*n
for i in range(n):
    cnt=0
    for j in range(i+1,n):
        if a[i]>a[j]:
            cnt +=1
    t[i]=cnt
for i in range(n):
    cnt=0
    for j in range(n):
        if a[i]>a[j]:
            cnt +=1
    ta[i]=cnt
ans=0
mod = 10**9+7
wa=[0]*n
for i in range(n):
    wa[i]+=t[i]*k%mod
    wa[i]%=mod
    if k%2==0:
        wa[i]+=((ta[i]*k/2)%mod)*((k-1)%mod)%mod
    else:
        wa[i]+=((ta[i]*k)%mod)*((k-1)/2%mod)%mod
    wa[i]%=mod
for i in range(n):
    ans += wa[i]
    ans %= mod
print(int(ans))

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
A = list(map(int, input().split()))
c1 = 0
c2 = 0
for i in range(n-1):
  for k in range(n-1-i):
    if A[i] > A[k+1+i]:
      c1 += 1
for i in range(n):
  for k in range(n):
    if A[i] > A[k]:
      c2 += 1
c3 = (m * (m - 1) / 2)%(10**9+7)
c4 = (c3*c2)%(10**9+7)
c5 = (c1*m)%(10**9+7)
print(int((c4+c5)%(10**9+7)))

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
A = list(map(int,input().split()))
a = len(A)
MOD = 10**9+7
mae_cnt = 0
ato_cnt = 0
ans = 0

def seki(num):
  return int(num*(num+1)/2)

for i in range(a):
  ans += (mae_cnt*seki(k)) % MOD
  ans += (ato_cnt*seki(k-1)) % MOD
  mae_cnt = 0
  ato_cnt = 0
  for j in range(i+1,a):
    if A[i] > A[j]:
      mae_cnt += 1

  for x in range(i):
    if A[i] > A[x]:
      ato_cnt += 1
      
ans += (seki(k)*mae_cnt)%MOD
ans += (seki(k-1)*ato_cnt)%MOD      

print(ans)

Submission status: Wrong Answer

Solution code:
N,K=list(map(int, input().split()))
A=list(map(int, input().split()))

MOD=10**9+7

arr=[0]*N
for i, ai in enumerate(A[:-1]):
    cnt=0
    for aj in A[i+1:]:
        if ai > aj:
            cnt+=1
    arr[i]=cnt

s=sum(arr)
v=(K+1)*K//2
print((s*v)%MOD)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split(" "))
A=list(map(int,input().split(" ")))
#N=3
#K=3
#A=[1,3,2]
A1=[set() for _ in range(N)]
cnt=0
cnt1=0
for n1 in range(N):
    for n2 in range(N):
        if n1!=n2 and A[n1]>A[n2]:
            cnt+=1
        if n1<n2 and A[n1]>A[n2]:
            cnt1+=1
#ten=int(cnt1+cnt*(K**2-K)/2+cnt1*(K-1))
k2=(K**2)%(10**9+7)
ten1=int((k2*cnt/2)%(10**9+7))
ten2=int((K*cnt/2)%(10**9+7))
ten3=int((cnt1*K)%(10**9+7))
if ten1-ten2<0:
    ten=ten1-ten2+10**9+7
else:
    ten=ten1-ten2
ten=ten+ten3
print(ten%(10**9+7))

Submission status: Wrong Answer

Solution code:
import numpy as np
N,K = map(int,input().split())
Alist = np.array(list(map(int,input().split())))
counter = 0
for i,A in enumerate(Alist,0):
    fir_tenti = np.count_nonzero(A>Alist[i:])
    counter += (K*fir_tenti*(K+1))/2
    print(counter)
    second_tenti = np.count_nonzero(A>Alist[:i+1])
    counter += (second_tenti*K**2-second_tenti*(K))/2
    print(counter)

print(int(counter%1000000007))

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a = [int(i) for i in input().split()]
b=a*3
c1 = 0
c2 = 0
c3 = 0

for i in range(n*3):
	for j in range(i,n*3,1):
		if b[i] > b[j]:
			c3+=1
			if i < n*2 and j < n*2:
				c2+=1
				if i < n and j < n:
					c1+=1

diff_c1 = c2-c1
diff_c2 = c3-c2
diff_c = diff_c2 - diff_c1


all_s = (diff_c1+(k-2)*diff_c+diff_c1)*(k-1)*0.5

if k == 1:
	print("%d" % int(c1%((10**9)+7)))
elif k == 2:
	print("%d" % int(c2%((10**9)+7)))
elif k == 3:
	print("%d" % int(c3%((10**9)+7)))
else:
	print("%d" % int((c1+all_s)%((10**9)+7)))

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())

a=list(map(int,input().split()))
tentou1=0
for i in range(N):
  for j in range(i+1,N):
    if(a[i]>a[j]):
      tentou1+=1
a.sort()
a.reverse()
stentou=0
for i in range(N):
  for j in range(i+1,N):
    if(a[i]>a[j]):
      stentou+=1
answer=int(int(tentou1*K) + int(stentou*K*(K-1)/2))
print(answer%1000000007)

Submission status: Wrong Answer

Solution code:
def main():
    def c(x,y):
        if x > y:
            return 1
        else:
            return 0
    n,k = map(int,input().split())
    x = 1000000007
    kk = int(k*(k-1)/2)%x
    a = list(map(int,input().split()))
    c1 = []
    c2 = []
    for i in range(n):
        l = [c(a[i],p) for p in a]
        c1.append(sum(l))
        c2.append(sum(l[i:]))
    ans = ((sum(c1)%x)*kk)%x+((sum(c2)%x)*k)%x
    print(ans%x)
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
l =list(map(int,input().split()))
cnt =0

for i in range(len(l)):
    for j in range((len(l)-i)):
        if l[i] > l[j]:
            cnt += 1
a = len(set(l))
cnt = k*cnt + (a-1)*a/2*(k-1)
print(int(cnt%(10**9 +7)))

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = (10 ** 9) + 7

if k == 1:
	ans = 0
	for i in range(n):
		for num in a[i:]:
			if a[i] > num:
				ans += 1
	print(ans)
	exit()

a = a * 2

lis = [0] * n * 2

for i in range(2*n):
	for num in a[i:]:
		if a[i] > num:
			lis[i] += 1

a = sum(lis[n:])
d = sum(lis[:n]) - sum(lis[n:])

ans = (2 * a + (k-1) * d) % mod
ans = (ans * k) % mod
print(ans//2)

Submission status: Wrong Answer

Solution code:
mod=10**9+7
n, k=map(int, input().split())
a=list(map(int, input().split()))
jibun=0
for i in range(n):
    for j in range(i+1, n):
        if a[i]>a[j]:
            jibun=(jibun+1)%mod

saki=0
for i in range(n):
    for j in range(n):
        if a[i]>a[j]:
            saki=(saki+1)%mod
ans=0

print(((jibun*k)%mod+int((1/2)*saki*k*(k-1))%mod)%mod)

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline
sys.setrecursionlimit(1000000)


def getN():
    return int(input())


def getList():
    return list(map(int, input().split()))


import math
MOD = 10 ** 9 + 7

n, k = getList()
anums = getList()

space = [[] for i in range(2002)]
remain = [1 for j in range(n)]
yet = n

for i, x in enumerate(anums):
    space[x].append(i)


ans = 0
for s in space:
    if s:
        jump = 0
        yet -= len(s)
        for num in s:
            jump += sum(remain[:num])
            remain[num] = 0
            # print(jump)
        ans += (yet * (k * (k-1))) // 2
        ans += jump * k
        # print(ans, jump, yet)
        # remain[num] = 0

        ans %= MOD
        # yet -= len(s)
        # yet -= 1
print(ans)
# print((43 * (998244353*998244354) // 2) % MOD)

Submission status: Wrong Answer

Solution code:
n,K=map(int,input().split())
A=list(map(int,input().split()))
s=0
for i in range(1,n):
    k=i
    while A[k]<A[k-1]:
        A[k],A[k-1]=A[k-1],A[k]
        k-=1
        s+=1
        if k==0:
            break
j=0
l=1
S=0
while j<n-1:
    if A[j]==A[j+1]:
        l+=1
        j+=1
    else:
        S=S+l*(n-1-j)
        l=1
        j+=1
B=int(s*K+(S*K*(K-1))/2)
C=int(s*K)%1000000007
D=int(K*(K-1)/2)%1000000007
print((C+S*D)%1000000007)

Submission status: Wrong Answer

Solution code:
N,K = map(int, input().split())
A = list(map(int,input().split()))

def souwa(num):
    if num % 2 == 0:
        return int((num+1) * (num/2))
    else:
        return ((num+1) * (num//2)) + ((num//2)+1)

ans = 0
for i in range(N):
    buf1 = sum(A[i] > A[j] for j in range(i+1, N))
    buf2 = sum(A[i] > a for a in A)
    ans += (buf1 * K) + (buf2 * souwa(K-1))

print(ans % (10**9+7))

Submission status: Wrong Answer

Solution code:
n,k = map(int, input().split())

array = list(map(int, input().split()))
one_tento = 0
for i in range(n-1):
    for j in range(i+1,n):
        if array[i] > array[j]:
            one_tento += 1

two_tento = 0
for ki in range(n):
    for l in range(n):
        if array[ki] < array[l]:
            two_tento += 1

result =  (two_tento*k*(k-1))/2 + one_tento*k
waru = 7 + 10 ** 9
print(int(result % waru))

Submission status: Wrong Answer

Solution code:
def main():
    def c(x,y):
        if x > y:
            return 1
        else:
            return 0
    n,k = map(int,input().split())
    x = 1000000007
    kk = int(k*(k-1)/2)%x
    a = list(map(int,input().split()))
    c1 = []
    c2 = []
    for i in range(n):
        l = [c(a[i],p) for p in a]
        c1.append(sum(l))
        c2.append(sum(l[i+1:]))
    ans = (sum(c1)%x)*kk+(sum(c2)%x)*k
    print(ans%x)
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
ta = 0
c = 0
AA = [0 for i in range(N)]
for i in range(N):
	for j in range(N):
		if A[i]>A[j]:
			AA[i] = AA[i] + 1
			if i<j:
				ta = (ta + 1) % (10**9 + 7)
tb = (ta*K)%(10**9+7)
c = K*(K-1)%(10**9+7)
c = int(c/2)
for i in range(N):
	tb = (tb + (c*AA[i])%(10**9 + 7) ) % (10**9 + 7)

print(tb)

Submission status: Wrong Answer

Solution code:
import numpy as np

def mergecount(A):
  cnt = 0
  n = len(A)
  if n>1:
    A1 = A[:n>>1]
    A2 = A[n>>1:]
    cnt += mergecount(A1)
    cnt += mergecount(A2)
    i1=0
    i2=0
    for i in range(n):
      if i2 == len(A2):
        A[i] = A1[i1]
        i1 += 1
      elif i1 == len(A1):
        A[i] = A2[i2]
        i2 += 1
      elif A1[i1] <= A2[i2]:
        A[i] = A1[i1]
        i1 += 1
      else:
        A[i] = A2[i2]
        i2 += 1
        cnt += n//2 - i1
  return cnt

N,K = list(map(int,input().split()))
l = list(map(int,input().split()))
L = np.array(l)
for _ in range(K):
  L = np.append(L,l)
c = mergecount(L)

print(c%((10**7)+7))

Submission status: Wrong Answer

Solution code:
N,K = map(int, input().split())
A = list(map(int, input().split()))

MOD = 10 ** 9 + 7

X = 0

for i in range(N):
    for j in range(i+1,N):
        if A[i] > A[j]:
            X += 1

Y =0

for i in range(N):
    for j in range(N):
        if A[i] > A[j]:
            Y += 1

print((X * K + int((K * (K-1))/2 * Y )) % MOD)

Submission status: Wrong Answer

Solution code:
N, K = map(int,input().split())
A = list(map(int,input().split()))
SUM_1 = 0
for a in range(len(A)) :
    for _a in range(a+1, len(A)) :
        if A[a] > A[_a] :
            SUM_1 += 1

A2 = A+A
SUM_2 = 0
for a in range(len(A2)) :
    for _a in range(a+1, len(A2)) :
        if A2[a] > A2[_a] :
            SUM_2 += 1

S = SUM_2 - SUM_1 - SUM_1
SUM = SUM_1 + 0
if K == 1:
    print(SUM_1 % (10**9 + 7))
else :
    for i in range(2, K+1) :
        SUM = SUM + (i*S)
    print(SUM % (10**9 + 7))

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().strip().split())
list = list(map(int, input().strip().split()))
s = 0
t = 0
k = k


for i in range(n):
    for j in range(i, n):
        if list[i] > list[j]:
            s += 1
            
list.reverse()           
for i in range(n):
    for j in range(i, n):
        if list[i] > list[j]:
            t += 1            
            
a = int((k*(k+1)%1000000007)/2)
b = int((k*(k-1)%1000000007)/2)

print(int((s*a+t*b)%1000000007))

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())

l=list(map(int,input().split()))

x=10**9+7

a=0
for i in range(n-1):
  for j in range(i+1,n):
    if l[i]>l[j]:
      a+=1

ans=a*k%x
ans=ans*(k+1)%x
ans=ans//2

print(ans)

Submission status: Wrong Answer

Solution code:
mod=10**9+7
n, k=map(int, input().split())
a=list(map(int, input().split()))
jibun=0
for i in range(n):
    for j in range(i+1, n):
        if a[i]>a[j]:
            jibun=jibun+1

saki=0
for i in range(n):
    for j in range(n):
        if a[i]>a[j]:
            saki=saki+1
ans=0

print(((jibun*k)%mod+int((1/2)*saki*k*(k-1))%mod)%mod)

Submission status: Wrong Answer

Solution code:
import math
N,K =map(int,input().split())
A = list(map(int,input().split()))
B = 0
C = sorted(A)

D = 0
for j in range(N-1):
    for i in range(j+1,N-2):
        if A[j]>A[i]:
            B +=1
            #print(B)
B = B*K
#print(B)
if K>1:
    for k in range(N):
        #print(C.index(A[k]))
        D += int(C.index(A[k]))
        #print(D)
#print(C.index(10))
E=D*math.factorial(N-1)+B
F =7+10**9
#print(E)
print(E%F)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
li = list(map(int,input().split()))
mod = 10**9 +7
 
ans_1 = 0
ans_2 = 0
for i in range(n-1):
  for j in range(i+1,n):
    if li[i] > li[j]:
      ans_1+= 1
for i in range(n):
  for j in range(n):
    if li[i] < li[j]:
      ans_2 += 1
ans = k*ans_1%mod + 0.5*k%mod*(k-1)%mod*ans_2%mod
print(int(ans%mod))

Submission status: Wrong Answer

Solution code:
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))

def cal(A, N):
    cnt1 = 0
    cnt2 = 0
    for i in range(N):
        for j in range(i+1,N):
            if A[N-1-j] > A[N-1-i]:
                cnt1 += 1
    for i in range(N):
        for j in range(N):
            if A[N-1-i] < A[j]:
                cnt2 += 1
    
    return cnt1, cnt2
    
    
x, y = cal(A,N)
x = int(x)
y = int(y)

tmp = int(y*K*(K-1)/2)
ans = int(tmp + x*K)
print(ans%(10**9+7))

Submission status: Wrong Answer

Solution code:
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
import math
import queue
#import numpy as np
Mod = 1000000007




def main(): #startline-------------------------------------------
    n,k = map(int,input().split())
    a = list(map(int,input().split()))
    ans = 0
    for i in range(n):
        for j in range(n-1,i,-1):
            if a[j] < a[j-1]:
                a[j],a[j-1] = a[j-1],a[j]
                ans += 1
                ans %= Mod
    u = Counter(a)
    ul = list(u.keys())
    ul.sort(reverse = True)
    p = len(set(a))   
    ans *= k
    temp = 0
    for i in range(p):
        temp += u[ul[i]]
        ans += (n-temp)*(k*(k-1)//2)
        ans %= Mod
    print(ans)

if __name__ == "__main__":
    main() #endline===============================================





def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n < 2 is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))):
        if prime[i] == 1:
            for j in range(2*i,n):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n):
        if prime[i] == 1:
            res.append(i)
    return res

class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py

    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)

Submission status: Wrong Answer

Solution code:
import sys

def input(): return sys.stdin.readline()[:-1]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def MATINT(h): return [list(map(int, input().split())) for _ in range(h)]
def MATSTR(h): return [input() for _ in range(h)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
inf = float('inf')
mod = 10 ** 9 + 7

def main():
    N, K = MAP()
    A = LIST()
    count = 0
    for i in range(N):
        count_all = 0
        count_ = 0
        for j in range(N):
            if A[i] > A[j]:
                count_all += 1
                if i < j:
                    count_ += 1
        count += count_ * K % mod
        count += (count_all * (K - 1) * K / 2 % mod) % mod
        count = count % mod
        # import pdb; pdb.set_trace()
    print(int(count) % mod)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
mod = 10**9 + 7
N, K = map(int, input().split())
A = list(map(int, input().split()))
B1 = 0
B2 = 0
ll = [0] * N
ll2 = [0] * N
for i in range(0, N-1):
    for j in range(i+1, N):
        if A[i] > A[j]:
            ll[j] += 1
        else:
            for k in range(N):
                if A[i] < A[k]:
                    ll2[i] += 1
            # print(A[i], A[j], i, j)
        if A[j] > A[N-1]:
            B2 += 1
if A[N-1] > A[0]:
    ll[0] += 1
ans = 0
for i in range(N):
    if ll2[i] != 0:
        ans += ((ll2[i] * K * (K+1))//2 - (ll2[i] - ll[i]) * K)
    else:
        ans += (ll[i] * K * (K+1))//2
print(ans % mod)

Submission status: Wrong Answer

Solution code:
n, k  = map(int, input().split())
lst = list(map(int, input().split()))

# print(lst[3:])
s_lst = sorted(enumerate(lst), key=lambda x: x[1])
# print(s_lst)

# print(s_lst[0][1])

# x番目にでかい数がそれ以降の部分lstにいくつあるか
def pp(x):
	p = 0
	for i in lst[s_lst[-1*x][0]:]:
		if i < s_lst[-1*x][1]:
			p += 1
	return p

# x番目にでかい数より小さいものがlstにいくつあるか
def qq(x):
	q = 0
	for j in lst:
		if j < s_lst[-1*x][1]:
			q += 1
	return q

cnt = 0
for m in range(1,n+1):
	# print(pp(m))
	# print(qq(m))
	cnt += (int(k*pp(m)) + int(qq(m)*(k-1)*k/2))

print(cnt%(7+10**9))

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))

tota = 0
totd = 0

for i in range(N):
    for j in range(i+1, N):
        if A[i] > A[j]:
            tota += 1
    for k in range(N):
        if A[i] > A[k]:
            totd += 1

print(int((((K%1000000007)/2)*(2*tota + ((K-1)%1000000007)*totd))%1000000007))

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = (10 ** 9) + 7

if k == 1:
	ans = 0
	for i in range(n):
		for num in a[i:]:
			if a[i] > num:
				ans += 1
	print(ans)
	exit()

a = a * 2

lis = [0] * n * 2

for i in range(2*n):
	for num in a[i:]:
		if a[i] > num:
			lis[i] += 1

a = sum(lis[n:])
d = sum(lis[:n]) - sum(lis[n:])

ans = k * (2 * a + (k-1) * d) % mod


print(ans//2)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().strip().split())
list = list(map(int, input().strip().split()))
s = 0
t = 0
k = k


for i in range(n):
    for j in range(i, n):
        if list[i] > list[j]:
            s += 1
            
list.reverse()           
for i in range(n):
    for j in range(i, n):
        if list[i] > list[j]:
            t += 1            
            
a = int((k*(k+1)%1000000007)/2)
b = int((k*(k-1)%1000000007)/2)

print(a,b,int((s*a+t*b)%1000000007))

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
a0 = a[0]
an = a[n-1]
now = a0
c_self = 0
c_inter = 0
for i in range(n):
    for j in range(i,n):
        #print(i,j)
        #print("a",a[i],a[j])
        if a[i] > a[j]:
            c_self += 1
        if a[i] != a[j]:
            c_inter += 1

t =( (k-1) * k ) % (10**9 + 7)
l = (k * c_self) % (10**9 + 7)
q = (t * c_inter) % (10**9 + 7)

ans = (l + q / 2) % (10**9 + 7)
print(int(ans))

Submission status: Wrong Answer

Solution code:
mod = 1000000007
n,k = map(int, input().split())
a = list(map(int, input().split()))
count = 0
for (i,b) in enumerate(a):
    left = a[:i]
    right = a[i+1:]
    cl, cr = 0, 0
    for j in left:
        if b > j: cl += 1
    for j in right:
        if b > j: cr += 1
    count = (count + cr*k*(k+1)/2 + cl*k*(k-1)/2)%mod
print(int(count))

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())

a=list(map(int,input().split()))
tentou1=0
for i in range(len(a)):
  for j in range(i+1,len(a)):
    if(a[i]>a[j]):
      tentou1+=1
a.sort()
a.reverse()
stentou=0
for i in range(len(a)):
  for j in range(i+1,len(a)):
    if(a[i]>a[j]):
      stentou+=1
answer=int(int(tentou1*K) + int(stentou*K*(K-1)/2))
print(answer%1000000007)

Submission status: Wrong Answer

Solution code:
import math
N, K = map(int, input().split())
A = list(map(int, input().split()))
A2 = A * 2
a = [0]*2*N
for i in range(len(A2)-1):
    for j in A2[i+1:]:
        if A2[i] > j:
            a[i] += 1

if K % 2 == 0:
    c = []
    b1 = a[0:N]
    b2 = a[N:]
    for i in range(N):
        c.append(b1[i]-b2[i])
    b1sum = sum(c)

    print(int((K*(K-1)/2*b1sum+K*sum(b2))%(10**9+7)))
else:
    c = []
    b1 = a[0:N]
    b2 = a[N:]
    for i in range(N):
        c.append(b1[i]-b2[i])
    b1sum = sum(c)
    print(int((K*(K-1)/2*b1sum+K*sum(b2))%(10**9+7)))

Submission status: Wrong Answer

Solution code:
N,K = map(int, input().split())
A = [int(i) for i in input().split()]

def count_inversion(sequence):
    count = 0
    for i in range(1,len(sequence),1):
        for j in range(i,len(sequence),1):
            if sequence[i-1] > sequence[j]:
                count += 1
    return count

def count_inversion_B(sequence):
    count = 0
    for a in A:
        count = count + (A.count(a) - 1)
    return count

def count_inversion_C(sequence):
    count_hairetu = []
    for a in A:
        count_hairetu.append(A.count(a))
    return count_hairetu

count_inv = count_inversion(A)
count_tyouhuku = count_inversion_B(A)
count_hairetu = count_inversion_C(A)

count_a = 0
for i in range(len(count_hairetu)):
    count_a = count_tyouhuku * count_hairetu[i]

count_sum = (count_inv * K) + ((count_tyouhuku + count_a) * (K-1))

print(count_sum%(10**9+7))

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
#N,K = map(int,'10 998244353'.split())
Alist = list(map(int,input().split()))
#Alist = list(map(int,'10 9 8 7 5 6 3 4 2 1'.split()))
beforeTnumber = [0]*N
afterTnumber = [0]*N
beforesum = 0
aftersum = 0
mod_num = 10**9+7

for now in range(N):
    for before in range(now):
        if Alist[before] < Alist[now]:
            beforeTnumber[now] += 1
    for after in range(now,N):
        if Alist[after] < Alist[now]:
            afterTnumber[now] += 1
            
for i in range(N):
    beforesum += beforeTnumber[i]
    aftersum += afterTnumber[i]

Ksum = ((K/2)*(K+1))%mod_num

print((((aftersum*(Ksum))%mod_num+(beforesum*(Ksum-1))%mod_num))%mod_num)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
A=input().split()
A=[int(s) for s in A]
x=0
y=0
m=0
for i in A:
    j = m
    while j < n:
        if i > A[j]:
            x += 1
        j += 1
    m +=1

m=0
for i in A:
    j = m
    while j > 0:
        if i < A[j]:
            y += 1
        j -= 1
    m +=1

z = x * ((k+1)*k/2) + y * ((k-1)*k/2)
Ans = int(z) % (10**9+7)
print(Ans)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a = [int(i) for i in input().split()]
b=a*3
c1 = 0
c2 = 0
c3 = 0
for i in range(n):
	for j in range(i,n,1):
		if b[i] > b[j]:
			c1 += 1
for i in range(n*2):
	for j in range(i,n*2,1):
		if b[i] > b[j]:
			c2 += 1
for i in range(n*3):
	for j in range(i,n*3,1):
		if b[i] > b[j]:
			c3+=1

diff_c1 = c2-c1
diff_c2 = c3-c2
diff_c = diff_c2 - diff_c1

all_s = (diff_c1+(k-2)*diff_c+diff_c1)*(k-1)*0.5

if k == 1:
	print("%d" % int(c1%((10**9)+7)))
elif k == 2:
	print("%d" % int(c2%((10**9)+7)))
elif k == 3:
	print("%d" % int(c3%((10**9)+7)))
else:
	print("%d" % int((c1+all_s)%((10**9)+7)))

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())

A=list(map(int,input().split()))

d=10**9+7

c=0

for i in range(N-1):
    for j in range(i+1,N):
        if A[i]>A[j]:
            c+=1
c=c%d

cc=0

for i in range(N):
    for j in range(N):
        if A[i]>A[j]:
            cc+=1

cc=cc%d

e=(K*(K-1)/2)%d

print(int(((c*K)%d+(cc*e)%d)%d))

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
ans = 0
time_ans = 0
A_sort = sorted(A)
before = -1
b = -1
for i in range(N):
        a_sorti = A_sort[i]
        if a_sorti == before:
                time_ans += b
                continue
        b = A_sort.index(a_sorti)
        time_ans += b
        before = a_sorti

for i in range(N):
        for j in range(i + 1,N):
                if A[i] > A[j]:
                        ans += 1
ans1 = int((time_ans * K * (K + 1)) / 2) - K * (time_ans - ans)
if K >= 10:
        ans1 += ans
print(ans1 % (10 ** 9 + 7))

Submission status: Wrong Answer

Solution code:
import numpy as np

MOD = 1e+9 + 7
N, K = map(int, input().split())
Alist = list(map(int, input().split()))

Alist_sorted = sorted(Alist)
tmp = 0
tmp2 = 0
for i in range(1, len(Alist)):
    if Alist_sorted[i] == Alist_sorted[i-1]:
        tmp2 += 1
    else:
        tmp2 = 0
    tmp += i - (tmp2)
ans = ((tmp * ((K * (K-1) / 2) % MOD)) % MOD)

Alist = Alist[::-1]
for i in range(1, len(Alist)):
    ans += ((np.sum(np.array(Alist[:i]) < Alist[i]) * K) % MOD)
    ans = ans % MOD
ans = ans % MOD
print(int(ans))

Submission status: Wrong Answer

Solution code:
from sys import stdin
import math
import fractions
from collections import deque
from collections import Counter
import itertools

INF = 10 ** 10

MOD = 10**9 + 7

N, K = [int(x) for x in stdin.readline().rstrip().split()]
A = [int(x) for x in stdin.readline().rstrip().split()]


cnt = 0

for i in range(N):
    for j in range(i+1, N):
        if A[i] > A[j]:
            cnt += 1

cnt = cnt % MOD

if K >= 2:
    cnt = (cnt * K) % MOD

cnt2 = 0

if K >= 2:
    for i in range(N):
        for j in range(N):
            if A[i] > A[j]:
                cnt2 += 1
    cnt2 = cnt2 % MOD

    tmp = ( (((K) * (K-1)) % MOD) / 2 )

    cnt2 = (cnt2 * tmp)

cnt = (cnt + cnt2) % MOD

print(int(cnt))

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))*2
count1=0
count2=0
for i in range(2*n):
  for j in range(i+1,2*n):
    if a[i]>a[j] and j<n:
      count1+=1
      count2+=1
    elif a[i]>a[j]:
      count2+=1

if k==1:
  print(count1%(10**9+7))
else:
  ans=((count2-2*count1)*k*(k-1)/2+count1*(k+1))%(10**9+7)
  print(int(ans+count1))

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
A = list(map(int, input().split()))
c1 = 0
c2 = 0
for i in range(n-1):
  for k in range(n-1-i):
    if A[i] > A[k+1+i]:
      c1 += 1
for i in range(n):
  for k in range(n):
    if A[i] > A[k]:
      c2 += 1
c3 = (m * (m - 1) / 2)%(10**9+7)
print(int((c3*c2+c1*m)%(10**9+7)))

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
ans = 0
time_ans = 0
A_sort = sorted(A)
before = -1
b = -1
for i in range(N):
        a_sorti = A_sort[i]
        if a_sorti == before:
                time_ans += b
                continue
        b = A_sort.index(a_sorti)
        time_ans += b
        before = a_sorti

for i in range(N):
        for j in range(i + 1,N):
                if A[i] > A[j]:
                        ans += 1
ans1 = int((time_ans * K * (K + 1)) / 2) - K * (time_ans - ans)
if K >= 10 ** 5:
        ans1 += ans
print(ans1 % (10 ** 9 + 7))

Submission status: Wrong Answer

Solution code:
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))

def cal(A, N):
    cnt1 = 0
    cnt2 = 0
    for i in range(N):
        for j in range(i+1,N):
            if A[N-1-j] > A[N-1-i]:
                cnt1 += 1
    for i in range(N):
        for j in range(N):
            if A[N-1-i] < A[j]:
                cnt2 += 1
    
    return cnt1, cnt2
    
    
x, y = cal(A,N)

tmp = int(y*K*(K-1)/2)
ans = tmp + x*K
print(int(ans%(10**9+7)))

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
l = list(map(int, input().split()))

c=0
for k in range(K, 0, -1):
  for i in range(N):
    for j in range(i,N):
      if l[i] <= l[j]:break
      if l[i] > l[j]:
        c += 1
  c *= k
c = c % (10*9+7)
print(c)

Submission status: Wrong Answer

Solution code:
import bisect
from collections import deque
import sys
MAX_INT = int(10e9)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N,K = IL()
a = IL()

cnt = 0
for left in range(N):
  for right in range(left+1,N):
    if a[left] > a[right]:
      cnt += 1
cnt = cnt*K %mod

a.sort()
tmp = 0
for i in range(N-1):
  if a[i+1] > a[i]:
    tmp = i+1
  cnt += (((K-1)/2)*((2*tmp+(K-2)*tmp) %mod)) %mod

print(int(cnt) %mod)

"""
6 3
1 1 2 2 3 3

10 3
10 9 8 7 6 5 4 3 2 1
"""

Submission status: Wrong Answer

Solution code:
import numpy as np
N, K = map(int,input().split())
A= list((map(int, input().split())))
A = np.array(A)
an = int(K*(K+1)/2)%(10**9+7)
a = int((K-1)*(K)/2)%(10**9+7)
au =0
al = 0
for i in range(N):
    au += sum(A[i+1:]<A[i])%(10**9+7)
    al += sum(A[:i]<A[i])%(10**9+7)
print((au*an%(10**9+7)+(al*a%(10**9+7))%(10**9+7)))