Problem:


Score : 300 points

Problem Statement

We have a sequence of N integers A~=~A_0,~A_1,~...,~A_{N - 1}.

Let B be a sequence of K \times N integers obtained by concatenating K copies of A. For example, if A~=~1,~3,~2 and K~=~2, B~=~1,~3,~2,~1,~3,~2.

Find the inversion number of B, modulo 10^9 + 7.

Here the inversion number of B is defined as the number of ordered pairs of integers (i,~j)~(0 \leq i < j \leq K \times N - 1) such that  B_i > B_j.

Constraints

All values in input are integers.

1 \leq N \leq 2000

1 \leq K \leq 10^9

1 \leq A_i \leq 2000

Input

Input is given from Standard Input in the following format:

N K
A_0 A_1 ... A_{N - 1}

Output

Print the inversion number of B, modulo 10^9 + 7.

Sample Input 1

2 2
2 1

Sample Output 1

3

In this case, B~=~2,~1,~2,~1. We have:

B_0 > B_1

B_0 > B_3

B_2 > B_3

Thus, the inversion number of B is 3.

Sample Input 2

3 5
1 1 1

Sample Output 2

0

A may contain multiple occurrences of the same number.

Sample Input 3

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

Sample Output 3

185297239

Be sure to print the output modulo 10^9 + 7.



Sample input:
2 2
2 1


Sample output:
3

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
 
mod = 10 ** 9 + 7
# 配列内で自身より小さい数の個数　前後別に求める
b = [[0, 0] for _ in range(n)]
for i in range(n):
    for j  in range(i,n):
        if a[i] > a[j]:
                b[i][1] += 1
        elif a[i] < a[j]:
        		b[i][0] +=1


