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: Accepted

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

x=0
y=0
for i in range(len(a)):
    for j in range(i+1,len(a)):
        if a[i]>a[j]:
            x+=1
for i in range(len(a)):
    for j in range(0,i):
        if a[i]>a[j]:
            y+=1
ans=x*k*(k+1)//2+y*k*(k-1)//2
print(ans%(10**9+7))

Submission status: Accepted

Solution code:
from decimal import Decimal

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

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



a = 10**9+7

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

for i in range(0,N):
	for j in range (0,N):

		if A[i]>A[j]:
			Ans+=1

ans =Decimal((ans-Ans))*Decimal(K)+Decimal(Ans)*Decimal(K)*Decimal((K+1))/Decimal(2)


print(Decimal(ans) % Decimal(a))

Submission status: Accepted

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

count1 = 0
count2 = 0

#A1回での転倒数を求める
for i in range(N):
  for j in range(i+1, N):
    if A[i] > A[j]:
      count1 += 1 
      
#繰り返すことで生じる転倒数を求める
for i in range(2*N):
  for j in range(i+1, 2*N):
    if A2[i] > A2[j]:
      count2 += 1
      
count3 = count2 - count1 * 2

count = count3 * (K - 1) * K // 2 + count1 * K
print(count % mod)
#print(count1,count2,count3)

Submission status: Accepted

Solution code:
n,k = map(int, raw_input().split())
a = map(int, raw_input().split())
mod = 10 ** 9 + 7
ans = 0
for i in xrange(n):
  inv = lt = 0
  for j in xrange(i+1, n):
    if a[i] > a[j]:
      inv += 1
  ans += inv * k
  for j in xrange(n):
    if a[i] > a[j]:
      lt += 1
  ans += lt * k * (k-1) / 2
  ans %= mod
print ans

Submission status: Accepted

Solution code:
mod = int(1e9 + 7)

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

ans = 0
for i in range(N):
    cnt1 = len([x for x in A[i + 1:] if x < A[i]])
    mul1 = K * (K + 1) // 2 % mod
    cnt2 = len([x for x in A[:i] if x < A[i]])
    mul2 = (K - 1) * K // 2 % mod
    ans = (ans + cnt1 * mul1 % mod) % mod
    ans = (ans + cnt2 * mul2 % mod) % mod
print(ans)

Submission status: Accepted

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

countR=0
countA=0

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

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

