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_lst = list(map(int, input().split()))
mod = 10**9 + 7

count1 = 0
count2 = 0
for i in range(N):
    for j in range(i+1, N):
        if j <= K * N - 1 and A_lst[i] > A_lst[j]:
            count1 += 1
    for j in range(N):
        if j <= K * N - 1 and A_lst[i] > A_lst[j]:
            count2 += 1

count2 %= mod

F = (K-1)*K // 2
F %= mod

ans = count1 * K + count2 * F
ans %= mod

"""
if A_lst[N-1] > A_lst[0]:
    ans -= 1
"""

print(ans)

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
N,K = map(int,input().split(' '))
l = list(map(int,input().split(' ')))

u = 10**9 + 7
in_cnt = 0
out_cnt = 0
for i in range(N):
    k = l[i]
    for j in l[i:]:
        if k > j:
            in_cnt += 1
for i in range(N):
    k = l[i]
    for j in range(N):
        kk = l[j]
        if i==j:
            continue
        if k > kk:
            out_cnt += 1
cnt = out_cnt*(K*(K-1)//2)
cnt += in_cnt*K
print(cnt%u)

Submission status: Accepted

Solution code:
n,k = map(int, input().split())
a = list(map(int,input().split()))
aa = sorted(a)
c = 0
d = 0
for i in range(n):
  c += len([l for l in a[i:] if l < a[i]]) % (10**9+7)
  c = c % (10**9+7)
  d += aa.index(a[i])
  d = d % (10**9+7)
c *= k
K = (0+k-1)*k // 2
c += (d*K) % (10**9+7)
c = c % (10**9+7)
print(c)

Submission status: Accepted

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

def solve():
  n,k = (int(i) for i in input().split())
  a = list(int(i) for i in input().split())
  mod = 10**9+7
  firstt = [0]*n
  for i in range(n-1):
    for j in range(i+1,n):
     if a[i] > a[j]:
      firstt[i] += 1
      
  secondt = [0]*n
  a2 =  a + a
  for i in range(n):
   for j in range(i+1,2*n):
    if a2[i] > a2[j]:
      secondt[i] += 1
  
  query = []
  for i in range(n):
    query.append(secondt[i]-2*firstt[i])

  ans = 0
  for i in range(n):
    tmp = 0
    tmp += (query[i]*(k*(k-1)))
    tmp += (firstt[i]*(k*(k+1)))
    tmp //= 2
    ans += tmp
  print(ans%mod)
solve()

Submission status: Accepted

Solution code:
#coding:utf-8
import collections

N, K = list(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

inner_count = count_inversion(A)

A = sorted(A)

duplicate = {k:1 for k,v in enumerate(A)}

A_index = 0
duplicate_index = 0

while A_index < len(A)- 1:
    if A[A_index+1] == A[A_index]:
        duplicate[A_index + 1] -= 1
        duplicate[duplicate_index] += 1
    else:
        duplicate_index = A_index + 1
    A_index += 1
        
count = 0
for k, v in duplicate.items():
    count += (v * k * K * (K-1) )//2

count += inner_count * K

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

Submission status: Accepted

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

M = 10 ** 9 + 7

R = [0] * N
L = [0] * N

for i in range(N):
    Tr = 0
    if i <= N - 2:
        for r in range(i + 1, N):
            if A[i] > A[r]:
                Tr += 1
    Tl = 0
    if i > 0:
        for l in range(i - 1, -1, -1):
            if A[i] > A[l]:
                Tl += 1
    R[i] = Tr
    L[i] = Tl

sum = 0
for i in range(N):
    sum += R[i] * K * (K + 1) // 2 % M + L[i] * (K - 1) * K // 2 % M


print(sum % M)

Submission status: Accepted

Solution code:
from bisect import bisect_left

N, K = map(int, input().split())
A = list(map(int, input().split()))
ans = 0
B = sorted(A)
for i in range(N):
    for j in range(i + 1, N):
        if A[i] > A[j]:
            ans += 1
ans *= K
S = set(A)
less = [0] * 2000
for s in S:
    less[s - 1] = bisect_left(B, s)
    ans += bisect_left(B, s) * A.count(s) * (K * (K - 1)) // 2
    ans %= 10 ** 9 + 7

print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
A = list(map(int, input().split()))
sort_A = sorted(A, reverse = True)
mod = 10**9 + 7
mi = 0
cnt = 0
for i in range(n-1):
  a = A[i]
  for j in range(i+1, n):
    b = A[j]
    if a < b:
      mi += 1
for i in range(n-1):
  a = sort_A[i]
  for j in range(i+1, n):
    b = sort_A[j]
    if a > b:
      cnt += 1
print((cnt * (k*(k+1)//2) - (mi * k)) %mod)

Submission status: Accepted

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

LARGE = 10 ** 9 + 7
res_lr = 0
res_rl = 0

for i in range(N):
    for j in range(N):
        if A_list[i] > A_list[j]:
            if i < j:
                res_lr += 1
            else:
                res_rl += 1

res_1 = (res_lr * K) % LARGE
res_2 = ((res_lr + res_rl) * K * (K - 1) // 2) % LARGE

print((res_1 + res_2) % LARGE)

Submission status: Accepted

Solution code:
import sys
N,K=map(int, sys.stdin.readline().split())
A=map(int, sys.stdin.readline().split())

mod=10**9+7

naka=[ 0 for _ in range(N)]
soto=[ 0 for _ in range(N)]

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

v=0
for i in range(N-1):
	if A[i]<A[i+1]:
		v=i+1
		soto[i+1]=v
	else:
		soto[i+1]=v		


print (sum(naka)*K+sum(soto)*K*(K-1)/2)%mod

Submission status: Accepted

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

a_list = [int(a) for a in input().split()]

result_list = [[0,0] for _ in range(N)]
for i in range(N):
    aa = a_list[i]

    f = 0
    for j in range(N):
        an = a_list[j]
        if i == j:
            f = 1
            continue

        if aa > an:
            result_list[i][f] += 1

c = 0
for i, j in result_list:
    kk = i+j
    c += (kk*K*(K+1)//2 - i*K)

n = 1000000000+7

print(c%n)

Submission status: Accepted

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

mp = {}

for i in range(20000):
    mp[i] = (0, 0)

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

for i in mp:
    tmp = mp[i][1] * ((k + 1) * k) // 2
    res += tmp
    tmp = mp[i][0] * ((k - 1) * k) // 2
    res += tmp

MOD = 10 ** 9 + 7
print(res % MOD)

Submission status: Accepted

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


class BinaryIndexedTree:
    """
        Parameters
        ----------
        array : list
            to construct BIT from
        f : func
            binary operation of the abelian group
        fi : func
            inverse mapping of f
            i.e. f(a, b) == c <-> fi(c, a) == b
        e : 
            identity element of the abelian group
        size : int
            limit for array size
    """

    def __init__(self, array, f, fi, e, size):
        self.f = f
        self.fi = fi
        self.e = e
        self.size = size
        self.n = len(array)
        self.dat = [e] * (size + 1)
        self.array = [e] * size
        self.build(array)

    def build(self, array_):
        for i, v in enumerate(array_):
            self.modify(i, v)

    def modify(self, p, v):
        """
        set value at position p (0-indexed)
        """
        self.add(p, self.fi(v, self.array[p]))

    def add(self, p, dv):
        """
        add value at position p (0-indexed)
        """
        fi, dat, f, size, array = self.fi, self.dat, self.f, self.size, self.array
        array[p] = f(array[p], dv)
        p += 1
        while p <= size:
            dat[p] = f(dat[p], dv)
            p += p & -p

    def query(self, l, r):
        """
        result on interval [l, r) (0-indexed)
        """
        return self.fi(self._query(r), self._query(l))

    def _query(self, p):
        dat, f, res = self.dat, self.f, self.e
        while p:
            res = f(res, dat[p])
            p -= p & -p
        return res


f = lambda x, y: x + y
fi = lambda z, x: z - x
e = 0
BIT = BinaryIndexedTree([0] * 2001, f=f, fi=fi, e=e, size=2001)
ans1 = N * (N + 1) // 2
for a in A:
    BIT.add(a, 1)
    ans1 -= BIT._query(a + 1)

BIT = BinaryIndexedTree([0] * 2001, f=f, fi=fi, e=e, size=2001)
ans2 = 2 * N * (2 * N + 1) // 2
for a in A:
    BIT.add(a, 1)
    ans2 -= BIT._query(a + 1)
for a in A:
    BIT.add(a, 1)
    ans2 -= BIT._query(a + 1)

BIT = BinaryIndexedTree([0] * 2001, f=f, fi=fi, e=e, size=2001)
ans3 = 3 * N * (3 * N + 1) // 2
for a in A:
    BIT.add(a, 1)
    ans3 -= BIT._query(a + 1)
for a in A:
    BIT.add(a, 1)
    ans3 -= BIT._query(a + 1)
for a in A:
    BIT.add(a, 1)
    ans3 -= BIT._query(a + 1)

x = ans1
y = ans2
z = ans3
mod = 10**9 + 7
K -= 1
print(((
    (K - 2) * (K - 1) * x - 2 * K * (K - 2) * y + (K - 1) * K * z) // 2) % mod)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import collections


def input():
    return sys.stdin.readline()[:-1]


def main():
    N, K = map(int, input().split())
    A = [int(i) for i in input().split()]
    mod = 10**9+7
    ans = 0
    count = 0
    c = collections.Counter(A)
    k = list(c.keys())
    k.sort(reverse=True)

    # print(c)
    s = c[k[0]]
    for i in k[1:]:
        count += s*c[i]
        s += c[i]

    for i, v in enumerate(A):
        for j in range(0, i):
            if A[j] > v:
                ans += 1
    # print(ans, count)

    print((ans*K+K*(K-1)//2*count) % mod)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def solve():
    mod = 10 ** 9 + 7
    N, K = map(int, input().split())
    A = [int(i) for i in input().split()]
    count = 0
    for i in range(N):
        inner_count = 0
        all_count = 0
        for j in range(N):
            if A[i] < A[j]:
                all_count += 1
            if i > j and A[i] < A[j]:
                inner_count += 1
        # print('i', i, 'all', all_count, 'inner', inner_count,
        #       'A[i]', A[i],
        #       all_count * ((K - 1) * K // 2) + inner_count * K)
        count += all_count * ((K - 1) * K // 2) + inner_count * K
        count %= mod
    print(count)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:

MOD = 10 **9 +7
 
N, K = [int(v) for v in raw_input().split()]
A = [int(v) for v in raw_input().split()]

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



#print('Inversions =  {} '.format(inversions))
#print('Versions =  {} '.format(versions))
res = ((K + 1) * K)/2 * inversions + (K * (K-1))/2 * versions
res = res % MOD
print(res)

Submission status: Accepted

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

ans=0
L= (K*(K+1)//2) % 1000000007

for i in range(N):
    for j in range(N):
        if i==j:
            continue
        if A[i] > A[j]:
            if i < j:
                ans = (ans + L) % 1000000007
            else:
                ans = (ans + L-K) % 1000000007

print(int(ans))

Submission status: Accepted

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

c=0
for e,i in enumerate(A):
    for j in A[e:]:
        if i>j:c+=K*(K+1)//2
        if i<j:c+=K*(K-1)//2
            
print(c%(10**9+7))

Submission status: Accepted

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 += dic[i] * (num * (k - 1) * k // 2) + li[i] * k
        ans %= MOD
    num += dic[i]
print(ans)

Submission status: Accepted

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

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

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

A_s = sorted(A)
num_out = 0
for i in range(0, N):
    for j in range(i+1, N):
        if A_s[i] < A_s[j]:
            num_out += 1

MOD = int( 1e9 + 7 )

print((K*(K-1)//2*num_out+K*num_in)%MOD)

Submission status: Accepted

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


Aset = set(As)
As_tmp = [a for a in As]
from collections import defaultdict
d = defaultdict(int)

# # 自分より小さい数は何個あるか
# for a_set in sorted(Aset):
#     cnt = 0
#     for a in As_tmp:
#         if a_set > a:
#             cnt += 1
#     d[a_set] = cnt


# 1個目転倒数はいくつ？(初項)
cnt = 0
for i,ai in enumerate(As):
    for aj in As[i:]:
        # print(bi,bj)
        if ai > aj:
            cnt += 1 
# 最大の転倒数は、最大値を引いたもの(階差)
sumA = 0
rA = sorted(As,reverse=True)
for i,ai in enumerate(rA):
    for aj in rA[i:]:
        if ai > aj:
            sumA += 1 
# print("sum",sumA,"cnt",cnt) 
mod = 10**9 + 7     
ans = sumA*(k-1)*k//2 + cnt*k
print(ans%mod)

Submission status: Accepted

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
double = 0
for i in range(len(a_list)):
    for j in range(len(a_list)):
        if i < j and  a_list[i] > a_list[j]:
            single += 1
        if a_list[i] > a_list[j]:
            double += 1


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

if k == 1:
    print(single)
    sys.exit()
else:
    value = k * single
    value += (k*(k-1)//2) * double
    value %= big_num
    print(value)

Submission status: Accepted

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

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

d={}
B=sorted(A)
for a in B:
	if a not in d:d[a]=1
	else:d[a]+=1

PP=10**9+7
y=0
t=0
for a in d:
	y+=(t*d[a])%PP
	t+=d[a]
print((((cnt*K)%PP+(y*(K*(K-1)//2))%PP))%PP)

Submission status: Accepted

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

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

MOD = 1000000007
result = base * K + (diff * K * (K - 1) // 2)
result %= MOD
print(result)

Submission status: Accepted

Solution code:
def modInverse(a,m):
    m0 = m 
    y = 0
    x = 1
  
    if (m == 1) : 
        return 0
  
    while (a > 1) : 
        q = a // m 
        t = m 
        m = a % m 
        a = t 
        t = y 
        y = x - q * y 
        x = t 
  
    if (x < 0) : 
        x = x + m0 
  
    return x 

def main():
    n,k = map(int,input().split())
    arr = list(map(int,input().split()))
    mod = 10**9+7
    ans = 0
    for i in range(n):
        for j in range(i+1,n):
            if arr[i] > arr[j]:
                ans += 1

    ans = ans*k
    ans = ans%mod

    dist = {}
    for i in arr:
        if i not in dist.keys():
            dist[i] = 1
        else:
            dist[i] += 1

    arr = []
    for i in dist.keys():
        arr.append((i,dist[i]))

    arr.sort(reverse = True)
    count = 0
    total = 0
    for i in arr:
        total += i[1]

    #print(arr)
    for i in arr:
        total -= i[1]
        count += total*i[1]

    count = count*k*(k-1)
    count = count%mod
    count = count*modInverse(2,mod)
    count = count%mod
    ans += count
    print(ans%mod)
    


main()

Submission status: Accepted

Solution code:
import numpy as np

n, k = np.array(input().split(" ")).astype(int)
a = np.array(input().split(" ")).astype(int)

num_less = 0
num_more = 0
for i in range(n):
    for j in range(i,n):
        if i==j:
            continue
        if a[i] > a[j]:
            num_less += 1
        elif a[i] < a[j]:
            num_more += 1

num_all = (num_less%(10**9 + 7)) * ((k*(k+1)//2)%(10**9+7))
num_all += (num_more%(10**9 + 7)) * ((k*(k-1)//2)%(10**9+7))
print(num_all%(10**9 + 7))

Submission status: Accepted

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,2000+2):
        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: Accepted

Solution code:
import bisect
n, k = map(int, input().split())
a = list(map(int, input().split()))
b = [0] * 2001
c = [0] * 2001
cnt = 0
for i in range(len(a)):
    b[a[i]] += 1
for i in range(len(a)):
    c[a[i]] += 1
    sb = sum(b[a[i] + 1:])#全カウント
    sc = sum(c[a[i] + 1:])#これまでのカウント
    ss = (sc + (sc + sb * (k - 1))) * k // 2
    cnt += ss
    cnt %= (10 ** 9 + 7)
print(cnt)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def main():
    def inv(a):
        a_sort = sorted(list(set(a)))
        n = len(a_sort) + 1
        bit = [0] * n
        tento = 0
        for ai, ak in enumerate(a):
            wa = 0
            i = ii = a_sort.index(ak) + 1
            while i:
                wa += bit[i]
                i -= i & -i
            tento += ai - wa
            while ii < n:
                bit[ii] += 1
                ii += ii & -ii
        return tento

    md = 10 ** 9 + 7
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    if k <= 4:
        a = a * k
        print(inv(a))
        exit()
    t1 = inv(a)
    t2 = inv(a * 2)
    t3 = inv(a * 3)
    d1 = t2 - t1
    d2 = t3 - t2
    dd = d2 - d1
    print((t1 + d1 * (k - 1) + dd * (k - 2) * (k - 1) // 2) % md)

main()

Submission status: Accepted

Solution code:
from collections import defaultdict

mod = 10**9 + 7

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

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

num_dic = defaultdict(int)
num_smaller = [0 for x in range(2001)]

for num in a:
  num_dic[num] += 1
  for i in range(num + 1, 2001):
    num_smaller[i] += 1

cnt = 0
#print(num_dic)
#print(num_smaller[0:5])
# m番目以降にある数
for key, v in num_dic.items():
  # print(key, v, num_smaller[key])
  cnt += (num_smaller[key] * v * (k * (k-1)) // 2) % mod
  
# print(cnt)
# m番目にある数
for i in range(0, n - 1):
  for j in range(i + 1, n):
    if a[i] > a[j]:
      cnt += k
cnt %= mod
print(cnt)

Submission status: Accepted

Solution code:
import sys

M = int(1e9 + 7)
n, k = map(int, sys.stdin.readline().strip().split())
xs = list(map(int, sys.stdin.readline().strip().split()))
x = 0
y = 0
for i in range(n):
    for j in range(n):
        if i < j and xs[i] > xs[j]:
            x += 1
        if i < j and xs[i] < xs[j]:
            y += 1

ans = ((x * k * (k + 1) // 2) % M) + ((y * k * (k - 1) // 2) % M)
print(ans % M)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = [int(x) for x in input().split()]
sum = 0

for i in range(n):
    for j in range(n):
        if a[i] > a[j]:
            sum += (k+1)*k//2 if j > i else k*(k-1)//2

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

Submission status: Accepted

Solution code:
import math

n,k=map(int,input().split())
a = [int(i) for i in input().split()]
dic={}
ans=0
for i in a:
    if i in dic:
        dic[i]+=1
    else:
        dic[i]=1

dic=sorted(dic.items() , key=lambda x:x[0], reverse=True)
check=0
for i in range(len(dic)-1):
    ans+=dic[i][1]*(((1+(k-1))*(k-1))//2)*(n-check-dic[i][1])
    check +=dic[i][1]

check=0
for i in range(n):
    for j in range(i+1,n):
        if a[i]>a[j]:
            check+=1
    
    
print((ans+check*k)%(10**9+7))

Submission status: Accepted

Solution code:
mod = 10**9 + 7

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

a = 0
b = 0

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

ans = a*K*(K+1)//2 + b*(K-1)*K//2
ans %= mod
print(ans)

Submission status: Accepted

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

b = [0 for _ in range(2001)]
in_range = 0

# 与えられたA内の転倒数 in_range
for i in A:
    in_range += sum(b[i+1:])
    b[i] += 1
    
# Aを二つつなげた時、それらの間
compare_to_another = 0
for i in A:
    compare_to_another += sum(b[i+1:])

# もとめるもの
answer = ( (in_range * k) + (compare_to_another * (k*(k-1))//2) ) % (10**9 + 7)
print(answer)

Submission status: Accepted

Solution code:
from bisect import bisect
mod = 10**9+7
n,k = map(int,input().split())
*a,= map(int,input().split())
b = []
ans = 0
for j,x in enumerate(a):
	i = bisect(b,x)
	ans += (j-i)*k
	b.insert(i,x)
a.sort(reverse=True)
bef = a[-1]
j=0
for i,cur in enumerate(a):
	if cur==bef:
		ans += k*(k-1)*j//2
	else:
		ans += k*(k-1)*i//2
		j = i
		bef = cur
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
C = 0
t = 0
for i in range(n):
    for j in range(n):
        if A[i] > A[j] and i < j:
            t += 1
        if A[i] > A[j]:
            C += 1
print((t * k + (C * k * (k - 1) // 2)) % mod)

Submission status: Accepted

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

mae=0
ato=0
ans=0
sum = (k*(k-1))//2
for i in range(n):
    mae, ato = 0, 0
    for j in range(n):
        if a[i]>a[j]:
            if i<j:
                ato+=1
            else:
                mae+=1
    ans += (sum)*(mae+ato) + (ato*k)
    ans%=mod

print(ans)

Submission status: Accepted

Solution code:
INFTY=10**9+7
N,K = map(int,input().split())
A = list(map(int,input().split()))
if K==1:
    tot = 0
    for i in range(1,N):
        for j in range(i):
            if A[j]>A[i]:
                tot += 1
else:
    B = [0 for _ in range(2*N)]
    A = A+A
    for i in range(1,2*N):
        cnt = 0
        for j in range(i):
            if A[j]>A[i]:
                cnt += 1
        B[i] = cnt
    tot = 0
    for i in range(N):
        a = B[i]
        d = B[i+N]-B[i]
        tot = (tot + (K*(a-d))%INFTY + ((d*(K+1)*K)//2)%INFTY)%INFTY
print(tot)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
B = A[::-1]
MOD = int(1e9+7)
count1 = 0
count2 = 0
for i in range(N):
    for j in range(N - 1, i, -1):
        if A[j] < A[j-1]:
            A[j], A[j-1] = A[j-1], A[j]
            count1 += 1
        if B[j] < B[j-1]:
            B[j], B[j-1] = B[j-1], B[j]
            count2 += 1
print((count1 * K * (K+1) // 2 + count2 * K * (K-1) // 2) % MOD)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#第一回日本最強プログラマー学生選手権-予選- B

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,k = LI()
a = LI()
x = [0]*n
y = [0]*n
for i in range(n):
    s,t = 0,0
    for j in range(i,n):
        if a[i] > a[j]:
            s += 1
    for j in range(i):
        if a[i] > a[j]:
            t += 1
    x[i] = s
    y[i] = t
ans = 0
for i in range(n):
    ans += k*(2*x[i] + (x[i]+y[i])*(k-1))//2
    ans %= mod
print(ans)

Submission status: Accepted

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

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

count += back * (1+k) * k // 2 + forward * k * (k-1) // 2
ans = count % mod
print(ans)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
lst = [int(i) for i in input().split()]
ss = 0
for i in range(0,len(lst)):
    b,a = 0,0
    for ii in range(0,i):
        if lst[ii] < lst[i]:
            b += 1
    for ii in range(i,len(lst)):
        if lst[i] > lst[ii]:
            a += 1
    n1 = k
    tna = a*n1
    ta = a
    aa = n1*(tna+ta)//2
    n2 = k-1
    tnb = b*n2
    tb = b
    bb = n2*(tnb+tb)//2
    ss += aa+bb
print(ss%(10**9+7))

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = [int(x) for x in input().split()]
mod = 1000000007
t = 0
for i in range(n):
    for j in range(n-i-1):
        if a[i+j+1] < a[i]:
            t += 1
a.sort()
s = 0
for i in range(n):
    for j in range(n-i-1):
        if a[i+j+1] > a[i]:
            s += 1
key = ((k%mod)*((k-1)%mod)//2)%mod
ans = ((t*k)%mod+(s*key)%mod)%mod
print(ans)

Submission status: Accepted

Solution code:
n,k=[int(i) for i in input().split()]
a=[int(i) for i in input().split()]
ookii=[0]*n
num=[0]*n
for i in range(n):
    for j in range(n):
        if a[i]<a[j] and i!=j:
            ookii[i]+=1
            if i>j:
                num[i]+=1
ans=0
for i in range(n):
    ans+=k*(2*num[i]+(k-1)*ookii[i])//2
    ans%=1000000007
print(ans)

Submission status: Accepted

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

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

A.sort()

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

print((K * (K - 1) // 2 * inversion2 + K * inversion) % MOD)

Submission status: Accepted

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

Solution code:
n,m=map(int,input().split())
hoge=list(map(int,input().split()))
ans=0
for i in range(len(hoge)):
  huga1=[hoge[j] for j in range(len(hoge)) if hoge[j]<hoge[i]]
  huga2=[hoge[j] for j in range(len(hoge)) if hoge[j]<hoge[i] and j>i]
  ans+=(len(huga1)*int(m*(m+1)//2))%(10**9+7)
  ans-=(len(huga1)-len(huga2))*m
  ans=ans%(10**9+7)
print(ans)

Submission status: Accepted

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

cnt = 0
cnt2 = 0
for i, a1 in enumerate(A):
    for j, a2 in enumerate(A):
        if a2 < a1:
            cnt += 1
            if j > i:
                cnt2 += 1

ans = cnt2 * K + (K * (K - 1)) // 2 * cnt
print(ans % ((10 ** 9) + 7))

Submission status: Accepted

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

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

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

aa=(a*k*(k+1)//2)%(10**9+7)
bb=(b*k*(k-1)//2)%(10**9+7)

ans=(aa+bb)%(10**9+7)
print(int(ans))

Submission status: Accepted

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

 
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
n, k = map(int, input().split())
M = 10**9 + 7

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

def s(n):
    return ((n + 1) * n) // 2

def calc_t(tk):
    tmp = a * tk
    t = [0] * n
    for i in range(n):
        ans = 0
        for j in range(i + 1, n * tk):
            if tmp[i] > tmp[j]:
                ans += 1
        t[i] = ans
    return np.array(t)

t1 = calc_t(1)
t2 = calc_t(2) - t1 * 2
print((int(sum(t1)) * s(k) + int(sum(t2)) * s(k - 1)) % M)

Submission status: Accepted

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

pre_countA = 0
pre_countB = 0
if N >= 2:
    for i in range(N):
        for k in range(i + 1, N):
            if A[i] > A[k]:
                pre_countA += 1
    for i in range(N):
        for k in range(N):
            if A[i] > A[k]:
                pre_countB += 1

    result = pre_countA * K
    result += pre_countB * (((K - 1) * (1 + (K - 1))) // 2)
    print(result % (10 ** 9 + 7))
else:
    print(0)