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:
M = 10**9+7
N,K = map(int, input().split())
A = list(map(int, input().split()))
A_ = sorted(A, reverse = True)
ans = 0
ans_ = 0
for i in range(0,N-1):
    for j in range(i+1,N):
        if A[i] > A[j]:
            ans += 1
        if A_[i] > A_[j]:
            ans_ += 1

print((((int(K*(K-1)/2)%M)*ans_)%M+ans*K)%M)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import Counter
MOD = 10**9 + 7
n, k = map(int, input().split())
a = list(map(int, input().split()))
li = [0] * (2001)
for i in range(n):
    for j in range(i + 1, n):
        if a[i] > a[j]:
            li[a[i]] += 1
ans = 0
dic = Counter(a)
num = 0
for i in sorted(dic.keys()):
    if i > 1:
        ans += num * (k - 1) * k // 2 + li[i] * k
        ans %= MOD
    num += dic[i]
print(ans)

Submission status: Wrong Answer

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

sf=[0]*n
sb=[0]*n

for i in range(n):
    for j in range(n):
        if i<j:
            if a[i]>a[j]:
                sf[i]+=1
        else:
            if a[i]>a[j]:
                sb[j]+=1
ans=0
for i in range(n):
    ans+=k*sf[i]+k*(k-1)*(sf[i]+sb[i])/2

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

Submission status: Wrong Answer

Solution code:
import math

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

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

cnt_2 = 0
for i in range(len(A)):
  for j in range(len(A)):
    if A[i] > A[j]:
      cnt_2 += 1

cnt = cnt_1 * K + cnt_2 * int((K-1)*K/2)

print(cnt % 1000000007)

Submission status: Wrong Answer

Solution code:
import numpy as np

N, K = map(int, input().split())
A = np.array(input().split(), dtype=np.int64)

B = 0
C = 0

for i in range(N):
    D = A[i::]
    B += np.sum(D < A[i]) % (10**9 + 7)
    C += np.sum(A < A[i]) % (10**9 + 7)
    

E = B * K % (10**9 + 7)
F = C * (((K-1)*K/2) % (10**9 + 7)) % (10**9 + 7)

print(int((E+F) % (10**9 + 7)))

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = [int(x) for x in input().split()]
ans_base = 0
ans_base_rev = 0
ans = 0
big = (10**9)+7
for i in range(N-1):
    for k in range(i + 1, N):
        if A[i] > A[k]:
            ans_base += 1
        if A[i] < A[k]:
            ans_base_rev += 1
#ans_base %= big
val_p = (K * (K + 1)) / 2
val_m = (K * (K - 1)) / 2
#val_m %= big
#val_p %= big
ans = ans_base * val_p+ans_base_rev * val_m
ans %= big
print(int(ans))

Submission status: Wrong Answer

Solution code:
import bisect
mod = 10**9+7
def main():
    n,k=map(int,input().split(' '))
    a = list(map(int,input().split(' ')))
    a_fall= 0
    a_rev = sorted(a,reverse=True)
    u_cnt = 0
    for i in range(n-1):
        a_sorted = sorted(a[i+1:])
        a_fall += bisect.bisect_left(a_sorted,a[i])
        a_fall %=mod
    for i in range(n-1):
        if a_rev[i] > a_rev[i+1]:
            u_cnt += n-i-1
    ans = a_fall*k+u_cnt*k*(k-1)//2
    ans %= mod
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

waru = 10 ** 9 + 7;

for i in range(n) :
	a[i] = int(a[i]);

kaisu = [0] * n;
usiro = [0] * n;

for i in range(n) :
	for j in range(n) :
		if a[i] > a[j] :
			kaisu[i] += 1;
			if i < j :
				usiro[i] += 1;

ans = 0;
for i in range(n) :
	if k % 2 == 0 :
		ans += ((((k-1)%waru) * ((k/2)%waru) * (kaisu[i]%waru))%waru + ((k%waru) * (usiro[i]%waru)) %waru )%waru
	else :
		ans += (((((k-1)/2)%waru) * (k%waru) * (kaisu[i]%waru))%waru + ((k%waru) * (usiro[i]%waru)) %waru )%waru
	
