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

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

B=A+A
C=[0]*N
D=[0]*N

for i in range(N):
    for j in range(i,2*N):
        if(B[i]>B[j]):
            C[i]+=1
for i in range(N):
    for j in range(i,N):
        if(B[i]>B[j]):
            D[i]+=1

c=sum(C)%MOD
d=sum(D)%MOD
c=(c-d)%MOD
t=((K*(2*d+((K-1)*c)))//2)%MOD

print(t)

Submission status: Accepted

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


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

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
l=list(map(int,input().split()))
count=[0 for i in range(n)]
for i in range(n):
  count1=0 
  if i==n-1:
    pass
  else:
    for j in range(i+1,n):
      if l[i]>l[j]:
        count1+=1
  count[i]=count1
l1=sorted(l)
count2=[0 for i in range(n)]
countsub=0
for i in range(1,1+n-1):
  if l1[i]==l1[i-1]:
    count2[i]=count2[i-1]
    countsub+=1
  else:
    count2[i]=count2[i-1]+countsub+1
    countsub=0
ans=0
for i in range(n):
  ans=ans+count2[i]*(m-1)*m//2
  ans=ans+(count[i])*m
  ans%=10**9+7
print(ans)

Submission status: Accepted

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

cnt_in = 0
for i in range(N-1):
    for j in range(i+1, N):
        if A[i] > A[j]:
            cnt_in += 1
ans = (cnt_in * K) % MOD

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

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

print(int(ans))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)
mod = 10**9 + 7
import numpy as np
n, k = map(int,readline().split())
a = np.array(readline().split(),np.int64)
f = 0
r = 0
for i in range(n):
    for j in range(i+1, n):
        if a[i] > a[j] :
            r += 1
        elif a[i] < a[j]:
            f += 1
