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:
import sys

if sys.platform =='ios':
    sys.stdin=open('input_file.txt')
    
N,K=map(int,input().split())
l=list(map(int,input().split()))

cnt=0
cnt2=0
p=10**9+7
for i in range(N):
	for j in range(N):
		if l[i]>l[j] and j>i:
			cnt+=1
for k in range(N):
	for m in range(N):
		if l[k]>l[m] and k>m:
			cnt2+=1
Cn=K*(K+1)//2*cnt+(K-1)*K//2*cnt2
print(Cn%p)

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
t = (k*(k-1))//2
ans = 0
cnt1,cnt2 = 0,0
for i in range(n):
    for j in range(i,n):
        if A[i]>A[j]:
            cnt1 += 1
cnt1 *= k

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

cnt2 *= t
print((cnt1+cnt2)%MOD)

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

sn = lambda : stdin.readline().rstrip()
an = lambda : map(int, stdin.readline().split())
ni = lambda : int(sn())

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

def main():
  n, k = an()
  a = list(an())

  mod = int(1e9)+7
  ans = 0
  x = a[:] 
  for i, ai in enumerate(x):
    cnt = 0
    for j in range(i+1, n):
      if ai > x[j]:
        cnt += 1
    tcnt = 0
    for j in range(i+1):
      if ai > x[j]:
        tcnt += 1

    ans += f(k) * cnt
    ans %= mod
    ans += f(k - 1) * tcnt
    ans %= mod

  print(ans)

main()

Submission status: Accepted

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

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

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

mod = 10 ** 9 + 7
N, K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]

bit = Bit(2020)
X = 0
for i, p in enumerate(A):
    bit.add(p, 1)
    X += i + 1 - bit.sum(p)

bit = Bit(2020)
Y = 0
for i, p in enumerate(A * 2):
    bit.add(p, 1)
    Y += i + 1 - bit.sum(p)
Y -= 2 * X