print(int((countR * K + countA * K * (K-1) // 2)%(10**9+7)))

Submission status: Accepted

Solution code:
import collections


def duplicate(n):
    return n * (n - 1) // 2


def main():
    n, k = map(int, input().split())
    A = tuple(map(int, input().split()))
    
    a = 0;
    
    for i in range(n - 1):
        for j in range(i + 1, n):
            if A[i] > A[j]:
                a += 1
    
    a_counter = collections.Counter(A)
    
    b = duplicate(n)
    for key in a_counter:
        if a_counter[key] >= 2:
            b -= duplicate(a_counter[key])
    
    print((a * k + b * k * (k - 1) // 2) % ((10 ** 9) + 7))


main()

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int,input().split()))
MOD = 1000000007
count = 0
for i in range(N-1):
    for j in range(i+1, N):
        if A[i] > A[j]:
            count += 1
first = (count * K) % 1000000007

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

#ans = ((count * K) + (count2 * K * (K-1) // 2)) % MOD
second = (count2 * (K*(K-1)//2)%MOD) % MOD

print(int((first+second)%MOD))
#print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int,input().split()))
MOD = 1000000007
count = 0
for i in range(N-1):
    for j in range(i+1, N):
        if A[i] > A[j]:
            count += 1
first = (count * K) % 1000000007

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

ans = ((count * K) + (count2 * K * (K-1) // 2)) % MOD
#second = (count2 * (K*(K-1)/2)%MOD) % MOD

#print(int((first+second)%MOD))
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush, heapify
import math
import itertools
import random
 
# NO, PAY-PAY
#import numpy as np
#import statistics
#from statistics import mean, median,variance,stdev
 
INF = float('inf')
def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
 
def main():
    N,K = inputMap()
    A = inputList()
    
    ten = 0
    ten_zen = 0
    for i,vol in enumerate(A):
        for j,val in enumerate(A):
            if i >= j:
                if vol > val:
                    #print("{} {}".format(vol, val))
                    ten_zen += 1
                continue
            if vol > val:
                ten += 1
                ten_zen += 1
                
    #ans = (K*ten) + ((K-1)*ten_zen)
    #ans = ans%1000000007
    
    ans = (K*ten)%1000000007
    tmp = (K*(K-1)) // 2
    ans = ans + ((tmp * ten_zen)%1000000007)
    
    print(ans%1000000007)
    
    
if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
N,K = map(int, input().split())
As = [i for i in map(int, input().split())]
MOD = 10**9 + 7

count1 = 0
count2 = 0
for i,Ai in enumerate(As):
    for j,Aj in enumerate(As):
        if Ai > Aj:
            count2 += 1
        if i >= j:
            continue
        if Ai > Aj:
            count1 += 1
        
total = (count1*K + count2*K*(K-1)//2) % MOD
print(int(total % (10**9+7)))

Submission status: Accepted

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

# N = 2000
# K = 10 ** 9
# A = [i for i in range(2000)]

count1 = 0

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

count2 = 0

# 2回目以降のA
for i in range(N):
    for j in range(N):
        # print(i, j, A[i], A[j])
        if A[i] > A[j]:
            count2 += 1

# print(count)

ans = ((count1 * K) + (count2 * K * (K - 1) // 2)) % ((10 ** 9) + 7)

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

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

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

print((cntA*k+k*(k-1)*cntK//2)%(10**9+7))

Submission status: Accepted

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

whole = 0
right = 0

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

mod = 10 ** 9 + 7
ans = right * K
ans += whole * (K - 1) * K // 2

print(ans % mod)

Submission status: Accepted

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

whole = 0
right = 0
whole_list = []
right_list = []

for i in range(N):
    for j in range(N):
        if A[i] > A[j]:
            whole += 1
            if i < j:
                right += 1
    else:
        whole_list.append(whole)
        whole = 0
        right_list.append(right)
        right = 0

mod = 10 ** 9 + 7
ans = sum(right_list) * K
ans += sum(whole_list) * (K - 1) * K // 2

print(ans % mod)

Submission status: Accepted

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

for i in range(n):
    for j in range(n):
        if a[i] > a[j]:
            if i < j: p += 1
            q += 1

print((p*k + (q*k*(k-1) // 2)) % m)

Submission status: Accepted

Solution code:
from itertools import combinations

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

cnt_in_one = 0
cnt_in_two = 0

for ai, aj in combinations(a, 2):
    if ai > aj:
        cnt_in_one += 1
    if ai < aj:
        cnt_in_two += 1
       
mod = 10 ** 9 + 7
print((cnt_in_one * (k + k * (k - 1) // 2) + cnt_in_two * k * (k - 1) // 2) % mod)

Submission status: Accepted

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

XX=0
YY=0
for x in range(0,N-1):
    for y in range(x+1,N):
        if A[x]>A[y]:
            XX=XX+1
for x in range(0,N):
    for y in range(0,N):
        if A[x]>A[y]:
            YY=YY+1
S=XX*K+YY*(K**2-K)//2
S=S%(10**9+7)
print(S)

Submission status: Accepted

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

within = 0
between = 0
for n in range(N):
    for i in range(N):
        if A[n] > A[i]:
            between += 1
            if n < i:
                within += 1

ans = 0
mod = 10**9+7
ans += within*K
ans %= mod
ans += (between*K*(K-1))//2
ans %= mod

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

mod = 10**9+7
ans = 0

for i in range(N):
	bs = [1 if g < A[i] else 0 for g in A]
	ans += (K+1)*K*sum(bs)//2 - sum(bs[:i])*K
print(int(ans)%mod)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
l=list(map(int,input().split()))
MOD=10**9+7
ans=0
for num,i in enumerate(l):
    n1=sum([j<i for j in l])
    n2=sum([j<i for j in l[num:]])
    ans+=k*n2+k*(k-1)*n1//2
    ans%=MOD
print(ans)

Submission status: Accepted

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

X=[]
for i in range(N):
    cnt=0
    for j in range(i):
        if A[i]<A[j]:
            cnt+=1
    X.append(cnt)

Y=A
Y.sort()

ans=0
mod=10**9+7
for i in range(N):
    Z=bisect.bisect_left(Y,A[i])
    ans+=(K*(K-1)//2)*Z+X[i]*K
    ans%=mod
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-

MOD = 1000000007


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

Ans = 0
for i in range(N):
  an_all,an_right = 0,0
  for j in range(N):
    if An[i] > An[j]:
      an_all += 1
      if i < j:
        an_right += 1
  Ans = (Ans + K*(K-1)//2*an_all + K*an_right) % MOD
print(Ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, k = map(int,input().split())
 
a=list(map(int,input().split()))
 
mod = 1000000007
 
need = (k * (k + 1)) // 2
need2 = ((k - 1) * k) // 2
ans = 0
 
freq = []
before = []
for i in range(0, 3000):
	freq.append(0)
	before.append(0)
	
 
for i in range(0, n):
	for j in range(i + 1, n):
		if(a[i] > a[j]):
			freq[i] += 1
			
	j = i - 1
	while j >= 0:
		if(a[i] > a[j]):
			before[i] += 1
		j -= 1
		
	ans += (freq[i] * need)
	ans += (before[i] * need2)
	ans %= mod
 
#print(ans)
print(ans % mod)

Submission status: Accepted

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

p=0
p_=0
for i,j in enumerate(A):
  p+=len(list(filter(lambda x:x>j,A)))
  p_+=len(list(filter(lambda x:x<j,A[i:])))


ans=p_*K+p*K*(K-1)//2

print(ans%mod)

Submission status: Accepted

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

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

ain=0
aout=0

for i in range(n):
    for j in range(n):
        if l[i]>l[j]:
            aout+=1
            if i<j:
                ain+=1
ain*=k
aout*=k*(k-1)//2

print((ain+aout)%mod)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
from math import factorial, ceil, floor
from bisect import bisect_right as bsr
from operator import itemgetter as ig
from collections import defaultdict as dd
from collections import deque, Counter as cnt

# お約束
args = None
INF = float("inf")
MOD = int(1e9 + 7)
def input(*ps):
    if type(ps[0]) is list:
        return [input(*ps[0][:-1]) for _ in range(ps[0][-1])]
    elif len(ps) == 1:
        return ps[0](next(args))
    else:
        return [p(next(args)) for p in ps]
def nlist(n, v):
    if not n: return v.copy()
    return [nlist(n[1:], v) for _ in range(n[0])]

# バイナリインデックス木
class BIT:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
    def sum(self, i):
        s = 0
        while 0 < i:
            s += self.tree[i]
            s %= MOD
            i -= i & -i
        return s
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

# エントリーポイント
def main():
    N, K = input(int, int)
    A = input([int, N])

    MAX = 2010
    bit = BIT(MAX)
    # 最終周をカウントする
    sum1 = []
    for i, a in enumerate(A, start=1):
        bit.add(a, 1)
        sum1.append(i - bit.sum(a))
    # 繰り返し周をカウントする
    sum2 = []
    for a in A:
        sum2.append(N - bit.sum(a))
    # (1 + (K - 1))回分を集計する
    ans = 0
    for v1, v2 in zip(sum1, sum2):
        ans += K * v1 + ((K * (K - 1)) // 2) * v2
        ans %= MOD
    print(ans)

if __name__ == '__main__':
    args = iter(sys.stdin.read().split())
    main()

Submission status: Accepted

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

count = 0
for i in range(N):
    m = 0
    n = 0
    for j in range(N):
        if A[i] > A[j]:
            n += 1
            if i < j:
                m += 1
    count += K * m + n * K * (K - 1) // 2
print(count % (10 ** 9 + 7))

Submission status: Accepted

Solution code:

N, K = map(int,input().split())
A= list((map(int, input().split())))
an = (K*(K+1))//2
a = ((K-1)*K)//2
au =0
al = 0
for i in range(N):
  for j in range(N):
    au += 1 if A[i]<A[j] and i>j else 0
    al += 1 if A[i]<A[j] and i<j else 0
print((au*an+al*a)%(10**9+7))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
import numpy as np
N, K = map(int, input().split())
A = np.array(input().split(), dtype=np.int64)
MOD = 10**9 + 7

bl1 = A[:,None] > A[None,:]
bl2 = np.arange(N,dtype=np.int64)[:,None]
bl3 = np.arange(N,dtype=np.int64)[None,:]
mask = bl2[None] < bl3[None]
mask = bl1 & mask
ans1 = (mask*1).astype(np.int64).sum() % MOD
ans1 = ans1 * K % MOD

ans2 = (bl1 * 1).astype(np.int64).sum() % MOD
coe =int(K * (K - 1) // 2) % MOD
ans2 = ans2 * coe % MOD


print((ans1 + ans2) % MOD)

Submission status: Accepted

Solution code:
from collections import Counter


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())
aaa = list(map(int, input().split()))
MOD = 10**9 + 7
bit = Bit(2001)
single = 0
for a in reversed(aaa):
  single += bit.sum(a)
  bit.add(a + 1, 1)
ans = single * k % MOD
coef = k * (k - 1) // 2 % MOD
cnt = Counter(aaa)
before = 0
for a, c in sorted(cnt.items()):
  ans = (ans + c * before * coef) % MOD
  before += c
print(ans)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7


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


class BinaryIndexedTree:
    def __init__(self, tree_size):
        self.tree_size = tree_size
        self.tree = [0] * (self.tree_size + 1)

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

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


def count_inversion(A, max_num):
    bit = BinaryIndexedTree(max_num)
    x = 0
    for i, a in enumerate(A, start=1):
        bit.add(a, 1)
        x += i - bit.sum(a)
    return x


def main():
    N, K = MAP()
    A = MAP()

    tento_int = count_inversion(A, 2000)  # Aの内部で発生する転倒数
    tento_ext = count_inversion(sorted(A, reverse=True), 2000)  # AiとAjの間で発生する転倒数

    x = tento_int * K
    y = tento_ext * K * (K - 1) // 2
    print((x + y) % MOD)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools
# import numpy as np
 
DIV_NUM = 1000000000 + 7
 
INPUT_NUMS = list(map(int, input().split()))
N=int(INPUT_NUMS[0])
K=int(INPUT_NUMS[1])
 
A = [int(x) for x in input().split()]
#AA = np.array(A , dtype='int64')

if N==1:
    print(0)
    exit()


nn=int(math.log2(2000))+1
tree = [0] * (2**nn)

def BIT_update(tree,x):
    while x <= 2000:
        tree[x] += 1
        y = x
        z = 1
        while y > 0:
            if y % 2 == 1:
                x += z
                break
            y //= 2
            z *= 2

def BIT_sum(tree,x):
    s = 0
    while x > 0:
        s += tree[x]
        y = x
        z = 1
        while y > 0:
            if y % 2 == 1:
                x -= z
                break
            y //= 2
            z *= 2
    return s
 
answer = N*(N-1)//2
for i in A:
    answer -= BIT_sum(tree,i)
    BIT_update(tree,i)

B = sorted(A)
 
q=0
p=B[0]
r=0
for i in range(1,N):
    if B[i]>p:
        p=B[i]
        r=i
    q += r
 
answer = answer * K + q * K * (K-1) // 2
answer = answer % DIV_NUM
print(answer)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()*2))
base1 = 0
base2 = 0
for i in range(N):
  count1=0
  count2=0
  for j in range(i+1,i+N+1):
    if A[i] > A[j]:
      if j < N:
        count1+=1
      else:
        count2+=1
  base1+=count1
  base2+=count2

ans = (base1*K*(K+1) + base2*K*(K-1))//2
div = 10**9 + 7
print(ans%div)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import Counter


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())
aaa = list(map(int, input().split()))
MOD = 10 ** 9 + 7
bit = Bit(2001)
single = 0
for a in reversed(aaa):
    single += bit.sum(a)
    bit.add(a + 1, 1)
ans = single * k % MOD
coef = k * (k - 1) // 2 % MOD
cnt = Counter(aaa)
before = 0
for a, c in sorted(cnt.items()):
    ans = (ans + c * before * coef) % MOD
    before += c
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    mod = 10 ** 9 + 7
    ans = 0

    # See:
    # https://www.youtube.com/watch?v=JTH27weC38k
    # https://atcoder.jp/contests/jsc2019-qual/submissions/7107452

    # Key Insight
    # 2つの整数の順序対(i, j)の選び方
    # 同じブロックにある/異なるブロックにある で場合分け

    # 同じブロックにある
    # Bi > Bjとなる組み合わせを全探索
    for i in range(n - 1):
        count = 0

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

        # 一つのブロックにある組み合わせのk倍
        ans += count * k
        ans %= mod

    # 別のブロックにある
    for i in range(n):
        count = 0

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

        # k個のブロックから2個選ぶ（kC2）
        ans += count * (k * (k - 1) // 2)
        ans %= mod

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
mod=1000000007
a=list(map(int,input().split()))
zenbu=sorted(a)
aa=[]
ans=0
for i in range(n):
  kouhan=a[i:]
  kouhan.sort()
  b1=int(zenbu.index(a[i]))
  b2=int(kouhan.index(a[i]))
  #print(b1,b2)
  #print((k*(k-1)*b1/2)+k*b2)
  ans=ans+k*(k-1)*b1//2+k*b2
  ans=int(ans)%mod
print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
A = list(map(int, input().split()))
count=0
for i in range(n):
    for j in range(i+1,n):
        if A[i]>A[j]:
            count += (k*(k+1)//2)
    for l in range(i):
        if A[i]>A[l]:
            count += ((k-1)*(k)//2)

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

Submission status: Accepted

Solution code:
[N, K] = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]*2

base1 = 0
base2 = 0

for i in range(N):
    count1 = 0
    count2 = 0
    for j in range(i+1, i+1+N):
        if B[i] > B[j]:
            if j < N:
                count1 += 1
            else:
                count2 += 1
        
    base1 += count1
    base2 += count2
    
ans = (base1*K*(K+1)+base2*(K-1)*K)//2
    
divisor = 1000000007

print(ans % divisor)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
A=[int(i) for i in input().split()]
mod=10**9+7
import math
import bisect

n_max=2000
nn=int(math.log2(n_max))+1
BIT=[0]*(2**nn)
BIT.insert(0,0)

def bitsum(BIT,i):
  s=0
  while i>0:
    s+=BIT[i]
    i-=i&(-i)
  return s

def bitadd(BIT,i,x):
  while i<=n_max:
    BIT[i]+=x
    i+=i&(-i)
  return BIT

ans1=0
for i in range(n):
  ans1+=i-bitsum(BIT,A[i])
  bitadd(BIT,A[i],1)

ans2=0
A.sort()
for i in range(n-1):
  ans2+=n-bisect.bisect_right(A,A[i])

ans=(ans1*k)%mod
ans=(ans+ans2*k*(k-1)//2)%mod
print(ans)

Submission status: Accepted

Solution code:
# N = int(input())
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 - 1):
        for j in range(i + 1,N):
                if A[i] > A[j]:
                        ans += 1
ans1 = K * (K + 1) * time_ans // 2 - (time_ans - ans) * K
print(ans1 % (10 ** 9 + 7))

Submission status: Accepted

Solution code:
from bisect import bisect_left as lower_bound, bisect_right as upper_bound

mod = 10**9 + 7

def inversion_count(arr, n, k):
	b = []
	cnt = 0
	for i in range(n-1, -1, -1):
		pos = lower_bound(b, arr[i])
		cnt = (cnt + pos)%mod
		b.insert(pos, arr[i])
	
	cnt = (cnt*k)%mod	
	
	for i in range(n):
		pos = lower_bound(b, arr[i])

		cnt = (cnt + ((k*(k-1))//2)*pos)%mod

	
	return cnt



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

	arr = list(map(int, input().strip().split()))

	print (inversion_count(arr, n, k))

if __name__ == "__main__":
	main()

Submission status: Accepted

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

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

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

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

bit = Bit(2000)

intra, inter = 0, 0
for i, a in enumerate(map(int, input().split())):
    bit.add(a, 1)
    intra += i + 1 - bit.sum(a)
    inter += bit.sum(a - 1)

mod = 10**9 + 7
ans = (intra * K * (K + 1) // 2) % mod
ans += (inter * (K - 1) * K // 2) % mod
print(ans % mod)

Submission status: Accepted

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

tentosu_f = 0
tentosu_l = 0
mod = 10**9 + 7
ans = 0

for i in range(n):
    for j in range(i, n):
        if A[i] > A[j]:
            tentosu_f += 1
          
for i in range(n):
    for j in range(n):
        if A[i] > A[j]:
            tentosu_l += 1
            
ans = (tentosu_f * k) + ((k * (k-1) // 2) * tentosu_l)
print(int(ans % mod))

Submission status: Accepted

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

ten_f = 0
ten_l = 0

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

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

ans = (ten_f * (K)) + ((K * ((K - 1)) // 2) * ten_l)
print(ans % mod)

Submission status: Accepted

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

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

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

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

bit = Bit(2000)

intra, inter = 0, 0
for i, a in enumerate(A):
    bit.add(a, 1)
    intra += i + 1 - bit.sum(a)
    inter += bit.sum(a - 1)

mod = 10**9 + 7
ans = (intra * K * (K + 1) // 2) % mod
ans += (inter * (K - 1) * K // 2) % mod
print(ans % mod)

Submission status: Accepted

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

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

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

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

# inter = 0
# for i in range(N):
#     ai = A[i]
#     for j in range(i + 1):
#         aj = A[j]
#         if ai > aj:
#             inter += 1

bit = Bit(2000)

intra = 0
inter = 0
for i in range(len(A)):
    a = A[i]
    bit.add(a, 1)
    intra += i + 1 - bit.sum(a)
    if a != 1:
        inter += bit.sum(a - 1)

# for i in range(len(A)):
#     a = A[i]
#     if a != 1:
#         inter += bit.sum(a - 1)

# print(inter, intra)

mod = 10**9 + 7

ans = (intra * K * (K + 1) // 2) % mod
ans += (inter * (K - 1) * K // 2) % mod
print(ans % mod)

Submission status: Accepted

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

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

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

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

inter = 0
for i in range(N):
    ai = A[i]
    for j in range(i + 1):
        aj = A[j]
        if ai > aj:
            inter += 1

bit = Bit(2000)

intra = 0
for i in range(len(A)):
    a = A[i]
    bit.add(a, 1)
    intra += i + 1 - bit.sum(a)

# print(inter, intra)

mod = 10**9 + 7

ans = (intra * K * (K + 1) // 2) % mod
ans += (inter * (K - 1) * K // 2) % mod
print(ans % mod)

Submission status: Accepted

Solution code:
N, K = map(int,input().split())
An = list(map(int,input().split()))
f_count = 0
r_count = 0

for i in range(N):
    for j in range(N):
        if i < j:
            if An[i] < An[j]:
                f_count += 1
            elif An[i] > An[j]:
                r_count += 1

Ans = (f_count * K*(K-1)//2 + r_count * (K*(K+1)//2)) % (10**9+7)

print(int(Ans))

Submission status: Accepted

Solution code:
import collections

N,K = map(int, input().split())
arr = list(map(int, input().split()))
c = collections.Counter(arr)

counts = list(c.values())[::-1]

if len(counts)==1:
  print(0)
else:
  value = 0
  for num in arr:
    value += len([1 for x in arr if x<num])
  out_arr = value*K*(K-1)//2
  
  in_arr = 0
  for j,num in enumerate(arr):
    in_arr += len([1 for x in arr[j+1:] if x<num])
  in_arr = in_arr*K
  print((out_arr+in_arr)%1000000007)

Submission status: Accepted

Solution code:
N,K = map(int, input().split())
A = list(map(int, input().split()))
Ans = 0
 
count1 = (K * (K+1) // 2) % 1000000007
count2 = ((K-1) * K // 2) % 1000000007

#print(count1)
#print(count2)
 
for i in range(N):
 
  for j in range(N):
 
    if A[i] > A[j]:
      if i < j:
        Ans = Ans + count1
      else:
        Ans = Ans + count2
      
      if Ans > 1000000007:
        Ans = Ans % 1000000007  
 
 
print(int(Ans))

Submission status: Accepted

Solution code:
n,k = list(map(int,input().split()))
num_list = list(map(int,input().split()))
next_list = []
mod = ((10**9)+7)
up = 0
exup = 0
ans = 0
for i in range(n):
    for j in num_list:
        if num_list[0] > j:
            up+=1
    next_list.append(num_list.pop(0))
for i in range(n):
    for j in next_list:
        if next_list[-1] > j:
            exup+=1
    del next_list[-1]
ans = up*k*(k+1)//2 + exup*(k-1)*k//2

print(int(ans%mod))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N, K = map(int, input().split())
A = list(map(int, input().split()))
INF = 10 ** 9 + 7

inner = 0
outer = 0
cnt = 0
ans = 0

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

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

ans = (inner * K + ((K * (K - 1)) // 2) * outer) % INF
print(ans)