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:
import bisect
n,k = map(int,input().split())
a = list(map(int,input().split()))

# i が与えられたとき a1~aiまでの和を計算する( O(log n) )
def bitsum(bit,i):
    s = 0
    while i > 0:
        s += bit[i]
        i -= i&(-i)
    return s
    
# i と x が与えられたとき ai += x とする ( O(log n) )
def bitadd(bit,i,x):
    while i <= n:
        bit[i] += x
        i += i&(-i)
    return bit
    
#################################
import math

#bitの構築
n_ = int(math.log2(2000)) + 1
bit = [0] * (2**n_)*2
bit.append(0)

################################
ass = 0
for j in range(n):
    ass += j-bitsum(bit,a[j])
    #bitsum(bit,a[j]): j-1番目までの中でa[j]以下のもの
    bit = bitadd(bit,a[j],1)

res = 0
b = sorted(a)

for e in b:
    kw = bisect.bisect_right(b,e)
    res += n-kw

mod = 10**9+7

print((k*ass%mod+res*k*(k-1)//2%mod)%mod)

Submission status: Wrong Answer

Solution code:
I=lambda:input()
L=lambda:list(map(int,I().split()))
n,k=L()
a=L()
m=10**9+7
kk=(k*(k+1)//2)%m
k=(k*(k-1)//2)%m
from bisect import bisect_right
x=0
for i in range(n):
  if i!=0:
    l=a[:i]
    l.sort()
    b=bisect_right(l,a[i])
    x+=(b*k)%m
  if i!=n-1:
    l=a[i+1:]
    l.sort()
    b=bisect_right(l,a[i])
    x+=(b*kk)%m
  x%=m
print(x)

Submission status: Wrong Answer

Solution code:
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7

R = {}
L = []
for i in A:
  if i not in R:
    R[i] = 1
    L.append(i)
  else:
    R[i] += 1

L.sort(reverse = True)

k = 0
t = R[L[0]]
for i in range(1, len(L)):
  k = (k + t) % MOD
  t += R[L[i]]

ans = k * ((K * (K - 1)) // 2) % MOD

k = 0
for i in range(N):
  for j in range(i):
    if A[i] < A[j]:
      k += 1
ans = (ans + k * K) % MOD

print(ans)

Submission status: Wrong Answer

Solution code:

C = [0]*2010

(N,K) = (int(i) for i in input().split(" "))

A = [int(i) for i in input().split()]

B = [0]*2010

D = [0]*2010

mod = 10**9+7

for i,a in enumerate(A):
	B[i] = sum(C[a+1:])
	C[a] += 1
for i in range(2005):
	C[2005-i] += C[2005-i+1]
ans = (sum(B)*K)%mod
for i,a in enumerate(A):
	ans += (C[a+1]*K*(K-1)/2)%mod
	ans %= mod
print(int(ans))

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = [int(a) for a in input().split()]
P = 10**9+7
a = 0
b = 0
for i in range(N):
    for j in range(i):
        if A[i] < A[j]:
            a += 1
        b += 1

print((a*K+b*K*(K-1)//2)%P)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10**9+7
cnt = 0
for _ in range(n):
    for i in range(n-1):
        if A[i] > A[i+1]:
            A[i], A[i+1] = A[i+1], A[i]
            cnt += 1
AA = A*2
nn = len(AA)
out_cnt = 0
for _ in range(nn):
    for i in range(nn-1):
        if AA[i] > AA[i+1]:
            AA[i], AA[i+1] = AA[i+1], AA[i]
            out_cnt += 1
ans = (k*cnt % MOD + out_cnt * (k*(k-1)//2) % MOD) % MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def answer(arr, k):
    _mod = (10**9+7)
    left = 0
    right = 0
    for i in range(len(arr)):
        for j in range(i, len(arr)):
            if arr[i] > arr[j]:
                left += 1
            if arr[i] < arr[j]:
                right += 1
    leftStack = 0
    rightStack = 0
    for i in range(1, k+1):
        leftStack = (leftStack+(i*left))%_mod
        if i != k:
            rightStack = (rightStack + (i*right))%_mod

    return (leftStack + rightStack)%_mod

n, k = map(int, input().split())
arr = list(map(int, input().split()))
print(answer(arr, k))

Submission status: Time Limit Exceeded

Solution code:
import itertools

N, K = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10**9 + 7

# print(A * K)

ans = 0
meets = [0] * N
for i in range(N):
    for j in range(N):
        ans += int(i < j and A[i] > A[j])
        meets[i] += int(A[i] > A[j])
ans *= K
# print(meets)

ans += sum(meets) * K * (K - 1) // 2

print(ans % MOD)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
ans1,ans2=0,0
i = 0
while i < n-1:
    j = i+1
    while j < n:
        if a[i]>a[j]:
            ans1+=1
        j+=1
    i+=1
i = 0
while i < 2*n-1:
    j = i+1
    while j < 2*n:
        if a[i%n]>a[j%n]:
            ans2+=1
        j+=1
    i+=1
print((ans1*((1+k)*k)//2+(ans2-3*ans1)*((1+(k-1))*(k-1))//2)%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
ans1,ans2=0,0
for i in range(n-1):
    for j in range(i+1,n):
        if a[i]>a[j]:
            ans1+=1
for i in range(2*n-1):
    for j in range(i+1,2*n):
        if a[i%n]>a[j%n]:
            ans2+=1
print((ans1*((1+k)*k)//2+(ans2-3*ans1)*((1+(k-1))*(k-1))//2)%(10**9+7))

Submission status: Time Limit Exceeded

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

MOD = 10**9 + 7

ans = 0
for i in range(N):
    for j in range(N):
        l, r = 0, 0
        if A[i] > A[j] and i < j:
            l += 1
        if A[i] > A[j] and i > j:
            r += 1
        ans += (1+K)*K//2*l
        ans += K*(K-1)//2*r
        ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
def counter(A):
    cnt = 0
    for i,ai in enumerate(A):
        cnt += sum(a < ai for a in A[i+1:])
    return cnt

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

one_a = counter(A)
two_a = counter(A*2)

if A == sorted(A,reverse=True):
    ans = one_a * sum(range(1,K+1))
elif A == sorted(A):
    ans = two_a * sum(range(1,K)) 
else:
    ans = ((two_a-one_a*2) * sum(range(1,K)) ) + (K*one_a)
print(ans%((10**9)+7))

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    ans = 0
    maxa = max(a)
    dp = [0] * maxa
    for i in range(k * n):
        ans += dp[a[i%n] - 1]
        ans %= 1000000007
        dp = [(x + 1) % 1000000007 for x in dp[:a[i%n] - 1]] + dp[a[i%n] - 1:]
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

count = 0
for i in range(N*K-1):
    for j in range(i+1, N*K):
        B_i = A[i % N]
        B_j = A[j % N]
        if B_i > B_j:
            count += 1
        count %= 1000000007
print(count)

Submission status: Time Limit Exceeded

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

mod = 10 ** 9 + 7
k = k % mod
mod2 = 2 ** (mod-2) % mod
# 配列内で自身より小さい数の個数　前後別に求める
b = [[0, 0] for _ in range(n)]
for i in range(n):
    for j in range(n):
        if a[i] > a[j]:
            if i > j:
                b[i][0] += 1
            elif i < j:
                b[i][1] += 1
    b[i][0] = b[i][0] % mod
    b[i][1] = b[i][1] % mod
ans = 0
# kまでの和　後ろの数用
sigmakp = (((k * (k+1)) % mod) * mod2) % mod
#sigmakp = int(sigmakp)
# k-1までの和　前の数用
sigmakn = (((k * (k-1)) % mod) * mod2) % mod
#sigmakn = int(sigmakn)

for i in range(n):
    mae = (sigmakp * b[i][1]) % mod
    ushiro = (sigmakn * b[i][0]) % mod
    ans = ((mae + ushiro) % mod + ans) % mod 
print(ans)

Submission status: Time Limit Exceeded

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

mod = 10 ** 9 + 7
k = k % mod
mod2 = 2 ** (mod-2) % mod
# 配列内で自身より小さい数の個数　前後別に求める
b = [[0, 0] for _ in range(n)]
for i in range(n):
    for j in range(n):
        if a[i] > a[j]:
            if i > j:
                b[i][0] += 1
            elif i < j:
                b[i][1] += 1
    b[i][0] = b[i][0] % mod
    b[i][1] = b[i][1] % mod
ans = 0
# kまでの和　後ろの数用
sigmakp = (((k * (k+1)) % mod) * mod2) % mod
sigmakp = int(sigmakp)
# k-1までの和　前の数用
sigmakn = (((k * (k-1)) % mod) * mod2) % mod
sigmakn = int(sigmakn)

for i in range(n):
    mae = (sigmakp * b[i][1]) % mod
    ushiro = (sigmakn * b[i][0]) % mod
    ans = ((mae + ushiro) % mod + ans) % mod 
print(ans)

Submission status: Time Limit Exceeded

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

A = list(map(int, input().split()))
AA = []
for i in range(2):
    AA.extend(A)

x = 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]
            x += 1
M = 10**9 + 7

y = 0
NN = N*2
for i in range(NN):
    for j in range(NN-1, i, -1):
        if AA[j] < AA[j-1]:
            AA[j], AA[j-1] = AA[j-1], AA[j]
            y += 1

a = (K*x)
b = (y - 2*x) * (K*(K-1)//2)
ans = ((a+b)  % M)
print(int(ans))

Submission status: Time Limit Exceeded

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

A = list(map(int, input().split()))
AA = []
for i in range(2):
    AA.extend(A)

x = 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]
            x += 1
M = 10**9 + 7

y = 0
NN = N*2
for i in range(NN):
    for j in range(NN-1, i, -1):
        if AA[j] < AA[j-1]:
            AA[j], AA[j-1] = AA[j-1], AA[j]
            y += 1

a = (K*x) % M
b = (y - 2*x) * int( (K*(K-1)//2) % M)
ans = ((a+b)  % M)
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
N,K=(input().split())
N,K=int(N),int(K)
seq=list(input().split())
seq=[int(x) for x in seq]
cou=0
C=0
inc=0
for i in range(len(seq)):
    for j in range(i+1,len(seq)):
        if seq[i]>seq[j]: cou+=1
        if seq[i]<seq[j]: inc+=1
for m in range(K):
    C+=((K-m)*cou+m*inc)%1000000007
    C=C%1000000007
C=C%1000000007
print(C)

Submission status: Time Limit Exceeded

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

A = list(map(int, input().split()))
AA = []
for i in range(2):
    AA.extend(A)

x = 0
for i in range(len(A)):
    for j in range(len(A)-1, i, -1):
        if A[j] < A[j-1]:
            A[j], A[j-1] = A[j-1], A[j]
            x += 1
M = 10**9 + 7

y = 0

for i in range(len(AA)):
    for j in range(len(AA)-1, i, -1):
        if AA[j] < AA[j-1]:
            AA[j], AA[j-1] = AA[j-1], AA[j]
            y += 1

a = (K*x) % M
b = int(y - 2*x) * int( (K*(K-1)//2) % M)
ans = ((a+b)  % M)
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
from numpy import array
N, K = list(map(int, input().split()))
A = array(list(map(int, input().split())))
div = 1000000007
s = 0
s2 = 0
for i, n in enumerate(A):
    tmp = A < n
    s += int(sum(tmp[i+1:]))
    s2 += int(sum(tmp))

print(((s * K) + (s2 * (K-1) * K // 2)) % div)

Submission status: Time Limit Exceeded

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

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

x=10**9+7
y=2**(x-2)%x

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

ans1=a*k%x
ans2=n*(n-1)*y%x
ans3=k*(k-1)*y%x
ans=(ans1+ans2*ans3)%x

print(ans)

Submission status: Time Limit Exceeded

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

count1 = 0
for i in range(N):
    for j in range(i + 1, N):
        if A[i] == minA:
            continue
        if A[i] > A[j]:
            count1 += 1

A2 = A + A[::]
# count2 = 0
# for i in range(N * 2):
#     for j in range(i + 1, N * 2):
#         if A2[i] > A2[j]:
#             count2 += 1

count2 = count1
for i in range(N):
    for j in range(i + 1, N * 2):
        if A2[i] == minA:
            continue
        if A2[i] > A2[j]:
            count2 += 1

A3 = A + A[::] + A[::]
# count3 = 0
# for i in range(N * 3):
#     for j in range(i + 1, N * 3):
#         if A3[i] > A3[j]:
#             count3 += 1

count3 = count2
for i in range(N):
    for j in range(i + 1, N * 3):
        if A3[i] == minA:
            continue
        if A3[i] > A3[j]:
            count3 += 1

diff1 = count2 - count1
diff2 = count3 - count2
diffx = diff2 - diff1

bn_last = diff1 + diffx * (K - 2)
bn_sum = ((diff1 + bn_last) * (K - 1)) // 2
an_sum = count1 + bn_sum

if K == 1:
    print(count1)
elif K == 2:
    print(count2)
else:
    print(an_sum % ((10 ** 9) + 7))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n, k= (int(i) for i in input().split())
a = list(map(int, input().split()))

an = np.array(a)
bn = an.copy()

#print(bn)

for _ in range(k-1):
  an = np.concatenate([an, bn])

ans = 0

for i in range(n * k - 1):
  #print(an[i])
  for j in range(n * k - 1):
    if(i > j):
      continue
    #print(an[i],an[j+1])
    if(an[i] > an[j+1]):
      #print("ok")
      ans += 1
ans % 1000000007
print(ans)

Submission status: Time Limit Exceeded

Solution code:
M, K = map(int, input().split())
list = [int(i) for i in input().split()]
t_list = [] 
count = 0
for i in range(K):
    for j in list :
        t_list.append(j)
t_list.reverse()
for i in range(K * len(list)):
    for j in t_list[i+1:]:
        if t_list[i] < j:
            count += 1
count = count % (10**9 + 7)
print(count)

Submission status: Time Limit Exceeded

Solution code:
tmp = input().split()
n = tmp[0]
k = tmp[1]

a = input().split()
count = 0
if 1 <= int(n) and int(n) <= 2000:
    if 1 <= int(k) and int(k) <= 10**9:
        if 1 <= len(a) and len(a) <= 2000:
            tmp = a
            for i in range(int(k)-1):
                # print(i)
                for j in range(int(n)):
                    tmp.append(a[j])
            # print(tmp)

            for i in range(len(tmp)):
                for j in range(len(tmp)):
                    if i == j:
                        continue
                    if i < j:
                        if int(tmp[i]) > int(tmp[j]):
                            count += 1
                            # print("DA")
            print(count)
            # print(n)
            # print(k)
            # print(a)

Submission status: Time Limit Exceeded

Solution code:
from decimal import Decimal

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

A = [int(i) for i in input().split() ]

counter = 0 

for i in range(N):
	for j in range(i+1, N):
		if A[i] < A[j]:
			counter += (Decimal(K)*Decimal(K-1)/2)%(Decimal(10**9 + 7))
		if A[i] > A[j]:
			counter += (Decimal(K)*Decimal(K+1)/2)%(Decimal(10**9 + 7))

print(counter%(Decimal(10**9 + 7)))

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))*2
count1=0
count2=0
ans=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)%(10**9+7))//2)+count1*k)%(10**9+7)
  print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

i = np.array(list(map(int, input().split())))
 
N = i[0]
K = i[1]

B = np.array(list(map(int, input().split())))

C = np.array([e for row in [B for i in range(K)] for e in row])

cnt=np.array([e for row in [[1 for j in range(i+1,len(C)) if C[i] > C[j]] for i in range(len(C)-1)] for e in row])
print(len(cnt) % (10**9 + 7))

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))*2
count1=0
count2=0
ans=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%(10**9+7)*((k-1)%(10**9+7))//2)+count1*k)%(10**9+7)
  print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
def bubble_sort(A):
    cnt = 0
    for i in range(len(A)):
        for j in range(len(A)-1, i, -1):
            if A[j] < A[j-1]:
                A[j], A[j-1] = A[j-1], A[j]
                cnt += 1
    return cnt
n,k=map(int, input().split())
a = list(map(int, input().split()))
b = list()
for i in range(0,k):
    for j in a:
      b.append(j)
print(bubble_sort(b) % (10**9+7))

Submission status: Time Limit Exceeded

Solution code:
nk = input().split()
n = int(nk[0])
k = int(nk[1])

a = input().split()
a = [int(i) for i in a]
aa = a
for i in range (k-1):
    aa.extend(a)

count = 0
for i in range(len(aa)):

        xx = aa[0:i]
        for e in range(len(xx)):
            
            if aa[i] < aa[e] :
                #print(i)
                #print(e)
                count = count+1
                
                #print(aa[i])
                #print(aa[e])
            
            
z = count % (10**9 + 7)
print(z)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().strip().split(' '))
a = list(map(str, input().strip().split(' ')))
MOD = 1000000007
# 一周期内
bn = 0
for i in range(n-1):
  for j in range(n-1-i):
    if int(a[i]) > int(a[i+j+1]):
      bn = bn + 1
# 次の周期も考える
bm = 0
for i in range(n):
  for j in range(n):
    if int(a[i]) > int(a[j]):
      bm = bm + 1
if k % 2 == 0:
  bm = (bm % MOD) * ((k // 2) % MOD) * (k-1 % MOD)
else:
  bm = (bm % MOD) * (k % MOD) * (((k-1) // 2) % MOD)
s = (bn % MOD) * (k % MOD) + (bm % MOD)
print(s % MOD)

Submission status: Time Limit Exceeded

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

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

Blen = N * K

B = []

i = 0
while i < Blen:
    for j in range(0, N, 1):
        B.append(A[j])
        i += 1

ans = int(0)

for l in range(0, Blen - 1, 1):
    for m in range(0, Blen, 1):
        if l < m and B[l] > B[m]:
                ans += 1

ret = ans % 1000000007
print(ret)

Submission status: Time Limit Exceeded

Solution code:

from decimal import *
getcontext().prec = 28
n, k = map(int,input().split())
a = list(map(int,input().split()))
inner = Decimal(0)
outer = Decimal(0)
for i in range(0,n):
    for j in range(0,n):
        if a[i] > a[j]:
            outer += 1
            if i < j:
                inner += 1

b = (Decimal(Decimal(inner) * Decimal(k)) + Decimal(Decimal(outer) * Decimal(Decimal(k) * Decimal(k-1)) / 2))
print(Decimal(Decimal(b)%Decimal(1000000007)))

Submission status: Time Limit Exceeded

Solution code:
# 初期データ
B = []
data_1 = input().split(" ")
A = input().split(" ")
A = [int(s) for s in A]
N = int(data_1[0])
K = int(data_1[1])


def inversion(lis,K):
    count = 0
    
    for i in range(K):
        for _i in range(len(lis)):
            for j in range(K):
                for _j in range(len(lis)):
                    
                    I = (i-1)*len(lis) + _i
                    J = (j-1)*len(lis) + _j
                    if lis[_i] > lis[_j] and I < J:
                        count += 1
    return count
            



print(inversion(A,K))

Submission status: Time Limit Exceeded

Solution code:
nk = list(map(int,input().split()))
a  = list(map(int,input().split()))

s = nk[1]*nk[0]

b = []

for i in range(nk[1]):
    b += a

def bubble_sort(A,B):
    cnt = 0
    for j in range(B):
        for l in range(B-1, j, -1):
            if A[l] < A[l-1]:
                A[l], A[l-1] = A[l-1], A[l]

                cnt += 1
    return int(cnt)

ans = bubble_sort(b,s)
ans = ans % 1000000007
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n,k = map(int,input().split())
arr = list(map(int,input().split()))
arr = np.array(arr)

count = 0
mod = 10**9 + 7

for j in range(n):
    for i in range(1,n):
        head = arr[0]
        if head > arr[i]:
            if i+j < n: 
                count += (k*(k+1)//2) % mod
                count %= mod
            else:
                count += (k*(k-1)//2) % mod
                count %= mod
    arr = np.roll(arr, -1)
    
count %= mod
print(count)

Submission status: Time Limit Exceeded

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

b = []
for i in range(k):
  b = b + a

def count_inversion(sequence):
    return sum(sum(m<n for m in sequence[i+1:]) for i,n in enumerate(sequence))
  
ans = count_inversion(b)

print(ans % (1000000000 + 7))

Submission status: Time Limit Exceeded

Solution code:
i = list(map(int, input().split()))
 
N = i[0]
K = i[1]

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

C = [e for row in [B for i in range(K)] for e in row]

cnt=[e for row in [[1 for j in range(i+1,len(C)) if C[i] > C[j]] for i in range(len(C)-1)] for e in row]
print(len(cnt) % (10**9 + 7))

Submission status: Time Limit Exceeded

Solution code:
(N,K)=list(map(int,input().split()))
A=list(map(int,input().split()))
B=[]
for i in range(K):
    B=B+A
count=0
for i in range(len(B)):
    for j in range(i,len(B)):
        if (B[i]>B[j]):
            count=count+1
M=10**9+7
count=count%M
print(count)

Submission status: Time Limit Exceeded

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

b = []
for i in range(k):
  b = b + a

ans = 0
  
for i in range(k * n - 1):
  for j in range(i, k * n):
    if b[i] > b[j]:
      ans += 1

print(ans % (1000000000 + 7))

Submission status: Time Limit Exceeded

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

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

A2 = A + A[::]
# count2 = 0
# for i in range(N * 2):
#     for j in range(i + 1, N * 2):
#         if A2[i] > A2[j]:
#             count2 += 1

count2 = count1
for i in range(N):
    for j in range(i + 1, N * 2):
        if A2[i] > A2[j]:
            count2 += 1


A3 = A + A[::] + A[::]
# count3 = 0
# for i in range(N * 3):
#     for j in range(i + 1, N * 3):
#         if A3[i] > A3[j]:
#             count3 += 1

count3 = count2
for i in range(N):
    for j in range(i + 1, N * 3):
        if A3[i] > A3[j]:
            count3 += 1

diff1 = count2 - count1
diff2 = count3 - count2
diffx = diff2 - diff1

bn_last = diff1 + diffx * (K - 2)
bn_sum = ((diff1 + bn_last) * (K - 1)) // 2
an_sum = count1 + bn_sum

if K == 1:
    print(count1)
elif K == 2:
    print(count2)
else:
    print(an_sum % ((10 ** 9) + 7))

Submission status: Time Limit Exceeded

Solution code:
nk = input().split()
n = int(nk[0])
k = int(nk[1])

a = input().split()
a = [int(i) for i in a]
aa = a
for i in range (k-1):
    aa.extend(a)

count = 0
for i in range(len(aa)):

    
        for e in range(len(aa)):
    
            if i < e:
                break
            
            if aa[i] < aa[e] :
                #print(i)
                #print(e)
                count = count+1
                
                #print(aa[i])
                #print(aa[e])
            
            
z = count % (10**9 + 7)
print(z)

Submission status: Time Limit Exceeded

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right
from heapq import heappush, heappop

import re
# import numpy as np
# from scipy.misc import comb

# 再帰がやばいとき
import sys
sys.setrecursionlimit(10**9)

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e30)
MOD = int(1e9)+7 # 10^9 + 7

# field[H][W]
def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]

########

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 power_func(a,n,p):
  bi=str(format(n,"b"))#2進表現に
  res=1
  for i in range(len(bi)):
    res=(res*res) %p
    if bi[i]=="1":
      res=(res*a) %p
  return res

def main():
    N, K = l_inpl()
    A = l_inpl()
    a1 = count_inversion(A)
    b1 = (count_inversion(A*2) - count_inversion(A))
    b2 =  (count_inversion(A*3) - count_inversion(A*2))
    c1 = b2 - b1
    print((a1*K+c1*K*(K-1)//2)%MOD)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

count1 = 0
for i in range(N):
    for j in range(i + 1, N):
        # print(i, j)
        if A[i] > A[j]:
            # print(A[i], A[j])
            count1 += 1
# print(count1)

A2 = A + A[::]
count2 = 0
for i in range(N * 2):
    for j in range(i + 1, N * 2):
        # print(i, j)
        if A2[i] > A2[j]:
            # print(A[i], A[j])
            count2 += 1
# print(count2)

A3 = A + A[::] + A[::]
count3 = 0
for i in range(N * 3):
    for j in range(i + 1, N * 3):
        if A3[i] > A3[j]:
            count3 += 1
# print(count3)

diff1 = count2 - count1
diff2 = count3 - count2
diffx = diff2 - diff1

bn_last = diff1 + diffx * (K - 2)
# print(bn_last)
bn_sum = ((diff1 + bn_last) * (K - 1)) // 2
# print(bn_sum)
an_sum = count1 + bn_sum

if K == 1:
    print(count1)
elif K == 2:
    print(count2)
else:
    print(an_sum % ((10 ** 9) + 7))

Submission status: Time Limit Exceeded

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

n,k=map(int,input().split())
a =list(map(int,input().split()))
#a = [input() for i in range(n)]
b = a
for i in range(k-1):
  b = b + a
print(count_inversion(b)%1000000007)

Submission status: Time Limit Exceeded

Solution code:
i = list(map(int, input().split()))
 
N = i[0]
K = i[1]

B = list(map(int, input().split()))
A = [B for i in range(K)]

C = [e for row in A for e in row]

cnt=0
for i in range(len(C)-1):
    for j in range(i+1,len(C)):
        if C[i] > C[j]:
            cnt += 1
print(cnt % (10**9 + 7))

Submission status: Time Limit Exceeded

Solution code:
# 初期データ
B = []
data_1 = input().split(" ")
A = input().split(" ")
N = int(data_1[0])
K = int(data_1[1])

#転倒関数
def inversion(lis):
    count = 0
    for i in range(len(lis)):
        for j in range(len(lis)):
            if lis[i] > lis[j] and i < j:
                count += 1
    
    return count
            


for i in range(K):
    B += A
B = [int(s) for s in B]


print(inversion(B))

Submission status: Time Limit Exceeded

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

b = []
for i in range(k):
  b = b + a

ans = 0
  
for i in range(k * n - 1):
  for j in range(i, k * n):
    if j <= k * n - 1 and b[i] > b[j]:
      ans += 1

print(ans % (1000000000+7))

Submission status: Time Limit Exceeded

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

inv_A = 0
for i in range(0,N):
  for j in range(0,N):
    if i<j and A[i] > A[j]:
      inv_A += 1

inv_sorted_A = 0
for i in range(0,N):
  for j in range(0,N):
    if i<j and sorted_A[i] < sorted_A[j]:
      inv_sorted_A += 1

count = inv_A
for i in range(1,K):
  count += (inv_sorted_A * i) % 1000000007 + inv_A % 1000000007

print(count)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
#10^9+7  で割った余り
k = k %(1000000000 + 7)
#その文字より前に大きな数字
before_cnt = 0
#その文字より後に大きな数字
after_cnt = 0
n_list = list(map(int, input().split()))
for i in range(n):
  for j in range(n):
    if n_list[i] > n_list[j]:
      #print("i",i,"j",j)
      if i < j:
        after_cnt+=1
      else:
        before_cnt+=1
kurikaesi = 0
for i in range(1, k+1):
  kurikaesi += i
#print("kurikaesi",kurikaesi)
#print(after_cnt, before_cnt)
print((before_cnt*(kurikaesi-k) + after_cnt*kurikaesi)%(1000000000+7))

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
def modpow(a,n,mod):
    res = 1
    while n > 0:
        if n & 1:
            res = res * a % mod
        a = a * a % mod
        n >>= 1
    return res

def modinv(a,mod):
    return modpow(a,mod - 2,mod)


one = 0
for i in range(N):
    for j in range(i+1,N):
        if A[i] > A[j]:
            one+=1
two = 0
AA = A+A
for i in range(N*2):
    for j in range(i+1,N*2):
        if AA[i] > AA[j]:
            two+=1
two -= one*2
MOD = 10**9+7

print((one*K%MOD + two*(((K-1)*(K)//2)))%MOD)

Submission status: Time Limit Exceeded

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

b = []
for i in range(k):
  b = b + a

ans = 0
  
for i in range(len(b)):
  for j in range(i, len(b)):
    if i <= j and j <= k * n -1 and b[i] > b[j]:
      ans += 1

print(ans % (1000000000 + 7))

Submission status: Time Limit Exceeded

Solution code:
A = [10,998244353]
B = [10,9,8,7,5,6,3,4,2,1]

N = A[0]
K = A[1]
count = 0
 
list = []
 
for i in range(N):
  for j in range(i,N):
    if B[i] > B[j]:
      count+=1


for sabun in range(1,K):
    count = count*sabun + count
    
count = count%(10**9 + 7)
print(count)

Submission status: Time Limit Exceeded

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

b = []
for i in range(k):
  b = b + a

ans = 0
  
for i in range(len(b)):
  for j in range(len(b)):
    if i <= j and j <= k * n -1 and b[i] > b[j]:
      ans += 1

print(ans % (1000000000 + 7))

Submission status: Time Limit Exceeded

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

b = []
for i in range(k):
  b = b + a

ans = 0
  
for i in range(len(b)):
  for j in range(i, len(b)):
    if i <= j and j <= k * n -1 and b[i] > b[j]:
      ans += 1

print(ans % (1000000000+7))

Submission status: Time Limit Exceeded

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

b = []
for i in range(k):
  b = b + a

ans = 0
  
for i in range(len(b)):
  for j in range(len(b)):
    if i <= j and j <= k * n -1 and b[i] > b[j]:
      ans += 1

print(ans % (1000000000+7))