ans = (X * K + Y * K * (K - 1) // 2) % mod
print(ans)

Submission status: Accepted

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

import numpy as np

MOD = 10**9 + 7

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

# 同じグループ内
def type_1():
    bl1 = A[:,None] > A[None,:]
    bl2 = np.arange(N,dtype=np.int64)[:,None] < np.arange(N,dtype=np.int64)[None,:]
    x = ((bl1 & bl2)*1).astype(np.int64).sum() % MOD
    return x*K%MOD

def type_2():
    # グループ間
    counter = np.bincount(A)
    cum = counter.cumsum()
    larger = N-cum
    x = (larger * counter % MOD).sum() % MOD
    y = K*(K-1)//2 % MOD
    return x*y%MOD

answer = (type_1() + type_2()) % MOD
print(answer)

Submission status: Accepted

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

saki=0
for i in range(n):
    for j in range(n):
        if a[i]>a[j]:
            saki=(saki+1)%mod

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
c=0
d=0
for i in range(n-1):
  for j in range(i+1,n):
    if a[i]>a[j]:
      d+=1
for i in range(n):
  for j in range(n):
    if a[i]>a[j]:
      c+=1
ans=k*d+c*k*(k-1)//2
print(int(ans%(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-1):
    for j in range(i+1,N):
        if A[i] > A[j]:
            ans += 1
ans *= K

from collections import Counter
ctr = Counter(A)

P = (K*(K-1)//2) % MOD

s = 0
for k,v in sorted(ctr.items()):
    tmp = (v*s*P)%MOD
    ans += tmp
    ans %= MOD
    s += v

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from sys import stdin
import numpy as np

n, k = map(int, stdin.readline().rstrip().split(' '))
arg = np.array(list(map(int, stdin.readline().rstrip().split(' '))))
small = []
for i, val in enumerate(arg):
    small.append([np.count_nonzero(arg[:i] < val), np.count_nonzero(arg[i+1:] < val)])
smallnd = np.array(small)

a, b = np.sum(smallnd, axis=0)

res = k*(int(a)*(k-1)+int(b)*(k+1))//2

print(int(res % (10**9+7)))

Submission status: Accepted

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

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

total_lower = 0
for i in range(len(a_list)):
    total_lower += len([x for x in a_list if x < a_list[i]])


total_k = (K * (K - 1)) // 2
total = (total_lower * total_k+ inversion * K) % MOD
print(total)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

def main():
    N, K = [int(i) for i in input().split()]
    a_list = [int(i) for i in input().split()]
    cnt = 0
    cnt = sum([a_list[i] > a_list[j] for i in range(N) for j in range(i, N)])
    second_cnt = sum([a_list[i] > a_list[j] for i in range(N) for j in range(i)])
    if K > 1:
        second_cnt *= (K * (K - 1)) // 2
    cnt = cnt * ((K * (K + 1)) // 2)
    print((cnt + second_cnt) % (10 ** 9 + 7))


if __name__ == "__main__":
    main()

Submission status: Accepted

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

inversion = 0
for i in range(len(a_list)):
    for j in range(len(a_list) - 1, i, -1):
        if a_list[j] < a_list[j - 1]:
            a_list[j], a_list[j - 1] = a_list[j - 1], a_list[j]
            inversion += 1

total_lower = 0
for i in range(len(a_list)):
    total_lower += len([x for x in a_list if x < a_list[i]])


total_k = (K * (K - 1)) // 2
total = (total_lower * total_k+ inversion * K) % MOD
print(total)

Submission status: Accepted

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

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

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

res = cnt*k + cnt_2*k*(k-1)//2
res %= 10**9 + 7
print(res)

Submission status: Accepted

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

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

d=10**9+7

c=0

for i in range(N-1):
    for j in range(i+1,N):
        if A[i]>A[j]:
            c+=1
c=c%d

cc=0

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

cc=cc%d

e=(K*(K-1)//2)%d

print(int(((c*K)%d+(cc*e)%d)%d))

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
a0 = a[0]
an = a[n-1]
now = a0
c_self = 0
c_inter = 0
for i in range(n):
    for j in range(i,n):
        #print(i,j)
        #print("a",a[i],a[j])
        if a[i] > a[j]:
            c_self += 1
        if a[i] != a[j]:
            c_inter += 1

t =( (k-1) * k//2) % (10**9 + 7)
l = (k * c_self) % (10**9 + 7)
q = (t * c_inter) % (10**9 + 7)
# ans =  (k * c_self   + 0.5 * k*(k-1) * c_inter) % (10**9+7)
ans = (l + q ) % (10**9 + 7)
print(int(ans))

Submission status: Accepted

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

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

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


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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools

DIV_NUM = 1000000000 + 7

N,K = map(int, input().split())
A = [int(x) for x in input().split()]
if N==1:
    print(0)
    exit()

answer = 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]
            answer += 1

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

answer = answer % DIV_NUM
answer = (answer * K) % DIV_NUM
q = q % DIV_NUM
answer = answer + q * K * (K-1) // 2
answer = answer % DIV_NUM
print(answer)

Submission status: Accepted

Solution code:
MOD = 1000000007
N,K = map(int,input().split())
A = list(map(int,input().split()))
def bubble_sort(A):
    cnt = 0
    for i in range(len(A)):
        for j in range(len(A)-1, i, -1):
            if A[j] < A[j-1]:
                A[j], A[j-1] = A[j-1], A[j]
                cnt += 1
    return cnt
def sigma(k):
    return int(k*(k+1)//2)
C = []
for k in range(2):
    C.extend(A)
cnt = bubble_sort(A)
diff = bubble_sort(C) - 2 * cnt
a = (K*cnt)
b = (diff*sigma(K-1))
print ((a+b)%MOD)

Submission status: Accepted

Solution code:
from bisect import bisect

def solve():
	mod = 10**9+7
	n,k,*a = map(int,open(0).read().split())
	b = []
	ans = 0
	for j,x in enumerate(a):
		i = bisect(b,x)
		ans += (j-i)*k
		b.insert(i,x)
	bef = max(a)
	j=0
	for i,cur in enumerate(b[::-1]):
		if cur==bef:
			pass
		else:
			j = i
			bef = cur
		ans += k*(k-1)*j//2
	print(ans%mod)

if __name__=="__main__":
	solve()

Submission status: Accepted

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

Submission status: Accepted

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

A=list(map(int,input().split()))
L=[0]*N
R=[0]*N

for i in range(N):
    for j in range(N):
        if j<i and A[j]<A[i]:
            L[i]+=1
        if j>i and A[j]<A[i]:
            R[i]+=1
ans = 0
K1=((1+K)*K//2)%(10**9+7)
K2=(K*(K-1)//2)%(10**9+7)

for i in range(N):
    ans +=(R[i]*K1+L[i]*K2)%(10**9+7)

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

print(int(ans))

Submission status: Accepted

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

if k % 2 == 0:
    mul = (1 + k) * (k // 2)
else:
    mul = (1 + k) * (k // 2) + (k // 2 + 1)
mul2 = 0
if k > 1:
    k -= 1
    if k % 2 == 0:
        mul2 = (1 + k) * (k // 2)
    else:
        mul2 = (1 + k) * (k // 2) + (k // 2 + 1)
print(((cnt * mul) + (cnt2 * mul2)) % 1000000007)

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
A = list(map(int, input().split()))
c1 = 0
c2 = 0
for i in range(n-1):
  for k in range(n-1-i):
    if A[i] > A[k+1+i]:
      c1 += 1
for i in range(n):
  for k in range(n):
    if A[i] > A[k]:
      c2 += 1
c3 = (m * (m - 1) // 2)%(10**9+7)
c4 = (c3*c2)%(10**9+7)
c5 = (c1*m)%(10**9+7)
print(int((c4+c5)%(10**9+7)))

Submission status: Accepted

Solution code:
n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
k_sum = (k-1)*k//2

ans = 0
minus = 0
for i in range(n):
    tentou1 = 0
    tentou2 = 0
    for j in range(n):
        if i<j and a[i]>a[j]:
            tentou1 += 1
        if a[i]>a[j]:
            tentou2 += 1
    ans += tentou1*k+tentou2*k_sum

print(ans%1000000007)

Submission status: Accepted

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

MOD=10**9+7

def count(A,N):
    arr=[0]*N
    for i, ai in enumerate(A[:-1]):
        cnt=0
        for aj in A[i+1:]:
            if ai > aj:
                cnt+=1
        arr[i]=cnt
    return arr

s1=sum(count(A,N))
s2=sum(count(sorted(A,reverse=True),N))
v=K*(K-1)//2
print((s1*K+v*s2)%MOD)

Submission status: Accepted

Solution code:
import copy


# k = 1の場合の転倒数を求める
def bubble_sort(A):
    cnt = 0
    for i in range(len(A)):
        for j in range(len(A) - 1, i, -1):
            if A[j] < A[j - 1]:
                A[j], A[j - 1] = A[j - 1], A[j]
                cnt += 1
    return cnt


n, k = map(int, input().split())
a = list(map(int, input().split()))
# aはソートされてしまうので、元の並びを複製する
b = copy.deepcopy(a)
# k = 1の場合の転倒数が初項となる等差数列
initial = bubble_sort(a)
ans = initial
bigger = [0] * n
# bigger[i]: リストaに含まれる要素1つに着目した際に、その要素よりも小さい要素の個数
# ex. a = [1,3,4] のとき、 bigger[1] = 1
# 3より小さいのは1のみであるため。
for i in range(n):
    cnt = 0
    for j in b:
        if b[i] > j:
            cnt += 1
    bigger[i] = cnt
# biggerの合計が公差となる
d = sum(bigger)
# 等差数列の和の公式
ans = k * (2 * initial + d * (k - 1)) // 2
print(ans % (10 ** 9 + 7))

Submission status: Accepted

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

mod = 10**9 + 7
B, C = [0]*N, [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
    for j in range(i + 1):
        aj = A[j]
        if ai > aj:
            C[i] += 1

ans = (sum(B) * K * (K + 1) // 2) % mod
ans += (sum(C) * (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()))
x=0
for i in range(n):
    for j in range(i+1,n):
        if a[i]>a[j]:
            x+=1
y=0
for i in range(n):
    for j in range(n):
        if a[i]>a[j]:
            y+=1
cnt=(x*k)+(k*(k-1)//2*y)
print(cnt%(10**9+7))

Submission status: Accepted

Solution code:
def resolve():
    N,K=map(int,input().split())
    a=list(map(int,input().split()))

    A=0
    B=0
    mina=min(a)
    for i in reversed(range(len(a))):
        if a[i]==mina:continue
        for j in range(i,len(a)):
            if a[j]<a[i]:
                A+=1
    for i in reversed(range(len(a))):
        if a[i]==mina:continue
        for j in range(len(a)):
            if a[j]<a[i]:
                B+=1
    ans=int(((2*A+(K-1)*B)*K//2)%(10**9+7))
    print('{}'.format(ans))

resolve()

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
X = 10**9+7
count_self=0
for i,a in enumerate(A):
    j=N-1
    while i<j:
        if a>A[j]:
            count_self+=1
        j-=1
num = [0]*2000
for a in A:
    num[a-1]+=1
count=0
a=0
for n in num:
    if n != 0:
        if a == 0:
            a=n
        else:
            count = count + n*a
            a+=n
print((count_self*K + count*K*(K-1)//2)%X)

Submission status: Accepted

Solution code:
import copy


# k = 1の場合の転倒数を求める
def bubble_sort(A):
    cnt = 0
    for i in range(len(A)):
        for j in range(len(A) - 1, i, -1):
            if A[j] < A[j - 1]:
                A[j], A[j - 1] = A[j - 1], A[j]
                cnt += 1
    return cnt


n, k = map(int, input().split())
a = list(map(int, input().split()))
# aはソートされてしまうので、元の並びを複製する
b = copy.deepcopy(a)
# k = 1の場合の転倒数が初項となる等差数列
initial = bubble_sort(a)
ans = initial
bigger = [0] * n
# bigger[i]: リストaに含まれる要素1つに着目した際に、その要素よりも小さい要素の個数
# ex. a = [1,3,4] のとき、 bigger[1] = 1
# 3より大きいのは4のみであるため。
for i in range(n):
    cnt = 0
    for j in b:
        if b[i] > j:
            cnt += 1
    bigger[i] = cnt
# biggerの合計が公差となる
d = sum(bigger)
# 等差数列の和の公式
ans = k * (2 * initial + d * (k - 1)) // 2
print(ans % (10 ** 9 + 7))

Submission status: Accepted

Solution code:
INF = 1000000007

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

for i in range(len(a)):
    for j in range(len(a)):
        if i == j: continue
        #print(a[i], a[j])
        if a[i] > a[j]:
            if i < j:
                ans_i += 1
            else:
                ans_e += 1
x = ans_i * k
ans = ans_i + ans_e
y = ans * ((k * (k-1) ) // 2)
print(int((x + y) % INF))

Submission status: Accepted

Solution code:
MOD = 1000000007
N,K = map(int,input().split())
A = list(map(int,input().split()))
# import numpy as np
# A = np.random.rand(2000)
def bubble_sort(A):
    cnt = 0
    for i in range(len(A)):
        for j in range(len(A)-1, i, -1):
            if A[j] < A[j-1]:
                A[j], A[j-1] = A[j-1], A[j]
                cnt += 1
    return cnt

def sigma(k):
    #return int((1/2)*(k%MOD)*((k+1)%MOD))
    return k*(k+1)//2


# B = []
# for k in range(K):
#     B.extend(A)
# print (bubble_sort(B))


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

Submission status: Accepted

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

mod = 10**9 + 7
tota = 0
totd = 0

for i in range(N): # iは0からN-1
    for j in range(i+1, N): # jはi+1からN-1
        if A[i] > A[j]:
            tota += 1
    for k in range(N): # kは0からN-1
        if A[i] > A[k]:
            totd += 1

ans = (tota * K + K*(K-1)//2 * totd) % mod # ここで除算の小数点以下は切り捨てなかったせいで答えが合わなかった...
print(int(ans))

Submission status: Accepted

Solution code:

N,K = map(int,input().split())
A = list(map(int,input().split()))
B = A*2
d = []

for i in range(N*2):
  num = B[i]
  target = B[i+1:]
  d.append(len([n for n in target if num > n]))
  
d_each = sum(d[:N]) - sum(d[N:])
first = sum(d[N:])
print(int((K * first + K * (K - 1) * d_each // 2) % (10 ** 9 + 7)))

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)
if N==1:
    print(0)
    exit()

# https://kira000.hatenadiary.jp/entry/2019/02/23/053917
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

answer = bubble_sort(AA)

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

# print(answer,K)
answer = answer % DIV_NUM
answer = int(answer)
answer = (answer * K) % DIV_NUM
q = q % DIV_NUM
answer = answer + q * K * (K-1) // 2
answer = answer % DIV_NUM
print(answer)

Submission status: Accepted

Solution code:
import bisect
MOD = 10**9 + 7
 
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 = [int(item) for item in input().split()]
a = [int(item) for item in input().split()]
bit = Bit(2010 * 2)
ans = 0
 
for i, p in enumerate(a):
    bit.add(p, 1)
    ans += i + 1 - bit.sum(p)
 
a.sort()
big = 0
for item in a:
    big += n - bisect.bisect_right(a, item)
 
times = (k * (k - 1) // 2) % MOD
ans2 = (ans * k) % MOD + (big * times) % MOD
ans2 %= MOD
print(ans2)

Submission status: Accepted

Solution code:
import copy
import sys

input = sys.stdin.readline
n, k = map(int, input().split())
a = list(map(int, input().split()))
b = copy.deepcopy(a)

w = 10 ** 9 + 7

cnta = 0
cntb = 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]

            cnta += 1

for i in range(len(b)):
    for j in range(len(b)):
        if b[i] > b[j]:
            cntb += 1

wa = (k * (k - 1) // 2) * cntb + cnta * k
print(wa % w)

Submission status: Accepted

Solution code:
#!venv/bin/python
#from collections import defaultdict 
from itertools import combinations
from collections import defaultdict
from pprint import pprint
import math
import datetime
import sys
import fcntl
import time

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

smaller = [0] * N
rightSmaller = [0] * N

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

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

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

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
N,K = map(int,input().split())
Alist = np.array(list(map(int,input().split())))
counter = 0
for i,A in enumerate(Alist,0):
    fir_tenti = np.count_nonzero(A>Alist[i:])
    counter += (K*fir_tenti*(K+1))//2
    second_tenti = np.count_nonzero(A>Alist[:i+1])
    counter += (second_tenti*K**2-second_tenti*K)//2

print(int(counter%1000000007))

Submission status: Accepted

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

def cal(A, N):
    cnt1 = 0
    cnt2 = 0
    for i in range(N):
        for j in range(i+1,N):
            if A[N-1-j] > A[N-1-i]:
                cnt1 += 1
    for i in range(N):
        for j in range(N):
            if A[N-1-i] < A[j]:
                cnt2 += 1
    
    return int(cnt1), int(cnt2)
    
    
x, y = cal(A,N)
R = int(1*10**9 +7)
tmp = K*(K-1)//2
ans =  tmp*y + x*K
print(int(ans%R))

Submission status: Accepted

Solution code:
n,k=map(int,input().split())  #n,kに入力
a=list(map(int,input().split()))  #aにA[0]..A[n-1]を入力
ans=0 #答え
S1=0  #一つ目のcount
S2=0  #二つ目のcount

#Aを一回繰り返した時の転倒数
for i in range(n):
  for j in range(n):
    if i<j:
      if a[i]>a[j]:
        S1+=1
        S1%=(10**9+7)
        
#Aを二回繰り返した時の転倒数
for t in range(n):
  for T in range(n):
    if a[t]>a[T]:
      S2+=1
      S2%=(10**9+7)
      
#Aが全て同じ数の時,転倒数は存在しないため"0"を出力,及び実行終了
l=len(list(set(a)))
if l==1:
  print(0)
  exit()

#kから二つ選ぶ個数
if k>=2:
  K=((k*(k-1))//2)%(10**9+7)
elif k==1:
  K=1

#なんて説明すればいいのかわかんない→「そういうことだ（は？）」
ans+=(S1*k)%(10**9+7)
ans+=(S2*K)%(10**9+7)

#念には念を,で%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()))
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
cnt_A = bubble_sort(A)
A_min=0
for i in range(len(A)):
  l_odd = [k for k in A if k<A[i]]
  A_min += len(l_odd)
result = int((cnt_A*K + A_min*(K-1)*K//2)%((10**9)+7))
print(result)

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:
import numpy as np

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

B = 0
C = 0

mod = 10**9 + 7

for i in range(N):
    D = A[i:]
    B = (B + np.sum(D < A[i])) % mod 
    C = (C + np.sum(A < A[i])) % mod 
    
k_sum = int((K-1) * K//2) % mod 

E = (B * K) % mod 
F = (C * k_sum) % mod 

print(int((E+F) % mod ))

Submission status: Accepted

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

x = 0
for l in range(N - 1):
  for r in range(l + 1, N):
    if A[l] > A[r]:
      x += 1
# print(x)
      
AA = A + A
y = 0
for l in range(2 * N - 1):
  for r in range(l + 1, 2 * N):
    if AA[l] > AA[r]:
      y += 1
y -= 2 * x
# print(y)
  
print(int((K * x + K * (K - 1) * y // 2) % (10 ** 9 + 7)))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import *
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    m, d = LI()
    ans = 0
    for i in range(1, m + 1):
        for j in range(10, d + 1):
            if int(str(j)[0]) < 2 or int(str(j)[1]) < 2:
                continue
            if i == int(str(j)[0]) * int(str(j)[1]):
                ans += 1
    print(ans)
    return

#B
def B():
    n, l = LI()
    a = LI()
    d0 = defaultdict(int)
    d1 = defaultdict(int)
    for i in a:
        d0[i] += 1
    for i in range(n):
        b = 0
        for k in range(i+1, n):
            if a[i] > a[k]:
                b += 1
        d1[i] = b
    ans = 0
    d2 = list(d0.items())
    d2.sort()
    d3 = defaultdict(int)
    d = 0
    for key, value in d2:
        d3[key] = d
        d += value
    for i in range(n):
        ans += d3[a[i]] * l * (l-1) // 2 + d1[i] * l
        ans %= mod
    print(ans % mod)
    return

#C
def C():
    n = II()
    s = itertools.product([1, 0], repeat=2 * n)
    a = list(itertools.combinations(range(2*n), 2))
    d = defaultdict(int)
    def dfs(a):
        if len(a) == n:
            lis.append(a)
            return True
        for i in range(n):
            if d[i] == 0:
                d[i] = 1
                for k in range(n):
                    if d[k] == 0:
                        d[k] = 1
                        a.append((i, k))
                        dfs(a)
                        a.remove((i, k))
    lis = []
    dfs([])
    for si in s:
        for di in lis:
            b = list(si[::1])
            for x, y in di:
                for i in range(x, y + 1):
                    b[i] ^= 1
            if sum(b) < 1:
                print(si, di)
                break

    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    B()

Submission status: Accepted

Solution code:
import bisect
from collections import deque
import sys
MAX_INT = int(10e9)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N,K = IL()
a = IL()

cnt = 0
for left in range(N):
  for right in range(left+1,N):
    if a[left] > a[right]:
      cnt += 1
cnt = (cnt*K) %mod

a.sort()
tmp = 0
for i in range(N-1):
  if a[i+1] > a[i]:
    tmp = i+1
  cnt += ((tmp*K*(K-1))//2) %mod

print(int(cnt) %mod)

"""
2 1000000006
2 1

10 3
10 9 8 7 6 5 4 3 2 1
"""

Submission status: Accepted

Solution code:
from collections import Counter

mod = pow(10, 9)+7
n, k = map(int, input().split())
arr = list(map(int, input().split()))

BIT = [0]*(n+1)

def map_arr():
	dct = {}
	idx = 1
	lst = sorted(arr)
	for i in range(n):
		if lst[i] not in dct:
			dct[lst[i]] = idx 
			idx += 1
	return [dct[ele] for ele in arr]

arr = map_arr()
def get_add():
	counter = Counter(arr)
	lst = sorted(counter.items())
	add = lst[0][1]
	dp = [0]*len(lst)
	for i in range(1, len(lst)):
		dp[i] = lst[i-1][1] + dp[i - 1]
	return sum(dp[i]*lst[i][1] for i in range(len(lst)))

def read(idx):
	add = 0
	while idx > 0:
		add += BIT[idx]
		idx -= (-idx & idx)
	return add 

def update(idx):
	while idx <= n:
		BIT[idx] += 1
		idx += (-idx & idx)

inv_count = 0

for i in range(n-1, -1, -1):
	inv_count += read(arr[i]-1)
	update(arr[i])
ans = (k*inv_count)%mod

add = get_add()
multi = (k*(k-1)//2)%mod
ans = (ans + (multi*add)%mod)%mod
print(ans)

Submission status: Accepted

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

MOD = 10 ** 9 + 7

X = 0

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

Y = 0

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

ans = (X * K + K*(K-1)//2 * Y) % MOD

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
MOD=10**9+7
n, k = map(int, input().split())
a = list(map(int, input().split()))
n = len(a)
li = [0] * 2001
t1 = 0
for i in range(n):
  for j in range(i + 1, n):
    if a[i] > a[j]:
      t1 += 1
for x in a:
  li[x] += 1
t2 = 0
for i in range(2000):
  t2 += li[i + 1] * li[i]
  li[i + 1] += li[i]
print((t1 * k + t2 * k * (k - 1) // 2) % MOD)