print(int(ans%waru));

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
cnt = 0
for i in range(n):
  for j in range(i+1,n):
    if a[i] > a[j]:
      cnt += 1
print((cnt*k)%(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
    second_tenti = np.count_nonzero(A>Alist)
    counter += (second_tenti*K**2-(2*second_tenti*K)+second_tenti)/2
print(int(counter%(10**9+7)))

Submission status: Wrong Answer

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

sort_a = sorted(a, reverse=True)
num_a = 0
num_b = 0

for i in range(n-1):
    for j in range(i+1, n):
        if a[j] < a[i]:
            num_a += 1
        if sort_a[j] < sort_a[i]:
            num_b += 1

total = (k * num_a + ((k*(k-1))/2)*num_b) % 1000000007

if k == 1:
    print(num_a)
else:
    print(int(total))

Submission status: Wrong Answer

Solution code:
import sys
from math import factorial

MOD = 1000000007

input = sys.stdin.readline

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

a1 = [0] * n
a2 = [0] * n

for i, ai in enumerate(a):
    for j in range(n):
        if ai > a[j]:
            a1[i] += 1
            if j > i:
                a2[i] += 1

k %= MOD
fact_k = factorial(k - 1) % MOD

ans = 0
for ai in a2:
    ans = (ans + (ai * k) % MOD) % MOD

for ai in a1:
    ans = (ans + (ai * fact_k) % MOD) % MOD

print(ans)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
b = sorted(a)
#print(b.index(a[0]))
ans = 0
in_ = [0]*n # リスト全体でa[i]より小さい数がいくつあるか
after = [0]*n # リストのa[i]以降の数でa[i]より小さい数がいくつあるか
for i in range(n):
    for j in range(n):
        if a[i] > a[j]:
            # 転倒数
            in_[i] += 1
            if i < j:
                after[i] += 1
print(in_)
print(after)
for i in range(n):
    ans += after[i]*k + (k*(k-1)//2) * in_[i]
ans %= 1000000007
print(int(ans))

Submission status: Wrong Answer

Solution code:
def count_inversion(sequence):
    return sum(sum(m<n for m in sequence[i+1:]) for i,n in enumerate(sequence))
n,k=map(int,input().split())
a=list(map(int,input().split()))
for i in range(k-1):
    a+=a
print(a)


print(count_inversion(a)%100000007)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

cna=0
for i,a in enumerate(A):
    for at in A[i+1:]:    
        if a>at:
            cna+=1

cna2=0
for a in A:
    for at in A:    
        if a>at:
            cna2+=1




kt=int((K-1)*(K)/2)

print( (K*cna+(kt*cna2))  %(10**9+7))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# 整数の入力
# スペース区切りの整数の入力
N, K = map(int, input().split())
As = list(map(int, input().split()))

count_base =0
for i in range(N-1):
    for j in range(i+1, N):
        if As[i] > As[j]:
            count_base += 1

count = count_base * (N * K + K *(K-1)/2)

print(count % (pow(10, 9) + 7))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

mod = 10 ** 9 + 7

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


A_dict = defaultdict(list)

for i, num in enumerate(A):
    A_dict[num].append(i)

sorted_A_list = (list(A_dict.items()))
sorted_A_list.sort(key=lambda x: x[0], reverse=True)
# print(A_dict)
# print(sorted_A_list)

tentou = 0
rest = N
for (key, value) in sorted_A_list:  # 次の周回で増える転倒数(1つあたり)
    num_of_this_key = len(value)
    rest -= num_of_this_key
    tentou += num_of_this_key*rest

    # print(tentou)

inside_tentou = 0  # 1内での転倒数
for i, mae in enumerate(A[:-1]):
    for usiro in A[i + 1:]:
        if usiro < mae:
            inside_tentou += 1

    # print((i, inside_tentou))

temp_ans1 = (inside_tentou * K) % mod
temp_ans2 = (1 / 2 * K * (K - 1) * tentou) % mod
ans = (temp_ans1 + temp_ans2) % mod
print(int(ans))

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))

n,k = m()

a = l()

aaa = [0 for i in range(n)]
co = [0 for i in range(2002)]


for i in range(n-1,-1,-1):
    aaa[i] = co[a[i]]
    for j in range(a[i]+1,n+1):
        co[j] += 1


su = 0

for i in range(n-1,-1,-1):
    su += k * aaa[i]
    su %= mod
    su += ((k)*(k-1)//2)*co[a[i]]
    su %= mod


print(su)

Submission status: Wrong Answer

Solution code:
N,K=list(map(int,input().split()))
A=list(map(int,input().split()))
mod=10**9+7
b=0
f=0
for i in range(N):
    for j in range(i+1,N):
        if A[i]>A[j]:
            #print(i,",",j)
            f+=1
           
            
for i in range(N-1,-1,-1):
    for j in range(i-1,-1,-1):
        if A[i]>A[j]:
            b+=1
tmp=(K+1)*K%mod
ans=(f*tmp/2)%mod
tmp=(K-1)*K%mod
ans+=(b*tmp/2)%mod
ans%=mod

print(int(ans))

Submission status: Wrong Answer

Solution code:
MOD = 1000000007
N,K = map(int,input().split())
A = list(map(int,input().split()))
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

def sigma(k):
    return int((1/2)*(k%MOD)*((k+1)%MOD))
#B = []
#for k in range(K):
#    B.extend(A)
#print (bubble_sort(B))
C = []
for k in range(2):
    C.extend(A)
cnt = bubble_sort(A)
#print (cnt)
diff = bubble_sort(C) - 2 * cnt
#print (diff)
a = (K*cnt)%MOD
b = (diff*sigma(K-1))%MOD
print ((a+b)%MOD)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
if n == 1:
  print("0")
  exit()
ans_unit = 0
for i in range(n-1):
  for j in range(i+1, n):
    if a[i] > a[j]:
      ans_unit+=1
if k == 1:
  print(ans_unit)
  exit()
c = sum([a,a], [])
ans_two = 0
for i in range(2*n-1):
  for j in range(i+1, 2*n):
    if c[i] > c[j]:
      ans_two+=1
ans_inc = ans_two - 2*ans_unit
ans = k*ans_unit
ans = ans%1000000007
ans += int(k*(k-1)*ans_inc/2)%1000000007
ans = ans%1000000007
print(ans)

Submission status: Wrong Answer

Solution code:
n, k = input().split()
N = int(n)
K = int(k)
A = [int(a) for a in input().split()]
countAList = []
countBList = []
for j in range(len(A)):
    countA = 0
    countB = 0
    for i in range(len(A)):
        if A[i] < A[j]:
            countB += 1
            if i > j:
                countA += 1
    countAList.append(countA)
    countBList.append(countB)
result = 0

for a, b in zip(countAList, countBList):
    result += K * a + int(b * K * (K - 1) / 2)

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

Submission status: Wrong Answer

Solution code:

n,k=map(int,input().split())
k=k%(1000000000+7)


a=list(map(int,input().split()))
ans=0

for i in range(len(a)):
    p=sum([1 for j in a[i:] if a[i]>j])
    q=sum([1 for j in a if a[i]>j])
   # print(p,q)
    s=int(p*(k%(1000000000+7)))
    t=int(q*((((k-1)*k)/2)%(1000000000+7)))
    ans+=s+t


print(int(ans%(1000000000+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
    second_tenti = np.count_nonzero(A>Alist)
    counter += second_tenti*K**2-(2*second_tenti*K)+second_tenti/2
print(int(counter%(10**9+7)))

Submission status: Wrong Answer

Solution code:
import math
import sys
import numpy as np
from collections import defaultdict, deque, Counter 
from itertools import accumulate, product, permutations,combinations, combinations_with_replacement
from operator import itemgetter
from bisect import bisect_left,bisect
from heapq import heappop,heappush
from fractions import gcd

max_value = 1000000000
min_value = -1000000000
sys.setrecursionlimit(max_value)

n, k = map(int,input().split())
a_list = list(map(int,input().split()))

big_num = 10**9 + 7
single = 0

for i in range(len(a_list)):
    for j in range(len(a_list)):
        if i < j:
            if a_list[i] > a_list[j]:
                single += 1

coeff = (k*(k+1)//2)%big_num
value = (coeff * single)%big_num

print(int(value))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

mod = 10 ** 9 + 7

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


A_dict = defaultdict(list)

for i, num in enumerate(A):
    A_dict[num].append(i)

sorted_A_list = (list(A_dict.items()))
sorted_A_list.sort(key=lambda x: x[0], reverse=True)
# print(A_dict)
# print(sorted_A_list)

tentou = 0
rest = N
for (key, value) in sorted_A_list:  # 次の周回で増える転倒数(1つあたり)
    num_of_this_key = len(value)
    rest -= num_of_this_key
    tentou += num_of_this_key*rest

    # print(tentou)

inside_tentou = 0  # 1内での転倒数
for i, mae in enumerate(A[:-1]):
    for usiro in A[i + 1:]:
        if usiro < mae:
            inside_tentou += 1

    # print((i, inside_tentou))

temp_ans1 = (inside_tentou * K % mod)
temp_ans2 = 1 / 2 * K * (K - 1) * tentou % mod
ans = (temp_ans1 + temp_ans2) % mod
print(int(ans))

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:])
    print(fir_tenti)
    counter += (K*(fir_tenti*(K+1)))/2
    second_tenti = np.count_nonzero(A>Alist)
    print(second_tenti)
    counter += second_tenti*K**2-(2*second_tenti*K)+second_tenti/2
print(int(counter%(10**9+7)))

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a=list(map(int,input().split()))
b=a+a
cnta=0
cntb=0
for i in range(n-1):
    for j in range(n-1-i):
        j+=i+1
        if(a[i]>a[j]):
            cnta+=1
            cnta=cnta%(1000000000+7)
for i in range(2*n-1):
    for j in range(2*n-1-i):
        j+=i+1
        if(b[i]>b[j]):
            cntb+=1
            cntb=cntb%(1000000000+7)

cntb-=2*cnta
cntak=(cnta*k)%(1000000000+7)
cntbk=(cntb* ((k*(k-1)/2)%(1000000000+7))     )%(1000000000+7)

ans=(cntak+cntbk)%(1000000000+7)

print(int(ans))

Submission status: Wrong Answer

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

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

nums_s = sorted(nums)
a = (count_inversion(nums) % mod) * k
b = count_inversion(nums_s + nums_s) % mod
c = ((k - 1) * k / 2) % mod
print(int((a + b * c) % mod))

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
temae=0
oku=0
for i in range(len(A)):
  for j in range(len(A)):
    if A[i] < A[j]:
      if j > i:
        temae += 1
      elif j < i:
        oku += 1
ans = int((oku*K*(K+1)/2))+int((temae*K*(K-1)/2))
print(ans%1000000007)

Submission status: Wrong Answer

Solution code:
def main():
    n, k = map(int, input().split(" "))
    A = list(map(int, input().split(" ")))

    Anomitenti = 0
    ikotonaritenti = 0
    for index, i in enumerate(A):
        for j in A[index+1:]:
            if i > j:
                Anomitenti += 1
        for j in A:
            if i > j:
                ikotonaritenti += 1

    kosuu = int((1 + (k-1)) * (k-1) / 2)
    result = Anomitenti * k + ikotonaritenti * kosuu
    print(result % 1000000007)

main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

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

a = bubble_sort(A)
b = K * (K + 1) / 2
ans = a * b
print(int(ans % mod))

Submission status: Wrong Answer

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

count = 0

for i in range(len(A)*K+1):
	for j in range(i,len(A)*K+1):
		if A[i%N] > A[j%N]:
			count += 1

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

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
ar=list(map(int,input().split()))
ch1=[0 for i in range(n)]
ch2=[0 for i in range(n)]
for i in range(n):
    aa=0
    for j in range(i):
        if(ar[j]>ar[i]):
            aa+=1
    ch1[i]=aa
for i in range(n):
    ar.append(ar[i])
    aa=0
    for j in range(len(ar)):
        if ar[j]>ar[i]:
            aa+=1
    ch2[i]=aa

ans=0
d=[]
for i in range(n):
    ans+=ch1[i]
    d.append(ch2[i]-ch1[i])
if k!=1:
    for i in range(n):
        ans+=int( ((k-1)/2)*(2*ch2[i]+(k-2)*d[i]) )
print(ans%1000000007)

Submission status: Wrong Answer

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

def count_bigger(sequence):
    count = 0
    for num1 in sequence:
        for num2 in sequence:
            if num1 < num2:
                count += 1
    return count

MAX = 7 + 10**9
N, K = map(int,input().split())
A = list(map(int,input().split()))
ans = (K*count_inversion(A))%MAX + (K*(K-1)/2*count_bigger(A))%MAX
print(int(ans%MAX))

Submission status: Wrong Answer

Solution code:
import math
n,k = map(int, input().split())
a = input().split()
sum = 0
first = 0
a_len = len(a)
for i in range(0, a_len):
  for j in range(0, a_len):
    if a[j] < a[i]:
      print(a[j], a[i])
      sum += 1
      if j > i and a[j] < a[i]:
        first += 1
      
ans = (sum * math.factorial(k-1) + first*k) % (10**9+7)
print(ans)

Submission status: Wrong Answer

Solution code:
def getlist():
	return list(map(int, input().split()))

N, K = getlist()
A = getlist()

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

B = sorted(A)
s = 0
v = 0
c = 0
for i in range(N):
	if B[i] > v:
		c = i
	s += c
	v = B[i]


ans1 = int(((K - 1) * K) / 2)
ans = ans1 * s + K * x
print(ans % 1000000007)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
if n == 1:
  print("0")
  exit()
ans_unit = 0
for i in range(n-1):
  for j in range(i+1, n):
    if a[i] > a[j]:
      ans_unit+=1
if k == 1:
  print(ans_unit)
  exit()
c = sum([a,a], [])
ans_two = 0
for i in range(2*n-1):
  for j in range(i+1, 2*n):
    if c[i] > c[j]:
      ans_two+=1
ans_inc = ans_two - 2*ans_unit
ans = k*ans_unit
ans = ans%1000000007
ans += int(k*(k-1)*ans_inc/2)
ans = ans%1000000007
print(ans)

Submission status: Wrong Answer

Solution code:
N,K= list(map(int, input().split()))
A= list(map(int, input().split()))
AA=sorted(A)
num=0
before=0
for i in A:
    num+=AA.index(i)
num2=0
for i in range(N-1):
    for j in range(i+1,N):
        if A[i]>A[j]:
            num2+=1
hoge=int((K-1)*K/2%1000000007)
hoge=hoge*num%1000000007
hoge2=num2*K%1000000007
hoge=(hoge+hoge2)%1000000007
print(hoge)

Submission status: Wrong Answer

Solution code:
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum_(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


n, k = map(int, input().split())
ppp = list(map(int, input().split()))
bit = Bit(3000)
ans_ = 0

for i, p in enumerate(ppp):
    bit.add(p, 1)
    ans_ += i + 1 - bit.sum_(p)

mod = 10 ** 9 + 7
ans = (ans_ * k) % mod

ppp = sorted(ppp)

ppp_ = set(ppp)
dic1 = {}
dic2 = {}
for i in ppp_:
    dic1[i] = 0
    dic2[i] = 0

for i in ppp:
    dic1[i] += 1
    dic2[i] += 1

k_ = ((k-1) * k / 2) % mod
k_ = int(k_)
for i in ppp_:
    dic1[i] = 0
    ans += k_ * dic2[i] * sum(dic1.values())
    ans %= mod

print(ans)

Submission status: Wrong Answer

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

sort_a = sorted(a, reverse=True)
num_a = 0
num_b = 0

for i in range(n-1):
    for j in range(i+1, n):
        if a[j] < a[i]:
            num_a += 1
        if sort_a[j] < sort_a[i]:
            num_b += 1

total = (k * num_a + int(((k*(k-1))/2)*num_b)) % 1000000007

if k == 1:
    print(num_a)
else:
    print(total)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
mod=10**9+7
srt=sorted(a)
b=[]
for i in range(n):
  b.append(srt.index(a[i]))
print(b)
ans=0
for j in range(n):
  ans+=((b[j]+b[j]*k)*k//2)%mod
res=0
for ii in range(n):
  for ij in range(ii+1):
    if a[ii]>a[ij]:
      res+=1
print((ans-res*k)%mod)

Submission status: Wrong Answer

Solution code:
n, k = [int(i) for i in input().split()]
As = [int(i) for i in input().split()]

init = []
aft = []
for i in range(len(As)):
  initmp = 0
  afttmp = 0
  for j in range(len(As)):
    if i > j and As[i] < As[j]:
      initmp += 1
      afttmp += 1
    elif As[i] < As[j]:
      afttmp += 1
  init.append(initmp)
  aft.append(afttmp)

ans = 0
for i, a in zip(init, aft):
  ans += (float(1)/2) * k * (2 * i + (k-1) * a)
print(ans % ((10**9)+7))

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) % mod) * (K % mod) % mod) / 2) % mod
        # import pdb; pdb.set_trace()
    print(int(count) % mod)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N, K = map(int,input().split())
A = list(map(int,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 cnt_bigger_elem(sequence):
    cnt = 0
    for i in range(N):
        for elem in sequence:
            if sequence[i] < elem:
                cnt += 1
    return cnt


#A = [1,2,3,5,4]

#print(cnt_bigger_elem(A))
#print(count_inversion(A))
BIG_NUM = 10**9+7
ans = int((count_inversion(A) * K + K*(K-1)*cnt_bigger_elem(A)/2)%BIG_NUM)
print(ans)

Submission status: Wrong Answer

Solution code:
#######################################
prime = 10**9+7

def sowa(num):
  return int((1+num)*num/2)
#######################################
n,k = map(int, input().split())
a = list(map(int, input().split()))


tento1 = [sum([1 if a[i]>a[j] else 0 for j in range(i+1,n)]) for i in range(n-1)]
tento2 = [sum([1 if a[i]>a[j] else 0 for j in range(n)]) for i in range(n)]


ret = ((sum(tento1)%prime) *(k%prime) %prime) + ((sum(tento2)%prime) *(sowa(k-1) %prime)%prime)
print(ret%prime)

Submission status: Wrong Answer

Solution code:
import sys
from math import factorial

MOD = 1000000007

input = sys.stdin.readline

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

fact_k = factorial(k - 1) % MOD

a1 = [0] * n
a2 = [0] * n

for i, ai in enumerate(a):
    for j in range(n):
        if ai > a[j]:
            a1[i] += 1
            if j > i:
                a2[i] += 1

ans = 0
for ai in a2:
    ans += (ai * k) % MOD

for ai in a1:
    ans += (ai * fact_k) % MOD

print(ans)

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 = 10**9 + 7
    kk = 0
    if k%2 == 1:
        kk = int(k*(k-1)/2)%x
    else:
        kk = int(k*(k-2)/2+k/2)%x
    a = list(map(int,input().split()))
    c1 = []
    c2 = []
    for i in range(len(a)):
        l = [c(a[i],p) for p in a]
        c1.append(sum(l))
        c2.append(sum(l[i:]))
    ans = 0
    if c1 and c2:
        for i,j in zip(c1,c2):
            ans += (i*kk + k*j)%x
    print(ans)  
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
MOD = 10 ** 9 + 7
def add(a, b):
  return (a + b) % MOD
def sub(a, b):
  return (a - b) % MOD
def mul(a, b):
  return ((a % MOD) * (b % MOD)) % MOD
def div(a, b):
  return ( (a % MOD) * (power(b, MOD)) ) % MOD
def power(a, b):
  return pow(a, b, MOD)


n, k = map(int, input().split())
an = list(map(int, input().split()))
n1 = [0] * n
n2 = [0] * n
for i, v in enumerate(an):
  n1[i] = len([x for x in an[i+1:] if x < v])
  n2[i] = n1[i] + len([x for x in an[:i] if x < v])

cnt = 0
if k // 2 == 0:
  ks = mul(k-1, k//2)
else:
  ks = mul((k-1)//2, k)
for i in range(n):
  cnt = add(cnt, mul(n1[i], k))
  cnt = add(cnt, mul(n2[i], ks))
print(cnt)

Submission status: Wrong Answer

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

waru = 10 ** 9 + 7;

for i in range(n) :
	a[i] = int(a[i]);

kaisu = [0] * n;
usiro = [0] * n;

for i in range(n) :
	for j in range(n) :
		if a[i] > a[j] :
			kaisu[i] += 1;
			if i < j :
				usiro[i] += 1;

ans = 0;
for i in range(n) :
	ans += ((((((k-1)%waru) * (k%waru) )%waru) / 2) * (kaisu[i]%waru) + ((k%waru)*(usiro[i]%waru))%waru)%waru;
	
print(int(ans%waru));

Submission status: Wrong Answer

Solution code:

n,k=map(int,input().split())
a=list(map(int,input().split()))
ans=0

for i in range(len(a)):
    p=sum([1 for j in a[i:] if a[i]>j])
    q=sum([1 for j in a if a[i]>j])
   # print(p,q)
    s=int(p*k%(1000000000+7))
    t=int(q*(((k-1)*k)/2)%(1000000000+7))
    ans+=s+t


print(int(ans%(1000000000+7)))

Submission status: Wrong Answer

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

res=0
for i in range(n):
    for j in range(i+1,n):
        if a[i]>a[j]:
            res+=1
sum = k*(k+1)//2
print(res*sum%mod)

Submission status: Wrong Answer

Solution code:
import bisect
N,K = map(int,input().split())
A = list(map(int, input().split()))
B1=sorted(A)
LIM=10**9+7
max_=0
right_max=0
Q1=[0]*N
Q2=[0]*N
for i in range(0,N):
  B2=sorted(A[i:])
  Q1[i] = bisect.bisect_left(B1,A[i])
  Q2[i] = bisect.bisect_left(B2,A[i])
  
#print(Q1)
#print(Q2)
S1=sum(Q1)
S2=sum(Q2)
ans=int(S1*K*(K-1)/2)+S2*K
print(ans % LIM)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
if n == 1:
  print("0")
  exit()
ans_unit = 0
for i in range(n-1):
  for j in range(i+1, n):
    if a[i] > a[j]:
      ans_unit+=1
if k == 1:
  print(ans_unit)
  exit()
c = sum([a,a], [])
ans_two = 0
for i in range(2*n-1):
  for j in range(i+1, 2*n):
    if c[i] > c[j]:
      ans_two+=1
ans_inc = ans_two - 2*ans_unit
ans = k*ans_unit + int(k*(k-1)*ans_inc/2)
ans = ans%1000000007
print(ans)

Submission status: Wrong Answer

Solution code:



def main():
    n, k = map(int, input().split(" "))
    A = list(map(int, input().split(" ")))

    Anomitenti = 0
    ikotonaritenti = 0
    for index, i in enumerate(A):
        for j in A[index+1:]:
            if i > j:
                Anomitenti+= 1
        for j in A:
            if i > j:
                ikotonaritenti += 1

    kosuu = int((1 + (k-1)) * (k-1) / 2)
    result = Anomitenti * k + ikotonaritenti * kosuu
    print(result % 1000000007)

main()

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) % mod) * (K % mod) % mod) / 2
        # import pdb; pdb.set_trace()
    print(int(count) % mod)

if __name__ == '__main__':
    main()

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=s*K+(S*K*(K-1))/2
print(int(B)%1000000007)