print((f * k * (k-1) // 2 % mod + r * k * (k+1) // 2 % mod) % mod)

Submission status: Accepted

Solution code:
def solve():
    N, K, *a_l = map(int, open(0).read().split())
    MOD = 10**9+7
    count_a, count_b = 0, 0
    inversion = 0

    for i in range(N):
        for j in range(N):
            if a_l[i] > a_l[j]:
                if i < j:
                    count_a += 1
                count_b += 1

    inversion = count_a * K + count_b * (K * (K - 1)) // 2
    print(inversion%MOD)



if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
def solve():
    N, K, *a_l = map(int, open(0).read().split())
    MOD = 10**9+7
    count_a, count_b = 0, 0
    inversion = 0

    for i in range(N):
        for j in range(N):
            if a_l[i] > a_l[j]:
                if i < j:
                    count_a += 1
                count_b += 1

    inversion = count_a * K + count_b * (K * (K - 1)) // 2
    print(inversion%MOD)


if __name__ == '__main__':
    solve()

Submission status: Accepted

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

Submission status: Accepted

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

countInA = 0
countBetA = 0
for i in range(N):
  for j in range(N):
    if i <= j and A[i] > A[j]:
      countInA += 1
    if A[i] > A[j] :
      countBetA += 1

print( (countInA*K + (countBetA * (K * (K-1) // 2))) % defi)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
a_below = []
count2 = 0
for i in range(n):
    count1 = 0
    for j in range(n):
        if a[j] < a[i]:
            count1 += 1
        if j > i and a[j] < a[i]:
            count2 += 1
    a_below.append(count1)
a_slip = count2

print(((sum(a_below)*k*(k-1))//2 + a_slip*k)%1000000007)

Submission status: Accepted

Solution code:
import bisect
n,k=map(int,input().split())
mod=10**9+7
a=list(map(int,input().split()))
c=sorted(a)
d=[0]*n
e=[0]*n
for i in range(n):
  d[i]=bisect.bisect_left(c,a[i])
for i in range(n):
  cnt=0
  for j in range(i,n):
    if a[i]>a[j]:
      cnt+=1
  e[i]=cnt
st=sum(e)*k%mod
ad=sum(d)%mod
print((st+(ad*(k-1)*k//2)%mod)%mod)

Submission status: Accepted

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

Submission status: Accepted

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

a = 0
for i in range(N):
  for j in range(i + 1,N):
    if A[i] > A[j]:
      a += 1
      
b = 0
A.sort()
for k in A:
  b += A.index(k) * K * (K - 1) // 2
  
print((a * K + b) % 1000000007)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
usiro=0
for i in range(n):
    for j in range(i,n-1):
        if a[i]>a[j+1]:
            usiro+=1            
mae=0
for i in range(n):
    for j in range(0,i):
        if a[i]>a[j]:
            mae+=1
#print(mae)
#print(usiro)
def f(x):
  return x*(x+1)//2
ans=mae*f(k-1)+usiro*f(k)
print(ans%(10**9+7))

Submission status: Accepted

Solution code:
# B Kleene_Inversion

n,k = map(int,input().split(" "))
a = list(map(int,input().split(" ")))
a_inv,b_inv = 0,0
mod = 10**9+7

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

s_inv = a_inv*k+b_inv*(k*(k-1))//2

print(s_inv%mod)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
N, K = map(int,sys.stdin.readline().split())
X = list(map(int, sys.stdin.readline().split()))
firstInv = 0
inv = 0

for i in range(N):
  for j in range(N):
    if X[i] > X[j]:
      inv += 1
      if i < j:
        firstInv += 1

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
lis = list(map(int,input().split()))
yakisoba = [0 for i in range(n)]
yakisaba = [0 for i in range(n)]
for i in range(n):
  for j in range(n):
    if lis[i] > lis[j]:
      yakisoba[i] += 1
      if i < j:
        yakisaba[i] += 1
ans = sum(yakisaba)
num = sum(yakisoba)
nu = sum(yakisaba)
print(((nu*k + num * (k * (k-1)) // 2)%(10 ** 9 + 7)))

Submission status: Accepted

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

one_cnt = 0

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

for i in range(N):
    for j in range(N, 2*N):
        if B[i] > B[j]: two_cnt+=1


one_cnt = one_cnt % 1000000007
two_cnt = two_cnt % 1000000007
ans = one_cnt * K + two_cnt * (K-1)*K//2

print(ans%1000000007)

Submission status: Accepted

Solution code:
N,K = list(map(int,input().split(" ")))
As = list(map(int,input().split(" ")))
ans = 0
MOD = 10 ** 9 + 7
for i in range(N): # i番目の数字
  left = 0
  right = 0
  temp = As[i]
  for j in range(0,i): #左側
    if temp <As[j]:
      left += 1
  ans += left*(K)*(K+1)//2
  ans %= MOD
  for j in range(i + 1,N):
    if temp <As[j]:
      right += 1
  ans += right*(K)*(K - 1)//2
  ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
def merge(l, r, a):
    l1 = len(l)
    r1 = len(r)
    i,j,k=0,0,0
    while j<l1 and k<r1:
        if l[j]<=r[k]:
            a[i]=l[j]
            j+=1
        else:
            cnt[0] += l1-j
            a[i]=r[k]
            k+=1
        i+=1
    while j<l1:
        a[i]=l[j]
        j+=1
        i+=1
    while k<r1:
        a[i]=r[k]
        k+=1
        i+=1
    return a
def merge_sort(a):
    n = len(a)
    if n==1:
        return a
    else:
        mid = n//2
        left = [0]*mid
        right = [0]*(n-mid)
        for i in range(mid):
            left[i] = a[i]
        for i in range(mid,n):
            right[i-mid]=a[i]
    merge_sort(left)
    merge_sort(right)
    merge(left,right,a)
    return a

n,k = map(int,input().split())
a = list(map(int,input().split()))
cnt = [0,0]
ans4 = 0
a = merge_sort(a)
for i in range(1,n):
    if a[i]==a[i-1]:
        cnt[1]+=1
        if i == n-1:
            ans4+=(1+cnt[1])*cnt[1]//2
    else:
        ans4+=(1+cnt[1])*cnt[1]//2
        cnt[1]=0

ans2 = (n*(n-1))//2 - cnt[0]-ans4
print((cnt[0]*(1+k)*k//2+ans2*k*(k-1)//2)%(10**9+7))

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
inv = lambda w:sum([sum([a[i]>a[j] for j in range(i+1,n)]) for i in range(n-1)])
inv1 = lambda w:sum([sum([a[i]==a[j] for j in range(i+1,n)]) for i in range(n-1)])
ans1 = inv(a)
ans3 = inv1(a)
ans2 = (n*(n-1))//2 - ans1 - ans3
print((ans1*((1+k)*k)//2+ans2*(k*(k-1))//2)%(10**9+7))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import os

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

cnt1 = 0  #Aの中で自分より後ろにある自分より小さい値の個数
cnt2 = 0  #Aの中で自分より小さい値の個数
for i in range(N):
    for j in range(N):
        if A[i] > A[j]:
            cnt2 += 1
            if i < j:
                cnt1 += 1

print((K*cnt1+K*(K-1)*cnt2//2)%mod)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
lists=list(map(int,input().split()))
cnt=0
for i in range(n):
    for j in range(i+1,n):
        if lists[i]>lists[j]:
            cnt+=1
cnt=(cnt*k)%(10**9+7)
additional=0
for some in lists:
    count=0
    for other in lists:
        if some>other:
            count+=1
    additional+=count
    
            

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

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
res1 = 0
res2 = 0
for i in range(0,n):
    res1 += len([sa for sa in a if sa < a[i] ])
    res2 += len([sa for sa in a[i:] if sa < a[i] ])

print((res2 *  k + res1 * k*(k-1) // 2) % (10** 9 + 7))

Submission status: Accepted

Solution code:
n, k = map(int,input().split( ))
a = list(map(int, input().split( )))
lst=[0 for _ in range(2010)]#種類ごとの数
mod = 10**9+7
unit = 0
#print(n,k,*a)
"""
for i in range(n):
    lst[a[i]] += 1
    for j in range(i):
        if a[i] < a[j]:
            #print(a[i],a[j])
            unit += 1
#print(unit)
lst2 = [0 for _ in range(n)]#種類ごとに小さい種類の要素数
for i in range(n):
    for j in range(n):
        if a[i]>a[j]:
            #lst2[i] += lst[a[j]] //lst2[i]=+1か?
"""

"""
新規
"""
unit = 0
multi = 0
for i in range(n):
    for j in range(i+1,n):
        if a[i]>a[j]:
            unit += 1

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

#print(lst[:15])
#print(lst2[:15])
ans = 0
"""
for i in range(n):
    ans += (lst[a[i]] * lst2[i] * (k-1) * k) //2
"""
ans += multi*(k-1)*k//2
    
ans += unit*k

print(ans%mod)

Submission status: Accepted

Solution code:

MOD = 10**9 + 7


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    a0 = 0

    for i in range(N):
        for j in range(i+1, N):
            if A[i] > A[j]:
                a0 += 1
    a1 = 0
    A2 = A * 2
    for i in range(N*2):
        for j in range(i+1, N*2):
            if A2[i] > A2[j]:
                a1 += 1
    a2 = 0
    A3 = A * 3
    for i in range(N*3):
        for j in range(i+1, N*3):
            if A3[i] > A3[j]:
                a2 += 1

    d = (a2 - a1) - (a1 - a0)
    # d * K + a0
    # print(d)
    print((a0 + d * ((K * (K - 1)) // 2) + (K - 1) * a0) % MOD)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
mod=10**9+7

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

s=[0]*N
t=[0]*N

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

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

for i in range(N):
  s[i]=(s[i]*K)%mod
  t[i]=(t[i]*(K-1)*K//2)%mod
#print(s)
#print(t)

print((sum(s)+sum(t))%mod)

Submission status: Accepted

Solution code:
def count_inv(lst):
    ret = 0
    for i in range(len(lst)):
        for j in range(i + 1, len(lst)):
            if lst[i] > lst[j]:
                ret += 1
    return ret


def count_smaller_elements(lst):
    ret = 0
    for i in range(len(lst)):
        for j in range(len(lst)):
            if i != j and lst[i] > lst[j]:
                ret += 1
    return ret


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

    a = count_inv(lst_A)
    num1 = a * K % MOD

    b = count_smaller_elements(lst_A)
    num2 = b * (K * (K - 1) // 2) % MOD

    ans = (num1 + num2) % MOD
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def count_inv(lst):
    ret = 0
    for i in range(len(lst)):
        for j in range(i + 1, len(lst)):
            if lst[i] > lst[j]:
                ret += 1
    return ret


def count_smaller_elements(lst):
    ret = 0
    for i in range(len(lst)):
        tmp = 0
        for j in range(len(lst)):
            if i != j and lst[i] > lst[j]:
                tmp += 1
        ret += tmp
    return ret


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

    a = count_inv(lst_A)
    num1 = a * K % MOD

    b = count_smaller_elements(lst_A)
    num2 = b * (K * (K - 1) // 2) % MOD

    ans = (num1 + num2) % MOD
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N, K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
INF = 10**9+7
ans = 0
for i in range(N):
    B = [1 if a < A[i] else 0 for a in A]
    ans = (ans + sum(B[i+1:])*K + sum(B) * (K*(K-1)//2)) % INF
print(ans)

Submission status: Accepted

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

#(方針)
#1)1回の整数列Aにp箇所大きさの順番が逆になっているところがあれば, 
#p×(1+2+...+K)回の転倒数
#2)1以外で1回目の整数列Aと2回目の整数列にq箇所大きさの順番が逆になっているところがあれば,
#q×(1+2+...+(K-1))回の転倒数
p,q = 0,0
for i in range(N):
  for j in range(N):
    if(i<j):
      if(A[i]>A[j]): p += 1
    if(i>j):
      if(A[i]>A[j]): q += 1

tmp1 = (K*(K+1)//2)%(10**9 +7)
tmp2 = ((K-1)*K//2)%(10**9 +7)
ans = (p*tmp1 + q*tmp2)%(10**9 +7)
print(ans)

Submission status: Accepted

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

for i in range(N):
  for j in range(i,N):
    if i == j:
      pass
    else:
      if A[i] > A[j]:
        tmp += 1
  for k in range(N):
    if A[i] > A[k]:
      tmp2 += 1  
  ans += tmp2*K*(K-1)//2+tmp*K
  ans %= MOD
  tmp = 0
  tmp2 = 0
print(ans)

Submission status: Accepted

Solution code:
n,k = (int(i) for i in input().split())
a = [int(i) for i in input().split()]
b,m,num,mod = sorted(a),0,0,10**9+7
for i in range(1,n):
    if b[i]==b[i-1]: num+=m
    else: num,m = num+i,i
d,ans = [0]*2001,0
def add(i,x):
	while i<=2000:
		d[i] += x
		i += i & -i
def get(i):
	s = 0
	while i:
		s += d[i]
		i -= i & -i
	return s
for i in range(n):
    add(a[i],1)
    ans = (ans-get(a[i])+i+1)%mod
print((ans*k+num*k*(k-1)//2)%mod)

Submission status: Accepted

Solution code:
import bisect
m = 10**9+7
n,k = map(int,input().split())
a = list(map(int,input().split()))
b = sorted(a)
cc = 0
ca = 0
for i in range(n):
  c = 0
  for j in range(i+1,n):
    if a[i] > a[j]:
      c += 1
  cc += c
  ca += bisect.bisect_left(b,a[i])
cc %= m; ca %= m
print(((cc * k) % m + (((((k-1) * k)//2) % m) * ca) % m) % m)

Submission status: Accepted

Solution code:
import bisect
m = 10**9+7
n,k = map(int,input().split())
a = list(map(int,input().split()))
b = sorted(a)
cc = [0] * n
ca = [0] * n
for i in range(n):
  c = 0
  for j in range(i+1,n):
    if a[i] > a[j]:
      c += 1
  cc[i] = c
  ca[i] = bisect.bisect_left(b,a[i])
s = 0
for i in range(n):
  s = ((cc[i]*k)%m + ((k-1)*k*ca[i]//2)%m + s)%m
print(s)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
N,K=map(int,input().split())

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

A=A+A

count=[0]*2*N

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

Submission status: Accepted

Solution code:
a,b=map(int,input().split())
l = list(map(int,input().split()))
dp = [0]*a
ep = [0]*a
s = 0
MOD = 10**9 + 7
for n,x in enumerate(l):
    for m,y in enumerate(l[n+1:]):
        if x > y:dp[n]+=1
    
for n,x in enumerate(l):
    for m,y in enumerate(l[:n]):
        if x > y:ep[n]+=1
for n,x in enumerate(dp):
    ep[n]+=x
# print(dp,ep)

s  = (sum(dp)*b)%MOD
s  += (sum(ep)*(b-1)*b//2)%MOD
print(s%MOD)

Submission status: Accepted

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

cnt=0
a=0

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

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

      
  print(int(cnt*k+a*(k*(k-1)//2))%(10**9+7))

Submission status: Accepted

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

count = 0

for j in range(0,n):
  for i in range(0,n):
    if a[j]>a[i]:
#      print(j,i)
      if j >= i:
        count += (k-1)*k//2
      else:
        count += k*(k+1)//2
#      print(count)
print(count%(10**9+7))

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a_array = [int(x) for x in input().split()]
INF = 10**9+7

cnt_array = [0 for x in range(2000+1)]
a_array2 = []
ans = 0
for a in a_array:
    cnt_array[a] += 1
    a_array2.append(sum(cnt_array[a+1:]))
a_array3 = []
for i in a_array:
    tmp = 0
    for j in a_array[::-1]:
        if j > i:
            tmp += 1
    a_array3.append(tmp)
for cnt, d in zip(a_array2, a_array3):
    ans += (k*(2*cnt+(k-1)*d))//2
    ans = ans % INF
print(ans)

Submission status: Accepted

Solution code:


maxs = 10 ** 9 +7
N, K = [int(x) for x in raw_input().split(' ')]
A = [int(x) for x in raw_input().split(' ')]
B = sorted(A)
l1, l2 = [], []
for i in xrange(N):
    l1.append(len([A[j] for j in range(0, N) if A[j] < A[i]]))
    l2.append(len([A[j] for j in range(i, N) if A[j] < A[i]]))
ans = sum(l1)  * K * (K-1) / 2 + sum(l2) * K
print(ans % maxs)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
n,k = map(int,input().split())
a = list(map(int,input().split()))

ans = 0
adds = 0
mins = 0

for i in range(n):
    for j in range(n):
        if a[i] > a[j]:
            if j < i:
                adds += 1
                mins += 1
            elif i < j:
                adds += 1

ans = (adds*(k+1)*k//2 - mins*k) % 1000000007
print(ans)

Submission status: Accepted

Solution code:
from sys import exit, stderr, stdin
input = stdin.readline
# setrecursionlimit(10**7)

def debug(var, name="hoge"):
    print(name +":" + str(type(var)) + " = " + repr(var), file=stderr)
    return

MOD = 10**9 + 7

def main():
    N, K = [int(n) for n in input().split()]
    A = [int(n) for n in input().split()]
    # 自分未満の数を数える配列を作りたい
    A_und = [0]*N
    for i in range(N):
        for j in range(N):
            if A[i] > A[j]:
                A_und[i] += 1
    # まず自分の中のてんとうを数える
    ans = 0
    for i in range(N):
        for j in range(i+1,N):
            if A[i] > A[j]:
                ans += 1
    ans *= K
    # 最初の列のnはKの回数だけn-1回必ず転倒する次はK-1回,,,
    N_rev = sum(A_und)
    K_time = 0 if K == 1 else max((K-1)*K//2,1)
    ans += N_rev*K_time

    print(ans % MOD)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
la = list(map(int,input().split()))
l1 =[]
l2 =[]
for i in range(0,n):
    l1.append(len([la[j] for j in range(0,n) if la[j]<la[i]]))
    l2.append(len([la[j] for j in range(i,n) if la[j]<la[i]]))
c = k*sum(l2) + (k*(k-1)//2)*sum(l1)
print(c%(10**9 + 7))

Submission status: Accepted

Solution code:
n,K=map(int,input().split())
A=list(map(int,input().split()))
s=0
for i in range(1,n):
    k=i
    while A[k]<A[k-1]:
        A[k],A[k-1]=A[k-1],A[k]
        k-=1
        s+=1
        if k==0:
            break
j=0
l=1
S=0
while j<n-1:
    if A[j]==A[j+1]:
        l+=1
        j+=1
    else:
        S=S+l*(n-1-j)
        l=1
        j+=1
B=int(s*K+(S*K*(K-1))//2)
C=int(s*K)%1000000007
D=(K*(K-1)//2)%1000000007
print((C+S*D)%1000000007)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
T0 = 0
T1 = 0
s = 0
for i in range(N):
  a = A[i]
  T0 = 0
  T1 = 0
  for j in range(i,N):
    if a > A[j]:
      T0 += 1
  for j in range(N):
    if a > A[j]:
      T1 += 1
  s += T1*K*(K-1)//2+T0*K
  s %= 1000000007
print(s)

Submission status: Accepted

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

def main():
    count1 = [0 for _ in range(N)]
    count2 = [0 for _ in range(N)]
    
    # 同じ整数列内での転倒数を数える
    for i, a in enumerate(A[:-1]):
        c = 0
        for b in A[i+1:]:
            if a > b:
                c += 1
        count1[i] = c

    # 異なる整数列に対する転倒数を数える
    for i, a in enumerate(A):
        c = 0
        for b in A[:i]:
            if a > b:
                c += 1
        count2[i] = c + count1[i]

    s = (sum(count1) * K) % MOD
    s += (sum(count2) * (K-1) * K // 2) % MOD
    print(s%MOD)
                
if __name__ == "__main__":
    main()

Submission status: Accepted

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

def get_inv_num(l):
    l=list(l)
    ret=0
    for ind in range(len(l)):
        char=l[ind]
        for s_ind in range(len(l))[ind:]:
            if int(l[s_ind])<int(char):
                ret=ret+1
    return ret

def get_inv_external(l):
    import collections
    l=list(l)
    l_count=collections.Counter(l)
    ret=0
    memo={}
    for num in l:
        if str(num) in memo:
            ret=ret+memo[str(num)]
        else:
            ret_tmp=0
            for suuji in l_count:
                if int(suuji)<int(num):
                    ret_tmp=ret_tmp+l_count[suuji]
            memo[str(num)]=ret_tmp
            ret=ret+ret_tmp
    return ret
internal=get_inv_num(A_list)
external=get_inv_external(A_list)
n,ret=divmod(internal*K+external*(K-1)*K//2,10**9+7)
print(ret)

Submission status: Accepted

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

count_1 = 0
count_2 = 0

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

k = (K-1)*K//2
B = count_1 * K + count_2 * k

print(B%mod)




# mod=10**9+7
# n,k=map(int,input().split())
# arr=list(map(int,input().split()))
#
# cnt1=[0]*n
# cnt2=[0]*n
#
# for i in range(n):
#   for j in range(n):
#     if arr[i]>arr[j]:
#       cnt2[i]+=1
#       if i<j:
#         cnt1[i]+=1
#
# ans=0
# for val in cnt1:
#   ans+=val*k
#   ans%=mod
# for val in cnt2:
#   ans+=val*(k*(k-1)//2)
#   ans%=mod
# print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import numpy as np
input = sys.stdin.readline

def main():
    N, K = map(int, input().split())
    a = list(map(int, input().split()))

    MOD = int(1e9) + 7
    left = [0] * N
    right = [0] * N
    for i in range(N):
        for j in range(i):
            if a[j] < a[i]:
                left[i] += 1
        for j in range(i, N):
            if a[j] < a[i]:
                right[i] += 1
    # print(left)
    # print(right)
    ans = 0
    for i in range(N):
        start = (left[i] + right[i]) * (K - 1) + right[i]
        end = right[i]
        ans += ((start + end) * K) // 2
        ans %= MOD
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import collections

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

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

vs = dict(collections.Counter(sorted(A)))
acc = 0

c = N
for i, (k, v) in enumerate(vs.items()):
    c -= v
    acc += v * c
tento += acc * (K * (K - 1) // 2)

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

Submission status: Accepted

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

Submission status: Accepted

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

l = []
for i in range(n):
    l.append([0, 0])
    for j in range(n):
        if (j < i and a[j] < a[i]):
            l[i][0] += 1
        if (j > i and a[j] < a[i]):
            l[i][1] += 1

s = 0
for i in range(n):
     s += int(l[i][0] * k * (k - 1) // 2)
     s += int(l[i][1] * k * (k + 1) // 2)
     s = int(s % (1000000007))

print(s)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
mod,ans = 1000000007,0
a = list(map(int,input().split()))
for i in range(len(a)):
    tmps,tmpt = 0,0
    for j in range(i):
        if a[i] > a[j]:
            tmpt+=1
    for j in range(i+1,len(a)):
        if a[i] > a[j]:
            tmps+=1
    ans = (ans%mod + k*tmps%mod + (k-1)*(k)%mod * (tmpt+tmps)%mod*500000004%mod)%mod
print(ans)

Submission status: Accepted

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


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    cnt = [0] * 2001
    used = [0] * 2001
    for a in A:
        cnt[a] += 1
    ans = 0
    for a in A:
        c = 0
        u = 0
        for i in range(1, a):
            c += cnt[i]
            u += used[i]
        begin = c * K - u
        last = c - u
        tmp = (begin + last) * K // 2
        ans = (ans + tmp) % MOD
        used[a] += 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from collections import *
import math
from bisect import *
import functools
INF = float('inf')
mod = 10**9+7

class BIT:
    def __init__(self, N):
        self.N = N
        self.bit = [0 for _ in range(N+1)]
    def add(self, x, a):
        while x <= self.N:
            self.bit[x] += a
            x += x & -x
    def sum(self, x):
        ret = 0
        while x != 0:
            ret += self.bit[x]
            x -= x & -x
        return ret

N, K = map(int, input().split())
A = [int(x) for x in input().split()]
bit = BIT(2001)
cnt = 0
for a in A:
    cnt += bit.sum(2000)-bit.sum(a)
    bit.add(a, 1)
X = 0
for a in A:
    X += bit.sum(a-1)
print((cnt*K+X*(K-1)*K//2)%mod)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
def counter_one(A):
    cnt = 0
    for i,ai in enumerate(A):
        cnt += sum(a < ai for a in A[i+1:])
    return cnt
def counter_two(A):
    cnt = 0
    for i,ai in enumerate(A):
        cnt += sum(a < ai for a in A)
    return cnt
  

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

one_a = counter_one(A)
two_a = counter_two(A)

ans = (one_a*K)+((two_a)*(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

x, y = 0, 0

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

ans = x * K * (K+1) // 2 + y * (K-1) * K // 2

print(ans % mod)