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:
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
ks = (k-1) * k // 2
for i in range(n):
  cnt = add(cnt, mul(n1[i], k))
  cnt = add(cnt, mul(n2[i], ks))
print(cnt)

Submission status: Accepted

Solution code:
import sys

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    MOD = 10**9 + 7

    para = []
    for i, s in enumerate(A):
        a = 0
        d = 0
        for j, t in enumerate(A):
            if s > t:
                d += 1
                if i < j:
                    a += 1
        para.append((a, d))

    ans = 0
    if K == 1:
        for a, _ in para:
            ans = (ans + a) % MOD
    else:
        for a, d in para:
            s = K * (2*a + (K-1)*d) // 2
            ans = (ans + s) % MOD

    return ans


if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
def main():
    MOD=10**9+7
    N,K=map(int, input().split())
    A=list(map(int, input().split()))
    A2=A*2
    C1=0
    C2=0
    for i in range(N*2):
        for j in range(i+1,N*2):
            if A2[i] > A2[j]:
                if j < N:
                    C1+=1
                elif i < N and N <= j:
                    C2+=1
    ans = (C1*K%MOD + C2*(K * (K-1) // 2)%MOD)%MOD
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10**9+7
nums = A[:]
nums_sorted = sorted(nums)
rank = {}
count = 0
for n in nums_sorted:
    if not n in rank:
        rank[n] = count
        count += 1
    else:
        count += 1
#print(rank)

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

#print(rev)
ans = 0
n = K
for a, d in zip(rev, nums):
    ans += n*(2*a + (n-1)*rank[d])//2 % MOD
print(ans% MOD)

Submission status: Accepted

Solution code:
import bisect

class BinaryIndexedTree:
    # http://hos.ac/slides/20140319_bit.pdf
    def __init__(self, size):
        self._bit = [0 for _ in range(size)]
        self._size = size
 
    def add(self, i, w):
        x = i + 1
        while x <= self._size:
            self._bit[x - 1] += w
            x += x & -x
 
    def sum(self, i):
        ret = 0
        x = i + 1
        while x > 0:
            ret += self._bit[x - 1]
            x -= x & -x
        return ret
 
    def __len__(self):
        return self._size
 
 
def count_inversions(li, max=None):
    if not max:
        max = __builtins__.max(li)
    bit = BinaryIndexedTree(size=max + 1)
    ret = 0
    for i in range(len(li)):
        ret += i - bit.sum(li[i])
        bit.add(li[i], 1)
    return ret

  
n,k = map(int, input().split())
a = list(map(int, input().split()))
sorted_a = sorted(a)
d = 0
tree = [0] * (n+1) 
mod = 10 ** 9 + 7
ans = (count_inversions(a, max=max(a)) * k) % mod

for i in a:
  d += bisect.bisect_left(sorted_a, i)

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import defaultdict
from heapq import heappush, heappop
import math
import bisect
import random

def LI(): return list(map(int, input().split()))
def I(): return int(input())
def LIM(): return list(map(lambda x:int(x) - 1, input().split()))
def LS(): return input().split()
def S(): return input()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def LIRM(n): return [LIM() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
mod = 1000000007


n, k = LI()
a_list = LI()


rev_tuple = []
for i in range(len(a_list)):
    num = a_list[i]
    a = len([j for j in a_list[i:] if j < num]) % mod
    b = len([j for j in a_list if j < num]) % mod
    rev_tuple += [(a, b)]



ans = 0

for a, b in rev_tuple:
    ans += b * k * (k - 1) // 2 % mod
    ans %= mod
    ans += a * k % mod
    ans %= mod





print(ans % mod)

Submission status: Accepted

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

mod = 10**9 + 7
B = [0]*N
for i in range(N):
    ai = A[i]
    for j in range(i, N):
        aj = A[j]
        if ai > aj:
            B[i] += 1

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

# print(B)
# print(C)
ans = 0
# for i in range(N):
#     ai = A[i]
#     for j in range(i + 1, N):
#         aj = A[j]
#         # print(i, j, ai, aj)
#         if ai > aj:
#             ans += 1

for i in range(N):
    ans += B[i]*K*(K+1)//2
    ans %= mod

for i in range(N):
    ans += C[i]*(K-1)*K//2
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7
n, k = [ int(v) for v in input().split() ]

num_list = [ int(v) for v in input().split() ]
num_list_2 = [ i - 1 for i in num_list ]
t_list = []
ts_list = []
for i, v in enumerate(num_list):
    t = 0
    s = 0
    for j in range(i):
        if num_list[j] < v:
            s += 1
    for j in range(i+1,n):
        if num_list[j] < v:
            t += 1
    t_list.append(t)
    ts_list.append(t+s)


a = ( k * (k-1) )  // 2
a = a % mod

print( (sum(ts_list)*a+ k*sum(t_list) ) % mod )

Submission status: Accepted

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

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

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

s = sorted(a)
groups = ((k-1)*k/2)%mod
inv2 = 0
same = 0
for i in xrange(n):
	if i > 0 and s[i] == s[i-1]:
		same += 1
		inv2 += i-same
	else:
		same = 0
		inv2 += i
print (k*inv1+groups*inv2)%mod

Submission status: Accepted

Solution code:
mod = 1000000007
def f(i):
    return i * (i + 1) // 2
def solve():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))
    now = other = 0
    for i in range(n):
        for j in range(n):
            if i < j:
                if A[i] > A[j]:
                    now += 1
            else:
                if A[i] > A[j]:
                    other += 1
    print((now * f(k) + other * f(k - 1)) % mod)
solve()

Submission status: Accepted

Solution code:
mod = 10**9+7

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

leftK = (K * (K+1))//2
leftK %= mod
rightK = ((K-1) * K)//2
rightK %= mod

ans = 0
for i in range(N):
    a = A[i]
    l = sum(map(lambda x:x>a,A[:i]))
    r = sum(map(lambda x:x>a,A[i:]))
    ans += l * leftK
    ans += r * rightK

print(ans % mod)

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(n-1):
  for j in range(i+1,n):
    if a[i]>a[j]:
      x+=1
for l in range(n):
  for m in range(n):
    if a[l]>a[m]:
      y+=1
ans=((k*(k-1)*y)//2)%(1000000007)+(k*x)%1000000007
print(ans%1000000007)

Submission status: Accepted

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

A_fall = []
for i in range(N):
  ai = A[i]
  fall_point1 = 0
  if i != N-1:
    for j in range(i+1, N):
      aj = A[j]
      if ai > aj:
        fall_point1 += 1
  fall_point2 = 0
  for n in range(N):
    an = A[n]
    if ai > an:
      fall_point2 += 1
  A_fall.append([fall_point1, fall_point2])

ans = 0
for i in range(N):
  x, y = A_fall[i]
  fall_point = (x*K + y*(K-1)*K//2) % 1000000007
  ans += fall_point

print(ans % 1000000007)

Submission status: Accepted

Solution code:
from itertools import combinations
MOD = 10**9 + 7

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

pos, neg = (0, 0)
for a1, a2 in combinations(A, 2):
    if a1 < a2:
        pos += 1
    elif a1 > a2:
        neg += 1
ans = (K * max(0, K-1) // 2 * pos) % MOD + (K * neg) % MOD + (K * (K-1) // 2 * neg) % MOD
print(ans % MOD)

Submission status: Accepted

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

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

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

ans = 0
for i in range(N):
    ans += K*t1[i] + (K*K - K + 1) // 2 * t2[i]
    ans %= (10**9+7)
print(ans)

Submission status: Accepted

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

a = 0
b = 0

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

for i in range(n):
  for j in range(i+1, n):
    if l[i] > l[j]:
      a += 1
      b += 1
    elif l[i] < l[j]:
      b += 1

aa = (k + 1) * k//2 - k

m = 10 ** 9 + 7
print((a * k + b * aa) % m)

Submission status: Accepted

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

Submission status: Accepted

Solution code:

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

A=list(map(int,input().split()))
B=[]
for i in range(2):
    for j in range(N):
        B.append(A[j])
b=len(B)


a=len(A)
counter=0
for i in range(a):
    for j in range(a-i):
        if B[i]>B[i+j]:
            counter+=1


count=0
for i in range(b//2):
    for j in range(b//2):
        if B[i]>B[b//2+j]:
            count+=1
#print(count)
#print(count)
#print(counter)
#print(count-2*counter)

#print(counter)
#print(count)
#ans=(counter*K+((count-2*counter)*(K-1)*K)//2)%(1000000007)
answer=(counter*K+(count*(K-1)*K)//2)%(1000000007)
#print(ans)
print(answer)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
t = 0
l = 0
for i in range(n):
    for j in range(n):
        if a[i] > a[j]:
            l += 1
        if j > i and a[i] > a[j]:
            t += 1

mod = 10**9 + 7
ans = (t * k) % mod + (l * k * (k - 1)) // 2 % mod 
print(ans % mod)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
alist=[int(i) for i in input().split()]
blist=alist+alist
counta=0
countb=0
for i in range(n):
	for j in range(i+1,n):
		if alist[i] > alist[j]:
			counta+=1
for i in range(n):
	for j in range(n,n*2):
		if blist[i] > blist[j]:
			countb+=1
print((counta*k+(k*(k-1)//2)*countb)%(10**9+7))

Submission status: Accepted

Solution code:
mod = 10**9 + 7
N, K = map(int, input().split())
A = list(map(int, input().split()))
ans = 0
for i in range(N):
    for j in range(i+1, N):
        if A[i] > A[j]:
            ans += 1
ans2 = 0
for i in range(N):
    for j in range(N):
        if A[i] > A[j]:
            ans2 += 1

d = ans2
l = ans + ans2 * (K-1)
print(((2*ans + (K-1)*d)*K//2)%mod)

Submission status: Accepted

Solution code:
import bisect
MOD = 10**9+7
N,K = map(int,input().split())
A = list(map(int,input().split()))
# N,K = 2000,10*9
# A = [1 for i in range(2000)]
SA = sorted(map(lambda x:-x, A))
befores = []
r_be = []
r_all = []
for i,a in enumerate(A):
  rbb = bisect.bisect_left(befores,-a)
  r_be.append(rbb)
  raa = bisect.bisect_left(SA,-a)
  r_all.append(raa)
  befores.insert(rbb,-a)
  # print(a,rbb,raa,befores)

sm_be = sum(r_be)
sm_al = sum(r_all)

r = ((sm_be*K)%MOD + ((((K*(K-1))//2)%MOD)*sm_al)%MOD)%MOD
print(r)
# print()
# print(A)
# print(r_be)
# print(r_all)

Submission status: Accepted

Solution code:
# A, B = [int(i) for i in input().split(" ")]
# A = int(input())

N, K = [int(i) for i in input().split(" ")]
As = [int(i) for i in input().split(" ")]
MOD = 10 ** 9 + 7
ans = 0

count1 = [0] * N
for i in range(N):
    count1[i] = sum(As[i] > As[j] for j in range(N))

count2 = [0] * N
for i in range(N):
    count2[i] = sum(As[i] > As[j] for j in range(i + 1, N))

# print(ans, total2, total2 * (K-1))
for i in range(N):
    a = ((2*count2[i] + (K-1)*count1[i]) * K) // 2
    ans = (ans + a) % MOD
print(ans)

Submission status: Accepted

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

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

#print(tmp )

tmp%= inf
ans = (K+1)*K//2 % inf
ans = ans * tmp  
ans %= inf

#print(ans)
x = len(list(set(A)))
#print(x)

a = tmp * K % inf
b = (x*(x-1)//2) % inf
c = (K*(K-1)//2) % inf
d = a + b * c
e = d% inf
#print(e)

#print(A * K)

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

a = tmp * K % inf
b = w % inf
c = (K*(K-1)//2) % inf
d = a + b * c
e = d% inf
print(e)

Submission status: Accepted

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

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

ans = 0
ans2 = 0
for i in range(n):
    for j in range(n):
        if a[i] > a[j]:
            if i < j:    
                ans += 1
            elif i > j:
                ans2 += 1
count1 = k*(k+1)//2
count2 = (k-1)*k//2

ans = ans * count1 + ans2 * count2

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

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

mod = 1000000007
n, k = na()
li = na()
ct1 = 0
ct2 = 0
for i in range(n):
    for j in range(n):
        if li[i] > li[j]:
            if i < j:
                ct1 += 1
            else:
                ct2 += 1

al = ct1 + ct2
an = ((k * (k-1))//2) % mod
print((ct1 * k + al * an) % mod)

Submission status: Accepted

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

Submission status: Accepted

Solution code:

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

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

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

print(((left * K*(K+1) // 2) + (right * K*(K-1)//2)) % (1000000007))

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
cnt = [0 for i in range(N)]
for i in range(N):
    for j in range(i + 1, N):
        if A[i] > A[j]:
            cnt[i] += 1

if K == 1:
    print(sum(cnt))
else:
    total = sum(cnt) * K
    cnt2 = [0 for i in range(N)]
    for i in range(N):
        for j in range(N):
            if A[i] > A[j]:
                cnt2[i] += 1
    for i in range(N):
        total = (total + cnt2[i] * K * (K - 1) // 2) % (10 ** 9 + 7)
    print(total)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n,k = na()
A = na()
mod = 10**9+7

def bSort(a):
    c = 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]
                c += 1

    return c

cc = bSort(A)
B = sorted(A)
g = 0
p = 0
for i in range(1,n):
    if B[i-1] != B[i]:
        p = i
    g += p

j = k*(k-1)//2

ans = cc*k%mod+g*j%mod

print(ans%mod)

Submission status: Accepted

Solution code:
def main():
    nk = [int(x) for x in input().split()]
    a = [int(x) for x in input().split()]
    tenchi_short = []
    for i in range(len(a)):
        tenchi_short.append([0, 0])
        for j in range(len(a)):
            if a[i] > a[j]:
                if i < j:
                    tenchi_short[i][0] += 1
                else:
                    tenchi_short[i][1] += 1
    sum = [(1 + nk[1]) * nk[1] // 2, (nk[1] - 1) * nk[1] // 2]
    ret = 0
    dividor = int(pow(10, 9) + 7)
    for i in range(len(a)):
        # tmp = 0
        # if nk[1] % 2 == 1:
        #     tmp += ()
        ret += (sum[0] * tenchi_short[i][0] + sum[1] * tenchi_short[i][1]) % dividor
        ret %= dividor
    print(int(ret))
    return


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
if n==1:
  print(0)
  exit()
if k==1:
  tentou=0
  for i in range(n-1):
    for j in range(i+1,n):
      if a[i]>a[j]:
        tentou+=1
  print(tentou)
  exit()

t=[0 for _ in range(n)]
tentou=0
for i in range(n-1):
  for j in range(i+1,n):
    if a[i]>a[j]:
      tentou+=1
      t[i]+=1
    if a[j]>a[i]:
      t[j]+=1
coef=((k-1)*k//2)%1000000007
ti=sum(t)*coef%1000000007
te=tentou*k%1000000007
print((ti+te)%1000000007)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
v1 = 0
for i in range(n - 1):
  for j in range(i + 1, n):
    if a[i] > a[j]:
      v1 += 1
v2 = 0      
for i in range(n):
  for j in range(n):
    if a[i] > a[j]:
      v2 += 1

t = v1 * k + v2 * k * (k - 1) // 2
print(t % (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()]
b=0
for i in range(n):
  for j in range(i):
    if a[j]>a[i]:
      b+=1
c=0
for i in range(n):
  for j in range(n):
    if a[j]>a[i]:
      c+=1
k=b*k+c*k*(k-1)//2
print(k%(10**9+7))

Submission status: Accepted

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

MOD = 1000000007
ans = 0
for i in range(N):
    cnt = 0
    pcnt = 0
    for j in range(N):
        if A[i] > A[j]:
            if i < j:
                cnt += 1
            else:
                pcnt += 1
    ans += cnt*(K)*(K+1) // 2
    # ans += pcnt*(K)
    # ans += pcnt*(K-1)
    ans += pcnt*(K-1)*(K) // 2

print(ans%MOD)

Submission status: Accepted

Solution code:
import sys


def main():
    n, k = [int(s) for s in sys.stdin.readline().strip().split()]
    a = [int(s) for s in sys.stdin.readline().strip().split()]

    seen_nums = []
    s = 0
    for i in range(n):
        for seen in seen_nums:
            if seen > a[i]:
                s += 1
        seen_nums.append(a[i])

    t = 0
    for i in range(n):
        for seen in seen_nums:
            if a[i] < seen:
                t += 1

    ans = (k * (k-1) * t // 2 + k * s) % (10 ** 9 + 7)
    print(ans)


main()

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right

N,K = [int(zz) for zz in input().split()]
A = [int(zz) for zz in input().split()]

B = sorted(A)

C = []
for i in range(N):
    p = bisect_left(B,A[i])
    C.append(p)

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

ans = q*K+sum(C)*((K*(K-1))//2)
print(ans%(10**9+7))

Submission status: Accepted

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

mod = 10**9+7

ans = 0

s = 0
count = [0 for _ in range(2000)]
for a in aa :
    s += sum(count[a:])
    count[a-1] += 1
ans = s*k%mod

s = 0
for i in range(2000) :
    s += count[i]*sum(count[i+1:])
ans = (ans+s*k*(k-1)//2)%mod

print(ans)

Submission status: Accepted

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

AA = A[:] + A[:]
mod = 10**9 + 7

def bubble_sort(L: list) -> int:
    A = L[:]
    count = 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]
                count += 1
    return count


ans1 = bubble_sort(A)
ans2 = bubble_sort(AA) - 2 * ans1
ans = (K * ans1 + (K * (K - 1) // 2) * ans2) % mod

print(ans)

Submission status: Accepted

Solution code:
import collections
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
if __name__ == "__main__":
    N,K = map(int,input().split())
    Len = N
    A = list(map(int,input().split()))
    num = 10 ** 9 + 7
    ti = (K * (K -1) // 2)%num
    count = 0
    cnt = bubble_sort(A)
    count = (count +cnt*K) % num
    C = collections.Counter(A)
    c = sorted(C.items(),key=lambda x:x[1],reverse = True)
    for a in c:
        b = a[1]
        Len -= b
        for i in range(b):
            count = (count + Len * ti) % num
    print(int(count))

Submission status: Accepted

Solution code:

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

mod = 10**9+7
ans = 0

for i in range(N):
    tmp = 0
    for aj in A[i+1:]:
        if A[i]>aj: tmp += 1
        
    ans += tmp*K*(K+1)//2
    ans %= mod
            
for i in reversed(range(N)):
    tmp = 0
    for aj in reversed(A[:i]):
        if A[i]>aj: tmp += 1
    ans += tmp*(K-1)*(K)//2
    ans %= mod
    
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
n,k=map(int, input().split())
a=list(map(int, input().split()))
b=Counter(a)
count=0
now=0
for i in sorted(b):
    count+=now*b[i]
    now+=b[i]
count*=(k-1)*k//2
c=[]
count2=0
import bisect
for i in a[::-1]:
    count2+=bisect.bisect_left(c,i)
    bisect.insort(c, i)
count2*=k
print((count+count2)%(10**9+7))

Submission status: Accepted

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

ans = 0
for i in range(N):
    l = len([a for a in A[0:i] if a < A[i]])
    r = len([a for a in A[i + 1:N] if a < A[i]])
    ans += (K - 1) * K * (l + r) // 2 + K * r
    ans %= MOD
print(ans)

Submission status: Accepted

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

MOD = 1000000007

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

result = 0
for i in range(N):
  result += count1[i] * K
  result %= MOD
  result += K * (K - 1) // 2 * count[i]
  result %= MOD

print(result)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(200000)
input = sys.stdin.readline

N, K = map(int, input().split())
L = [int(v) for v in input().split()]

m = [None] * N

c = 0
for i in range(N):
    a = 0
    b = 0
    for j in range(N):
        if i != j:
            if i < j and L[i] > L[j]:
                a += 1

            if i > j and L[i] > L[j]:
                b += 1

    m[i] = (a, b)

aa = 0
bb = 0
for a, b in m:
    aa += a * K
    bb += b * (K - 1)

cc = 0
for a, _ in m:
    cc += a

print((aa + bb + cc) * K // 2 % (10 ** 9 + 7))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

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


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)


@mt
def slv(N, K, A):
    ans = 0
    A_ = sorted(A)

    mod = Mod(10**9+7)
    c = mod.div(mod.sub(mod.mul(K, K), K), 2)
    
    for i, a in enumerate(A):
        j = bisect.bisect_left(A_, a) 
        t = 0
        for d in A[i:]:
            if d < a:
                t += 1
        ans = mod.add(ans, mod.mul(c, j))
        ans = mod.add(ans, mod.mul(K, t))
    return ans


def main():
    N, K = read_int_n()
    A = read_int_n()
    print(slv(N, K, A))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

L = [0]*N

for i in range(N) :
    a = A[i]
    for j in range(N) :
        b = A[j]
        if a > b :
            if i > j :
                L[i] += ((K-1)*K)//2
                L[i] %= 10**9+7
            else :
                L[i] += ((K+1)*K)//2
                L[i] %= 10**9+7
ans = sum(L)%(10**9+7)
print(ans)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7

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

right = [0 for _ in range(N + 1)]
left = [0 for _ in range(N + 1)]

for i, a in enumerate(A):
    for j, b in enumerate(A):
        if i < j and a > b:
            right[i] += 1
        elif i > j and a > b:
            left[i] += 1

res = 0

for i, (r, l) in enumerate(zip(right, left)):
    res = (res + K * (K + 1) // 2 * r) % MOD
    res = (res + (K - 1) * K // 2 * l) % MOD

print(res)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = [int(i) for i in input().split()]
ans = 0
left = 0
right = 0
rr = k*(k+1)//2
ll = k*(k-1)//2
mod = 10**9+7

for i in range(n):
    for j in range(0,i):
        if a[j] < a[i]:
            left += 1
    for _ in range(i+1,n):
        if a[_] < a[i]:
            right += 1
print(int((left * ll + right * rr)%mod))

Submission status: Accepted

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

count = [[0]*2 for i in range(N)]

for i in range(N-1):
    for j in range(i+1,N):
        if i == j:
            continue
        elif A[i] < A[j]:
            count[j][0] += 1
        elif A[j] < A[i]:
            count[i][1] += 1

ans = 0
for i in range(N):
    ans += count[i][0]*(K-1)*(K)//2
    ans % 1000000007
for i in range(N):
    ans += count[i][1]*K*(K+1)//2
    ans % 1000000007
print(ans%1000000007)

Submission status: Accepted

Solution code:
import numpy as np

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

a_2 = a.copy()
a_2.extend(a)

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

lst_2 = [0 for i in range(n)]
for i in range(n):
    for j in range(i+1, 2*n):
        if a[i] > a_2[j]:
            lst_2[i] += 1

arr1 = np.array(lst_1)
arr2 = np.array(lst_2)
arr2 = arr2 - arr1
sum1 = sum(arr1)
sum2 = sum(arr2)
ans = ((sum1*k) % (10**9+7) + (sum2 * (((k-1) * k // 2) % (10**9+7)))) % (10**9+7)

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):
        if a[j]>a[i]:
            count+=(k*(k+1))//2
    for j in range(i+1,n):
        if a[j]>a[i] :
            count+=((k-1)*k)//2
print(count%(10**9+7))

Submission status: Accepted

Solution code:
N, K = map(int,input().split())
A = list(map(int,input().split()))
B = [0]*N
C = [0]*N

for k in range(N):
    for l in range(k+1,N):
        if A[k] > A[l]:
            B[k] += 1
    for m in range(k):
        if A[k] > A[m]:
            C[k] +=1

ans = 0
MOD = 10**9 + 7

for e in B:
    ans += e*(K*(K+1)//2)
    ans %= MOD

for e in C:
    ans += e*(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
key = k
for i in range(n):
    for j in range(n):
        if a[i] > a[j] and i != j:
            if i < j:
                ans += (1 + key) * key // 2 % (10 ** 9 + 7)
            else:
                ans += (1 + key - 1) * (key - 1) // 2 % (10 ** 9 + 7)
        # print(ans, i, j)
ans %= ( 10 ** 9 + 7)
print(ans)