b[i][0]=b[i][0]%mod		
b[i][1]=b[i][1]%mod	
ans = 0
sigmakp = ((k * (k+1) ) // 2) % mod
sigmakp = int(sigmakp)
sigmakn = ((k * (k-1)) // 2) % mod
sigmakn = int(sigmakn)
for i in range(n):
    mae = int(sigmakn * b[i][0]) % mod
    ushiro = int(sigmakp * b[i][1]) % mod
    ans = int((mae + ushiro) + ans) % mod 
print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
 
mod = 10 ** 9 + 7
k = k % mod
# 配列内で自身より小さい数の個数　前後別に求める
b = [[0, 0] for _ in range(n)]
for i in range(n):
    for j in range(n):
        if a[i] > a[j]:
            if i > j:
                b[i][0] += 1
            elif i < j:
                b[i][1] += 1
    b[i][0] = b[i][0] % mod
    b[i][1] = b[i][1] % mod
ans = 0
# kまでの和　後ろの数用
sigmakp = ((k * (k+1)) // 2) % mod
sigmakp = int(sigmakp)
# k-1までの和　前の数用
sigmakn = ((k * (k-1)) // 2) % mod
sigmakn = int(sigmakn)
 
for i in range(n):
    mae = (sigmakp * b[i][1]) % mod
    ushiro = (sigmakn * b[i][0]) % mod
    ans = ((mae + ushiro) % mod + ans) % mod 
print(ans)

Submission status: Accepted

Solution code:
n,k,*a=map(int,open(0).read().split())
print(sum(k*~-k//2*(c<d)+k*-~k//2*(c>d)for i,c in enumerate(a)for d in a[i:])%(10**9+7))

Submission status: Accepted

Solution code:
n,k,*a=map(int,open(0).read().split())
l=k*~-k//2
print(sum(l*(c<d)+(l+k)*(c>d)for i,c in enumerate(a)for d in a[i:])%(10**9+7))

Submission status: Accepted

Solution code:
n,k,*a=map(int,open(0).read().split())
l=k*~-k//2
s=0
for i,c in enumerate(a):
 for d in a[i:]:s+=l*(c<d)+(l+k)*(c>d)
print(s%(10**9+7))

Submission status: Accepted

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

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

mod=10**9 +7
count=0
for i in range(N):
  for j in range(i+1, N):
    if A[i]>A[j]:
      count+=K
  for k in range(N):
    if A[i]>A[k]:
      count+=(K-1)*K//2
  

print(int(count%mod))

Submission status: Accepted

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

for i in range(0, N):
    for j in range(0,i):
        if A[j] > A[i]:
            numc += 1
        if A[i] > A[j]:
            numf += 1
numbers = numc*K*(K+1) + numf*K*(K-1)
 
ans = int(numbers//2 % (10**9 + 7))
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
r = list(map(int, input().split()))
n_cnt = 0
g_cnt = 0
for n in range(N):
  for i in range(N):
    if i > n and r[n] > r[i]:
      n_cnt += 1
    if r[n] > r[i]:
      g_cnt += 1
ans = ((n_cnt * K) + (g_cnt * ((K - 1) * K // 2))) % (10**9 + 7)
print(ans)

Submission status: Accepted

Solution code:
from itertools import groupby

R = lambda: map(int, input().split())
n, k = R()
a = list(R())
w = [0] * n

def merge(b, e):
    mid = b + (e - b) // 2
    in1, in2 = b, mid
    out = 0
    r = 0
    while in1 < mid and in2 < e:
        if a[in1] <= a[in2]:
            w[out] = a[in1]
            in1 += 1
        else:
            r += mid - in1
            w[out] = a[in2]
            in2 += 1
        out += 1
    a[e - mid + in1: e] = a[in1: mid]
    a[b: b + out] = w[:out]
    return r        
    
def mergesort(b, e):
    if e - b < 2:
        return 0
    mid = b + (e - b) // 2
    return mergesort(b, mid) + mergesort(mid, e) + merge(b, e)


r = k * mergesort(0, n)
c = n * (n - 1) // 2
for _, g in groupby(a):
    x = sum(1 for _ in g)
    c -= x * (x - 1) // 2
print((r + c * k * (k - 1) // 2) % (10**9 + 7))

Submission status: Accepted

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

rn_0 , rn_2 = 0, 0

for i in range(n-1):
  for j in range(i+1, n):
    if l[i] > l[j]:
      rn_0 += 1

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

rn_0 *= k*(k+1)//2
rn_2 *= k*(k-1)//2

rn = (rn_0 % (10**9+7)) + (rn_2 % (10**9+7))
print(rn%(10**9+7))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import copy

def j(n):
    if n:print("Yes")
    else:print("No")
    exit(0)
rem = 10 ** 9 + 7

"""
def ct(x,y):
    if (x>y):print("+")
    elif (x<y): print("-")
    else: print("?")
"""

def ip():
    return int(input())
def iprow():
    return [int(i) for i in input().split()]
def ips():
    return (int(i) for i in input().split())
def printrow(a):
    for i in a:
        print(i)
s = 0
n,r =ips()
a = iprow()
other=0
for i in range(n):
    for k in range(n):
        if a[i]>a[k] and i<k:
            s+=1
        elif i>k and a[i]>a[k]:
            other+=1
adder = 0
rate = s
ans = 0
ans =((s + (s * r)) * r)//2 + ((other + other*(r-1)) * (r-1))//2
print(ans%rem)

Submission status: Accepted

Solution code:
import numpy as np
import random
import sys
from functools import lru_cache

def main(n,k,a):

    mod = 10**9 + 7
    c1,c2 = 0,0
    for i in range(len(a)):
        for j in range(len(a)):
            # print('--- ---', i,j)
            if a[i] > a[j]:
                
                if i < j:
                    c1 += 1

                elif i > j:
                    c2 += 1
        
        count = (c1*k*(k+1)//2 + c2*k*(k-1)//2)%mod

    print(count)


if __name__ == '__main__':
    n,k = map(int,input().split(' '))
    a = list(map(int, input().split(' ')))
    main(n,k,a)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from collections import Counter
R = lambda: map(int, input().split())
n, k = R()
a = list(R())
r = sum(k for i in range(n) for j in range(i) if a[i] < a[j])
r += k*(k-1)//2 * (n*(n-1)//2 - sum(x*(x-1)//2 for x in Counter(a).values()))
print(r % (10**9 + 7))

Submission status: Accepted

Solution code:

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

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

    count = 0
    count_ = 0
    # 内部
    for j in range(N-1):
        for i in range(j+1, N):
            if A[j] > A[i]:
                count += K*(K+1)//2
    
    # 異なるK間の個数
    B = list(reversed(A))
    for l in range(N-1):
        for m in range(l+1,N):
            if B[l] > B[m]:
                count += K*(K-1)//2

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter
R = lambda: map(int, input().split())
n, k = R()
a = list(R())
r = k * sum(a[i] < a[j] for i in range(n) for j in range(i))
r += k*(k-1)//2 * (n*(n-1)//2 - sum(x*(x-1)//2 for x in Counter(a).values()))
print(r % (10**9 + 7))

Submission status: Accepted

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

#1つの箱の中の数を数える
cnt1=0
for i in range(n):
    for j in range(i,n):
        if A[i]>A[j]:
            cnt1+=1

#2つの箱の大小を調べる
B=A
cnt2=0
for i in range(n):
    for j in range(n):
        if B[i]>A[j]:
            cnt2+=1
ans = (cnt1*k + cnt2 * k*(k-1)//2)%(10**9+7)
print(ans)

Submission status: Accepted

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

ans=f*K
tmp=((K-1)*K)//2
ans+=b*tmp
#ans = K * f + (b * K * (K - 1)) // 2
ans%=mod

print(int(ans))

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
A = list(map(int,input().split()))
inner_count=0
other_count=0
for i in range(n):
  for j in range(n):
    if i==j or i>j:
      pass
    else:
      if A[i]>A[j]:
        inner_count+=1
for x in range(n):
  for y in range(n):
    if A[x]>A[y]:
      other_count+=1
inner_count = inner_count*k
other_count = other_count*(k*(k-1)//2)
print((inner_count+other_count)%(10**9+7))

Submission status: Accepted

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

r=list(map(int,input().split()))
MOD = 10**9+7
i=0
tentou=0
while i<n-1:
  j=i+1
  while j<n:
    if r[i]>r[j]:tentou+=1
    j=j+1
  i=i+1

tentou2=0
i=0
while i<n:
  j=0
  while j<n:
    if r[j]>r[i]:tentou2+=1
    j=j+1
  i=i+1

#print(tentou,tentou2)

temp1=(tentou*k)
#temp2=((tentou2*k*(k-1))/2)
temp3=((tentou2*k*(k-1))//2)
#print(temp2%MOD,temp3%MOD)
#浮動小数点型にしてはでかすぎるのでtemp2は近似値となってしまっている
print((temp1+temp3)% MOD)

Submission status: Accepted

Solution code:
from collections import Counter
R = lambda: map(int, input().split())
n, k = R()
a = list(R())
r = k * sum(a[i] < a[j] for i in range(n) for j in range(i))
r = n*(n-1)//2 - sum(x*(x-1)//2 for x in Counter(a).values())
r = r * k*(k-1)//2 + k * sum(a[i] < a[j] for i in range(n) for j in range(i))
print(r % (10**9 + 7))

Submission status: Accepted

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

#ans=f*K
#tmp=((K-1)*K)%mod
#ans+=((b*tmp)//2)%mod
ans = K * f + (b * K * (K - 1)) // 2
ans%=mod

print(ans)

Submission status: Accepted

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

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

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

# print(count1)
# print(count2)

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
data = input().split(" ")
n = int(data[0])
k = int(data[1]) 
a = list(map(int, input().split(" ")))
left = 0
right = 0
for i in range(0, n):
	for j in range(0, i):
		if a[j] < a[i]:
			left += 1
	for j in range(i+1, n):
		if a[j] < a[i]:
			right += 1

rt = ((k + 1) * k // 2) % 1000000007
lt = ((k - 1) * k // 2) % 1000000007
ans = (right * rt + left * lt) % 1000000007
print(ans)

Submission status: Accepted

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

x = 0
for l in range(N-1):
    for r in range(l+1, N):
        if A[l] > A[r]:
            x += 1
count = K * 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

# K_C_2 K個の中から2個選ぶ
count += K * (K - 1) // 2 * y

mod = 10 ** 9 + 7
result = int(count % mod)
print(result)

Submission status: Accepted

Solution code:
import numpy as np
n, k = map(int, input().split())
a = list(map(int, input().split()))
num = [[0, 0] for _ in range(n)]
for i in range(n):
    for j in range(n):
        if a[i] > a[j]:
            num[i][1] += 1
        if (i < j) and (a[i] > a[j]):
            num[i][0] += 1
num_np = np.array(num)
ks = k * (k - 1) // 2 % 1000000007
sum_left = sum(num_np[:,0])
sum_right = sum(num_np[:,1])
output = (sum_left * k) % 1000000007 + (sum_right * ks) % 1000000007
print(output % 1000000007)

Submission status: Accepted

Solution code:
from sys import stdin
n,k = map(int,stdin.readline().rstrip().split())
li = list(map(int,stdin.readline().rstrip().split()))
nai = 0
ato = 0
point = 0
for i in range(n):
    for s in range(i+1,n):
        if li[i] > li[s]:
            nai += 1
    for v in range(n):
        if li[i] > li[v]:
            ato += 1
point += (nai*k)+(ato*k*(k-1)//2)
print(point%(10**9+7))

Submission status: Accepted

Solution code:
# coding: utf-8

import sys
import math
import collections
import itertools
def input(): return sys.stdin.readline().strip()
def gcd(x, y): return y if x % y == 0 else gcd(y, x % y)
def lcm(x, y): return (x * y) // gcd(x, y)
MOD = 10 **9 + 7

# N = int(input())
# S = input()
N, K = map(int, input().split())
# 横
A = [int(x) for x in input().split()]
# 縦
# A = [int(input()) for _ in range(N)]
# 多次元
# L = [[int(x) for x in input().split()] for _ in range(N)]

ans = 0
tmp = 0

for i, a in enumerate(A) :
    for aa in range(i + 1, N) :
        if a > A[aa] :
            ans += 1

for a in A :
    for aa in A :
        if a > aa :
            tmp += 1

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

print(ans)

Submission status: Accepted

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

count = 0
for i in range(n):
    for j in range(n-i-1):
        jj = j+1+i
        if la[i] > la[jj]:
            count += 1

count2 = 0
laa = sorted(la)
for i in range(n):
    for j in range(n-i-1):
        jj = j+1+i
      
        if laa[i] < laa[jj]:
            count2 += 1

a = count * k
b = count2 * (((k-1)*k)//2)
result = int(a)+int(b)

print(result%(pow(10,9)+7))

Submission status: Accepted

Solution code:
# coding: utf-8

import sys
import math
import collections
import itertools
def input(): return sys.stdin.readline().strip()
def gcd(x, y): return y if x % y == 0 else gcd(y, x % y)
def lcm(x, y): return (x * y) // gcd(x, y)
MOD = 10 **9 + 7

# N = int(input())
# S = input()
N, K = map(int, input().split())
# 横
A = [int(x) for x in input().split()]
# 縦
# A = [int(input()) for _ in range(N)]
# 多次元
# L = [[int(x) for x in input().split()] for _ in range(N)]

ans = 0
tmp = 0

for i, a in enumerate(A) :
    for aa in range(i + 1, N) :
        if a > A[aa] :
            ans += 1

for a in A :
    for aa in A :
        if a > aa :
            tmp += 1

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

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8

import sys
import math
import collections
import itertools
def input(): return sys.stdin.readline().strip()
def gcd(x, y): return y if x % y == 0 else gcd(y, x % y)
def lcm(x, y): return (x * y) // gcd(x, y)
MOD = 10 **9 + 7

# N = int(input())
# S = input()
N, K = map(int, input().split())
# 横
A = [int(x) for x in input().split()]
# 縦
# A = [int(input()) for _ in range(N)]
# 多次元
# L = [[int(x) for x in input().split()] for _ in range(N)]

ans = 0
tmp = 0

for i, a in enumerate(A) :
    for aa in range(i + 1, N) :
        if a > A[aa] :
            ans += 1

for a in A :
    for aa in A :
        if a > aa :
            tmp += 1

print(((int((K*(K-1))//2)%MOD)*tmp+ans*K)%MOD)

Submission status: Accepted

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

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 += k*(k+1)//2

b = list(reversed(a))
for l in range(n-1):
  for m in range(l+1,n):
    if b[l] > b[m]:
      cnt += (k-1)*k//2
      
x = 10**9 + 7
print(int(cnt%x))

Submission status: Accepted

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

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

cnt2 = 0
for l in range(n):
  for m in range(n):
    if a[l] > a[m]:
      cnt2 += 1
cnt2 = cnt2*k*(k-1)//2

cnt = cnt1 + cnt2

x = 10**9 + 7
print(int(cnt%x))

Submission status: Accepted

Solution code:
import numpy as np
n, k = map(int, input().split())
a = list(map(int, input().split()))
x, y = 0, 0
for i in range(n):
    for j in range(n):
        if a[i] > a[j]:
            x += 1
        if (i < j) and (a[i] > a[j]):
            y += 1

output = ((x * k * (k - 1) // 2) + (y * k)) % 1000000007
print(output)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
#N,K = map(int,'10 998244353'.split())
#N,K = map(int,'10 2'.split())
Alist = list(map(int,input().split()))
#Alist = list(map(int,'10 9 8 7 5 6 3 4 2 1'.split()))
beforeTnumber = [0]*N
afterTnumber = [0]*N
beforesum = 0
aftersum = 0
mod_num = 10**9+7

for now in range(N):
    for before in range(now):
        if Alist[before] < Alist[now]:
            beforeTnumber[now] += 1
    for after in range(now,N):
        if Alist[after] < Alist[now]:
            afterTnumber[now] += 1
            
beforesum = sum(beforeTnumber)
aftersum = sum(afterTnumber)

Kaftersum = ((K*(K+1))//2)%mod_num
Kbeforesum = ((K*(K-1))//2)%mod_num

print(int(((aftersum)*(Kaftersum)+(beforesum*Kbeforesum))%mod_num))

Submission status: Accepted

Solution code:
import math, string, itertools, fractions, heapq, collections, re, \
array, bisect, sys, random, time, copy, functools, os, queue, pdb
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)

N, K = LI()
A = LI()

from fractions import Fraction
"""
2 1なら
2 1 2 1
点灯数は、左の数のほうが多いもの
2 1
2 1
2 1
の3種類
2回つなげてみたら決まる
2 1 2 1なら
K = 2で3
K=3 で 2 1 2 1 2 1で6
K=4 で2 1 2 1 2 1 2 1で10通り 4+3+2+1=
K=6なら 2 1 2 1 2 1 2 1 2 1 2 1で6+5+4+3+2+1 =

偶奇でわける
modで割る

1 2なら
1 2 1 2で1しかない1
1 2 1 2 1 2なら3で2 + 1
1 2 1 2 1 2 1 2 なら6で3+2+1
"""
if len(set(A)) == 1:
    print(0)
    exit()

"""
各数字ごとに数える
"""
K %= mod
in_count = 0
for i in range(N):
    for j in range(i, N):
        if A[i] > A[j]:
            #  print('i, j', i,j, A[i], A[j])
            in_count += 1
#  print(in_count)
in_count %= mod
in_ans = in_count * K
in_ans %= mod

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

out_count %= mod
#  out_ans = (out_count * K * (K-1))//2
#  out_ans = out_count * (((K * (K-1))%mod)/2) % mod
out_ans = int(Fraction(out_count) * Fraction(K) * Fraction(K-1) / Fraction(2))
out_ans %= mod
#  print(in_ans, out_ans)
print(int((in_ans + out_ans)%mod))

Submission status: Accepted

Solution code:
N,K = map(int, input().split())
A = list(map(int,input().split()))
 
def souwa(num):
    if num % 2 == 0:
        return int((num+1) * (num/2))
    else:
        return int((num+1) * (num//2)) + ((num//2)+1)
 
ans = 0
for i in range(N):
    buf1 = sum(A[i] > A[j] for j in range(i+1, N))
    buf2 = sum(A[i] > a for a in A)
    ans += (buf1 * K) + (buf2 * (K*(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()))

def souwa(num):
    if num % 2 == 0:
        return int((num+1) * (num/2))
    else:
        return int((num+1) * (num//2)) + ((num//2)+1)

ans = 0
buf1 = 0
buf2 = 0
for i in range(N):
    buf1 += sum(A[i] > A[j] for j in range(i+1, N))
    buf2 += sum(A[i] > a for a in A)

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

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
la = list(map(int, input().split()))
mod = pow(10,9)+7

c = 0
for i in range(n):
    for j in range(n-i-1):
        jj = j+1+i
        if la[i] > la[jj]:
            c += 1

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

a = c*k
b = c2*((k*(k-1))//2)


print((a+b)%mod)

Submission status: Accepted

Solution code:
DIV = 10**9 + 7
n, k = map(int, input().split())
li = list(map(int, input().split()))
x, y = 0, 0

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

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

print(((x * k) + (y * ((k * (k - 1) // 2)))) % DIV)

Submission status: Accepted

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

l=[]
l2=[]
for i in range(n):
    temp=0
    temp2=0
    for j in range(n):
        if a[i]>a[j]:
            if i<j:
                temp2+=1
            temp+=1
    l.append(temp)
    l2.append(temp2)
ans=0
for i in range(n):
    ans=(ans+k*l2[i]+(((k-1)*k*l[i]))//2)%(10**9+7)
print(ans)

Submission status: Accepted

Solution code:
M = 10**9+7
import sys
input = sys.stdin.readline

from decimal import *   #通常の割り算が正確に計算できるのは4*10**16までらしい。float型のため

N,K = map(int, input().split())
A = list(map(int, input().split()))
A_ = sorted(A, reverse = True)
ans = 0
ans_ = 0
for i in range(0,N-1):
        for j in range(i+1,N):
            if A[i] > A[j]:
                ans += 1
            if A_[i] > A_[j]:
                ans_ += 1

print(((int(Decimal(K*(K-1)) / Decimal(2))%M)*ans_+ans*K)%M)

Submission status: Accepted

Solution code:
from sys import stdin
import math
import fractions
from collections import deque
from collections import Counter
import itertools
 
INF = 10 ** 10
 
MOD = 10**9 + 7
 
N, K = [int(x) for x in stdin.readline().rstrip().split()]
A = [int(x) for x in stdin.readline().rstrip().split()]
 
 
cnt = 0
 
for i in range(N):
    for j in range(i+1, N):
        if A[i] > A[j]:
            cnt += 1

if K >= 2:
    cnt = cnt * K
 
cnt2 = 0
 
if K >= 2:
    for i in range(N):
        for j in range(N):
            if A[i] > A[j]:
                cnt2 += 1
 
    tmp = ((K) * (K-1)) // 2
 
    cnt2 = cnt2 * tmp
 
cnt = (cnt + cnt2) % MOD
 
print(cnt)

Submission status: Accepted

Solution code:
def tasu(a):
  out = (a*(a-1))//2 + a
  return out%(10**9 + 7)
    
  
N, K = map(int, input().split())
A_list = list(map(int, input().split()))
count = 0
count1 = 0

for i in range(N):
  for j in range(N):
    if i == j:
      continue
    elif (i<j) & (A_list[i] > A_list[j]):
      count += 1
    elif (i>j) & (A_list[i] > A_list[j]):
      count1 += 1

ans = (tasu(K) * count) + (tasu(K-1) * count1) 
print(ans%(10**9 + 7))

Submission status: Accepted

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

leftCount = 0
rightCount = 0
mod = 10**9 + 7

for i in range(n):
    for j in range(n):
        if arr[i] > arr[j]:
            if i < j:
                rightCount +=1
            else:
                leftCount +=1
leftCount = leftCount*k*(k-1)//2
rightCount = rightCount*k*(k+1)//2
count = (leftCount % mod) + (rightCount % mod)
count %= mod
print(count)

Submission status: Accepted

Solution code:
N,K=(input().split())
N,K=int(N),int(K)
seq=list(input().split())
seq=[int(x) for x in seq]
cou=0
C=0
inc=0
for i in range(len(seq)):
    for j in range(i+1,len(seq)):
        if seq[i]>seq[j]: cou+=1
for i in range(len(seq)):
    for j in range(len(seq)):
        if seq[i]>seq[j]: inc+=1
C=(K*(K-1)//2)*inc+K*cou
print(C%(10**9+7))

Submission status: Accepted

Solution code:
import math, string, itertools, fractions, heapq, collections, re, \
array, bisect, sys, random, time, copy, functools, os, queue, pdb
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)

N, K = LI()
A = LI()

"""
2 1なら
2 1 2 1
点灯数は、左の数のほうが多いもの
2 1
2 1
2 1
の3種類
2回つなげてみたら決まる
2 1 2 1なら
K = 2で3
K=3 で 2 1 2 1 2 1で6
K=4 で2 1 2 1 2 1 2 1で10通り 4+3+2+1=
K=6なら 2 1 2 1 2 1 2 1 2 1 2 1で6+5+4+3+2+1 = 

偶奇でわける
modで割る

1 2なら
1 2 1 2で1しかない1
1 2 1 2 1 2なら3で2 + 1
1 2 1 2 1 2 1 2 なら6で3+2+1
"""
if len(set(A)) == 1:
    print(0)
    exit()

"""
各数字ごとに数える
"""
K %= mod
in_count = 0
for i in range(N):
    for j in range(i, N):
        if A[i] > A[j]:
            #  print('i, j', i,j, A[i], A[j])
            in_count += 1
#  print(in_count)
in_count %= mod
in_ans = in_count * K
in_ans %= mod

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

out_count %= mod
out_ans = (out_count * K * (K-1))//2
out_ans %= mod
#  print(in_ans, out_ans)
print(int((in_ans + out_ans)%mod))

Submission status: Accepted

Solution code:
M = 10**9+7
import sys
input = sys.stdin.readline

N,K = map(int, input().split())
A = list(map(int, input().split()))
A_ = sorted(A, reverse = True)
ans = 0
ans_ = 0
for i in range(0,N-1):
        for j in range(i+1,N):
            if A[i] > A[j]:
                ans += 1
            if A_[i] > A_[j]:
                ans_ += 1

print(((int((K*(K-1))//2)%M)*ans_+ans*K)%M)

Submission status: Accepted

Solution code:
MAX = 10**9 + 7
_, K = map(int, input().split())
a = list(map(int, input().split()))
s = [sum([b > c for c in a]) for b in a]
r = [sum([b > c for c in a[i:]]) for i, b in enumerate(a)]
b = sum(s)*(K-1)*K//2%MAX
print((b+sum(r)*K)%MAX)

Submission status: Accepted

Solution code:
N,K= list(map(int, input().split()))
A= list(map(int, input().split()))
AA=sorted(A)
num=0
for i in A:
    num+=AA.index(i)
num2=0
for i in range(N-1):
    for j in range(i+1,N):
        if A[i]>A[j]:
            num2+=1
hoge=(K-1)*K//2%1000000007
hoge=hoge*num%1000000007
hoge2=num2*K%1000000007
hoge=(hoge+hoge2)%1000000007
print(hoge)

Submission status: Accepted

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

A = list(map(int, input().split()))
AA = []
for i in range(2):
    AA.extend(A)

x = 0
for i in range(N):
    for j in range(i+1, N):
        if A[j] < A[i]:
            x += 1
M = 10**9 + 7

y = 0
NN = N*2
for i in range(NN):
    for j in range(i+1, NN):
        if AA[j] < AA[i]:
            y += 1

a = (K*x)
b = (y - 2*x) * (K*(K-1)//2)
ans = ((a+b)  % M)
print(int(ans))

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
l=list(map(int,input().split()))
A=sorted(l)
x=[];d=[]
m=10**9+7
for i in range(n):
  ct=0
  for j in range(i+1,n):
    if l[i]>l[j]:ct+=1
  x.append(ct)
for i in range(n):
  d.append(A.index(l[i]))
ans=0
for i in range(n):
  ans+=((k*(2*x[i]+(k-1)*d[i]))//2)%m
print(ans%m)

Submission status: Accepted

Solution code:
def main():
    n, k = (int(i) for i in input().split())
    a = [int(i) for i in input().split()]
    MOD = 10**9 + 7
    ans = 0
    alpha = 0
    for i in range(n):
        for j in range(i+1,n):
            if a[i] > a[j]:
                alpha += 1
    ans = ans + (alpha * k)%MOD

    beta = 0
    for i in range(n):
        for j in range(n):
            if a[i] > a[j]:
                beta += 1
    ans = ans + (((k*(k-1)) // 2) * (beta) ) %MOD
    ans = ans % MOD
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, K = [int(x) for x in input().strip().split()]
A = [int(x) for x in input().strip().split()]
T_A = 0
T_A_all = 0
for i,a in enumerate(A):
    T_A += len([1 for x in A[i+1:] if a > x])
    T_A_all += len([1 for x in A if a > x])
a = T_A
z = T_A + T_A_all * (K -1)
print(int((K*(a+z)//2)%((10**9)+7)))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, K = [int(x) for x in input().strip().split()]
A = [int(x) for x in input().strip().split()]
T_A = 0
T_A_all = 0
for i,a in enumerate(A):
    T_A += len([1 for x in A[i+1:] if a > x])
    T_A_all += len([1 for x in A if a > x])
a = T_A
z = T_A + T_A_all * (K -1)
print(int((T_A*K+T_A_all*K*(K-1)//2)%((10**9)+7)))

Submission status: Accepted

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


li = []

for i in range(n):
    count=0
    for j in range(n):
        if List[i]>List[j]:
            count += 1
    li.append(count)

count2=0

for i in range(1,n):
    for j in range(i+1,n+1):
        if int(List[i-1]) > int(List[j-1]):
            count2 += 1

counted = k*count2 + (sum(li))*k*(k-1)//2

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

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
x=0
for i in range(n-1):
    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 + y*k*(k-1)//2
print(ans%(10**9+7))

Submission status: Accepted

Solution code:
N,K = input().split()
N = int(N)
K = int(K)
mod = 1000000007
ans =0

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

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


firstcnt =  firstcnt % mod
seccnt = seccnt % mod

a = (firstcnt*K)%mod
c = ((K-1)*K//2)%mod
b = (seccnt * c)%mod

ans = a + b
ans = ans % mod

print(int(ans))