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()))

C = [0] * (max(A)+1)
a1 = 0
a2 = 0

for i in range(n):
    C[A[i]] += 1
    a2 += sum(C[A[i]+1:])
for i in range(n):
    a1 += sum(C[A[i]+1:])

a1 %= mod
a2 %= mod
#print(a1*0.5*n*(n-1))
k %= mod

if k % 2 == 0:
    kk = [k//2, k-1]
else:
    kk = [k, (k-1)//2]

ans = 0
ans += a2*k % mod
ans2 = a1*kk[0] % mod
ans2 *= kk[1] % mod
ans += ans2 % mod

print(int(ans % mod))

Submission status: Accepted

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

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

tmp1 = 0
tmp2 = 0

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

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

ans = (tmp1 * (K)) + ((K * ((K - 1)) // 2) * tmp2)
print(ans % INF)

Submission status: Accepted

Solution code:
import numpy as np

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

l = 0
r = 0
for i in range(N):
    for j in range(N):
        if Alist[i] > Alist[j]:
            if i < j:
                r += 1
            if i > j:
                l += 1

Kl = int((K * (K - 1) // 2) % MOD)
Kr = int((K * (K + 1) // 2) % MOD)
ans = (l * Kl + r * Kr) % MOD

print(ans)

Submission status: Accepted

Solution code:
# B _再提出
n, k = map(int, input().split())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7

naibu = 0
for i in range(n):
    for j in range(i+1, n):
        if A[i] > A[j]:
            naibu += 1
gaibu = 0
A2 = A
for i in range(n):
    for j in range(n):
        if A[i] > A2[j]:
            gaibu += 1

total = naibu*k + gaibu*(k*(k-1)//2)
print(total%mod)

Submission status: Accepted

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


diff = []
npA = np.array(A)
lenA = len(A)
for a in A:
    temp = list(np.array([a for i in range(lenA)]) - npA)
    diff.append(temp)

D = np.array(diff)

upD = np.triu(D,k=1)

upC = np.count_nonzero(upD>0)
dwC = np.count_nonzero(upD<0)

ans = (K*(K+1)//2)*upC + ((K-1)*K//2)*dwC
print(ans%(1000000007))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)

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

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

MOD = pow(10,9) + 7

p = 0

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


ans = int(c * k % MOD) + int( (k *(k-1)//2) % MOD * d)
ans = int(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

H = [[b < a for b in A[:i]].count(True) for i, a in enumerate(A)]  # hukkisuu
T = [[b < a for b in A[i+1:]].count(True) for i, a in enumerate(A)]  # tentousuu

print(sum(h*K*(K-1)//2 + t*K*(K+1)//2 for h, t in zip(H, T)) % MOD)

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

cnt=(x*k)+(k*(k-1)//2*y)
print(cnt%mod)

Submission status: Accepted

Solution code:
import math

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

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

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

cnt = cnt_1 * K + cnt_2 * ((K-1)*K//2)

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

Submission status: Accepted

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

cna=0
for i,a in enumerate(A):
    for at in A[i+1:]:    
        if a>at:
            cna+=1

cna2=0
for a in A:
    for at in A:    
        if a>at:
            cna2+=1


kt=(K-1)*(K)//2

#kt=int((K-1)*(K)/2)
#the expression gives a bit different value
#because double precision can deal with the number till 2**53
#due to the memory is 52 bit for expression besides exponetial


print((K*cna+kt*cna2)%tmp)

Submission status: Accepted

Solution code:
import math

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

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

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

cnt = cnt_1 * K + cnt_2 * int((K-1)*K//2)

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

Submission status: Accepted

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

cna=0
for i,a in enumerate(A):
    for at in A[i+1:]:    
        if a>at:
            cna+=1

cna2=0
for a in A:
    for at in A:    
        if a>at:
            cna2+=1


kt=(K-1)*(K)//2

print((K*cna+kt*cna2)%tmp)

Submission status: Accepted

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

# O(N^2)
cnt_self = 0
cnt_left = 0
for i in range(N - 1):
    for j in range(i + 1, N):
        if A[i] > A[j]:
            cnt_self += 1
        if A[i] != A[j]:
            cnt_left += 1

ans = 0
ans = (ans + (K * cnt_self)) % (10 ** 9 + 7)

coeff = (K * (K - 1) // 2) % (10 ** 9 + 7)
ans = (ans + (coeff * cnt_left)) % (10 ** 9 + 7)

print(ans)

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:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right
from heapq import heappush, heappop

import re
# import numpy as np
# from scipy.misc import comb

# 再帰がやばいとき
import sys
sys.setrecursionlimit(10**9)

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e30)
MOD = int(1e9)+7 # 10^9 + 7

# field[H][W]
def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]

########

def c(seq):
    ans = 0
    for i in range(0, len(seq)):
        for j in range(i, len(seq)):
            if seq[i] > seq[j]:
                ans += 1
    return ans

def main():
    N, K = l_inpl()
    A = l_inpl()
    a = c(A)
    b = c(A*2)
    print((a*K+(b-2*a)*K*(K-1)//2)%MOD)

if __name__ == "__main__":
    main()

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):
    m = b + (e - b) // 2
    i, j = b, m
    r = k = 0
    while i < m and j < e:
        if a[i] <= a[j]:
            w[k] = a[i]
            i += 1
        else:
            r += m - i
            w[k] = a[j]
            j += 1
        k += 1
    a[e - m + i: e] = a[i: m]
    a[b: b + k] = w[:k]
    return r        
    
def mergesort(b, e):
    if e - b < 2:
        return 0
    m = b + (e - b) // 2
    return mergesort(b, m) + mergesort(m, e) + merge(b, e)


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

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):
    m = b + (e - b) // 2
    i, j = b, m
    r = k = 0
    while i < m and j < e:
        if a[i] <= a[j]:
            w[k] = a[i]
            i += 1
        else:
            r += m - i
            w[k] = a[j]
            j += 1
        k += 1
    a[e - m + i: e] = a[i: m]
    a[b: b + k] = w[:k]
    return r        
    
def mergesort(b, e):
    if e - b < 2:
        return 0
    m = b + (e - b) // 2
    return mergesort(b, m) + mergesort(m, e) + merge(b, e)


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

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
		ans %= mod
		b.insert(i,x)
	bef = max(a)
	j=0
	for i,cur in enumerate(b[::-1]):
		if cur!=bef:
			j = i
			bef = cur
		ans += k*(k-1)*j//2
		ans %= mod
	print(ans%mod)

if __name__=="__main__":
	solve()

Submission status: Accepted

Solution code:
from sys import stdin

N, K = [int(x) for x in stdin.readline().rstrip().split()]
A = [int(x) for x in stdin.readline().rstrip().split()]
ans = 0
inf = 10 ** 9 + 7

for i in range(N):
    cnt_left = 0
    cnt_right = 0
    for j in range(N):
        if A[j] < A[i]:
            if j < i:
                cnt_left += 1
            else:
                cnt_right += 1
    ans += (cnt_right * (K + 1) * K // 2) % inf
    ans += (cnt_left * (K - 1) * K // 2) % inf

print(ans % inf)

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):
    m = b + (e - b) // 2
    i, j = b, m
    r = k = 0
    while i < m and j < e:
        if a[i] <= a[j]:
            w[k] = a[i]
            i += 1
        else:
            r += m - i
            w[k] = a[j]
            j += 1
        k += 1
    a[e - m + i: e] = a[i: m]
    a[b: b + k] = w[:k]
    return r        
    
def mergesort(b, e):
    if e - b < 2:
        return 0
    m = b + (e - b) // 2
    return mergesort(b, m) + mergesort(m, 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:
from collections import Counter

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

def merge(b, e):
    m = b + (e - b) // 2
    i, j = b, m
    r = k = 0
    while i < m and j < e:
        if a[i] <= a[j]:
            w[k] = a[i]
            i += 1
        else:
            r += m - i
            w[k] = a[j]
            j += 1
        k += 1
    a[e - m + i: e] = a[i: m]
    a[b: b + k] = w[:k]
    return r        
    
def mergesort(b, e):
    if e - b < 2:
        return 0
    m = b + (e - b) // 2
    return mergesort(b, m) + mergesort(m, e) + merge(b, e)


r = k * mergesort(0, n)
c = n*(n-1)//2 - sum(x*(x-1)//2 for x in Counter(a).values())
print((r + c * k * (k - 1) // 2) % (10**9 + 7))

Submission status: Accepted

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

def resolve():
    n, k = map(int, input().split())
    aa = list(map(int, input().split()))

    a1 = 0
    for i in range(n-1,-1,-1):
        for j in range(i,-1,-1):
            if aa[i] < aa[j]:
                a1 += 1

    if k == 1:
        print(a1)
        return

    a2 = 0
    aa2 = aa * 2

    for i in range(2*n-1,-1,-1):
        for j in range(i,-1,-1):
            if aa2[i] < aa2[j]:
                a2 += 1

    if k == 2:
        print(a2)
        return

    a3 = 0
    aa3 = aa * 3

    for i in range(3*n-1,-1,-1):
        for j in range(i,-1,-1):
            if aa3[i] < aa3[j]:
                a3 += 1

    b1 = a2 - a1
    b2 = a3 - a2
    d = b2 - b1

    s = int(a1 + ((k-1) * (2 * b1 + (k-2) * d))//2)
    ans = s % (10**9 + 7)
    print(ans)



resolve()

Submission status: Accepted

Solution code:
s=list(map(int,input().split()))
t=list(map(int,input().split()))
if s[0]==1:
  print(0)
else:
  b=0
  for i in range(s[0]):
    a=0
    for j in range(s[0]):
      if t[i]>t[j]:
        a=a+1
    b=b+a*s[1]*(s[1]-1)//2
    b=b%1000000007
  b=b%1000000007
  for v in range(s[0]-1):
    a=0
    for w in range(v+1,s[0]):
      if t[v]>t[w]:
        a=a+1
    b=b+a*s[1]
    b=b%1000000007
  b=b%1000000007
  print(int(b))

Submission status: Accepted

Solution code:
n, k = input().split()
N = int(n)
K = int(k)
A = [int(a) for a in input().split()]
countAList = []
countBList = []
for j in range(N):
    countA = 0
    countB = 0
    for i in range(N):
        if A[i] < A[j]:
            countB += 1
            if i > j:
                countA += 1
    countAList.append(countA)
    countBList.append(countB)
result = 0

for a, b in zip(countAList, countBList):
    result += int(K * a) + int(b * K * (K - 1) // 2)
    result %= 10 ** 9 + 7
print(result)

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):
    m = b + (e - b) // 2
    i, j = b, m
    r = k = 0
    while i < m and j < e:
        if a[i] <= a[j]:
            w[k] = a[i]
            i += 1
        else:
            r += m - i
            w[k] = a[j]
            j += 1
        k += 1
    a[e - m + i: e] = a[i: m]
    a[b: b + k] = w[:k]
    return r        
  
  
def mergesort(b, e):
    if e - b < 2:
        return 0
    m = b + (e - b) // 2
    return mergesort(b, m) + mergesort(m, 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 = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
a_tentou = [0 for i in range(n)]
a_tentou2 = [0 for i in range(n)]
mod = 10 **9 + 7

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

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

answer = 0
for i in range(n):
    answer += a_tentou[i] * k
    answer += a_tentou2[i] * (k - 1) * k // 2
    answer = answer % mod
print(answer)

Submission status: Accepted

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

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

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

total_inv = k * intra_inv + k * (k - 1) // 2 * inter_inv
dst = int(total_inv % (10**9 + 7))
print(dst)

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

ans = 0
mod = 10 ** 9 + 7

for i in range(N):
    for j in range(i + 1, N):
        if a_list[i] > a_list[j]:
            ans += K
            ans %= mod

for i in range(N):
    cnt = 0
    for j in range(N):
        if a_list[i] > a_list[j]:
            cnt += 1
    ans += cnt * 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()))

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

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

ans = (p * K) % 1000000007 + (q * K * (K-1) // 2) % 1000000007

print(ans % 1000000007)

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))//2
 
ans = int(numbers % (10**9 + 7))
print(ans)

Submission status: Accepted

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

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

a2 = a * 2
cnt2 = 0
for i in range(len(a)):
    for j in range(len(a), len(a2)):
        if a2[i] > a2[j]:
            cnt2 += 1

print((cnt1 * k + cnt2 * k * (k-1) // 2) % MOD)

Submission status: Accepted

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

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

mod = 1000000007

# K = 2のときの初期値が必要
B = A * 2
syokiti_A = 0
syokiti_B = 0
for i in range(N):
    for j in range(i, N):
        if A[i] > A[j]:
            syokiti_A += 1

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

ans = (syokiti_A * K) % mod + (syokiti_B * K * (K-1) // 2) % mod
print(int(ans) % mod)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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

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



if __name__ == "__main__":
    main()

Submission status: Accepted

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

mod = 10**9+7

g = 0
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        elif i >= j:
            continue
        if a[i] > a[j]:
            #print(i,j)
            g += 1

if k == 1:
    print(g)
    exit()
    
a2 = []

for i in range(2*n):
    a2.append(a[i%n])
    
f = 0

for i in range(n):
    for j in range(2*n):
        if i == j:
            continue
        elif i >= j:
            continue
        if a2[i] > a2[j]:
            #print(i,j)
            f += 1

t = f-g
k = k

#print(t)
#exit()
#print(int((k*g%mod + t*(0.5*((k-1)*k))%mod)%mod))
#print(int(( (k%mod*g%mod)%mod + (t*(0.5*((k-1)%mod*k%mod)) ) %mod)%mod))
#print(int((k*g%mod + t*(0.5*((k-1)%mod*k%mod))%mod)%mod))
#print(int((k*g%mod + t*(0.5*((k-1)%mod*k%mod))%mod)%mod))
#ans1 = int((k*g%mod)%mod)
#ans2 = t*(0.5* (k-1)%mod * k%mod ) %mod
#ans2 = t*(0.5*((k-1)%mod*k%mod))%mod
#ans2 = int(t*(((k-1)%mod*k%mod)%mod)//2%mod)
ans = g*k + t*k*(k-1)//2
print( ans%mod)
#print(int(((k*g) + (t*(0.5*((k-1)*k))))%mod))
exit()

Submission status: Accepted

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

mod = 10**9+7

g = 0
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        elif i >= j:
            continue
        if a[i] > a[j]:
            #print(i,j)
            g += 1

if k == 1:
    print(g)
    exit()
    
a2 = []

for i in range(2*n):
    a2.append(a[i%n])
    
f = 0

for i in range(n):
    for j in range(2*n):
        if i == j:
            continue
        elif i >= j:
            continue
        if a2[i] > a2[j]:
            #print(i,j)
            f += 1

t = int((f-g)%mod)
k = int(k%mod)

#ans = g*k + t*k*(k-1)//2
#ans = g*k + t*k*(k-1)//2
print(int(( (k*g) + t*((k-1)*k//2))%mod))
#print(int(((k*g) + (t*(0.5*((k-1)*k))))%mod))
exit()

Submission status: Accepted

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

tmp = 0
for i in a:
    for j in b:
        if i > j:
            tmp += 1

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

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = [int(_) for _ in input().split()]
B = 10 ** 9 + 7
work = 0
ans1, ans2 = 0, 0
for i, p in enumerate(A):
    # A1セット中の個数
    for j in range(i + 1, N):
        if p > A[j]:
            ans1 += 1
    # A2セット目
    for q in A:
        if p > q:
            ans2 += 1

ans1 *= K
ans2 *= (K * (K - 1)) // 2
ans = ans1 + ans2
print(int(ans % B))

Submission status: Accepted

Solution code:
N,K= list(map(int, input().split()))
A= list(map(int, input().split()))
AA=sorted(A)
num=0
before=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:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
INF = (10 ** 9) + 7

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

tmp1 = 0
tmp2 = 0

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

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

ans = (tmp1 * (K)) + ((K * ((K - 1)) // 2) * tmp2)
print(ans % INF)

Submission status: Accepted

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

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

for i in range(N):
    before = 0
    after = 0
    for j in range(i):
        if A[i] > A[j]:
            before += 1
    for j in range(i + 1, N):
        if A[i] > A[j]:
            after += 1
    # print (i, before, after)
    ans += (tmp * (before + after) + after * K)
    ans %= MOD

print (ans)

Submission status: Accepted

Solution code:
# jsc2019-qualB - Kleene Inversion
class BIT:  # Binary Indexed Tree (Fenwick Tree)
    def __init__(self, lim):
        self.size = lim
        self.tree = [0] * (lim + 1)  # 1-idx

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

    def sum(self, i):  # sum of [1, i], O(logN)
        ret = 0
        while i > 0:
            ret += self.tree[i]
            i -= i & -i
        return ret

    def range_sum(self, l, r):  # range sum of [l, r]
        return self.sum(r) - self.sum(l - 1)


def main():
    N, K = tuple(map(int, input().split()))
    A = tuple(map(int, input().split()))
    MOD = 10 ** 9 + 7
    bit = BIT(2000)
    x = 0
    for i, a in enumerate(A, 1):  # internal inversion
        bit.add(a, 1)
        x += i - bit.sum(a)
    y = -x
    for i, a in enumerate(A, 1):  # external inversion
        bit.add(a, 1)
        y += i + N - bit.sum(a)
    ans = (x * K + y * K * (K - 1) // 2) % MOD
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
cnt=0
mod=10**9+7
n,k=map(int,input().split())
a=list(map(int,input().split()))
#a単体での店頭数
for i in range(n):
    for j in range(i+1,n):
        if a[i]>a[j]:
            cnt+=1
ans=cnt*k%mod
cnt=0
for i in range(n):
    for j in range(n):
        if a[i]>a[j]:
            cnt+=1
temp=((k-1)*k//2)%mod
ans+=cnt*temp%mod
ans%=mod
print(ans)

Submission status: Accepted

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

# 内部の転倒数
ls = a[:]
inner = 0
while ls:
    x = ls.pop(0)
    inner += sum(1 if x > y else 0 for y in ls)

# 外部の転倒数
outer = 0
for x in a:
    for y in a:
        if x > y:
            outer += 1


print((inner*k + outer*(k-1)*k//2) % (10**9+7))

Submission status: Accepted

Solution code:
# jsc2019-qualB - Kleene Inversion
from collections import Counter
from itertools import accumulate


def main():
    N, K = tuple(map(int, input().split()))
    A = tuple(map(int, input().split()))
    MOD = 10 ** 9 + 7
    C = list(Counter(A).values())
    ac = list(accumulate(C[:-1]))
    x = sum(i * j for i, j in zip(C[1:], ac)) % MOD
    y = sum(sum(b > a for b in A[i + 1 :]) for i, a in enumerate(A[:-1]))
    ans = (x * (1 + K) * K // 2) % MOD
    ans = (ans - y * K) % MOD
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# jsc2019-qualB - Kleene Inversion
from collections import Counter
from itertools import accumulate


def main():
    N, K = tuple(map(int, input().split()))
    A = tuple(map(int, input().split()))
    MOD = 10 ** 9 + 7
    C = list(Counter(A).values())
    ac = list(accumulate(C[:-1]))
    x = sum(i * j for i, j in zip(C[1:], ac)) % MOD
    y = 0
    for i, a in enumerate(A[:-1]):
        y += sum(b > a for b in A[i + 1 :])
    ans = (x * (1 + K) * K // 2) % MOD
    ans = (ans - y * K) % MOD
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# jsc2019-qualB - Kleene Inversion
from collections import Counter


def main():
    N, K = tuple(map(int, input().split()))
    A = tuple(map(int, input().split()))
    MOD = 10 ** 9 + 7
    C = Counter(A)
    x = sum(sum(j > i for j in A) * c for i, c in C.items())
    y = sum(sum(b > a for b in A[i + 1 :]) for i, a in enumerate(A[:-1]))
    ans = (x * K * (1 + K) // 2) % MOD
    ans = (ans - y * K) % MOD
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
B = [0] * len(A)
C = [0] * len(A)
mod = 10 ** 9 + 7
counter = 0
for i in range(N):
    B[i] = sum([A[i] > A[j] for j in range(0, N)])  # Aの中でAi>Ajとなる個数
    C[i] = sum([A[i] > A[j] for j in range(i, N)])  # Aの中でAi 以降で　Ai>Ajとなる個数

for i in range(N):
    c = (C[i] * K)%mod + ((K - 1) * K * B[i] // 2)%mod
    
    counter = (counter + c) % mod
print(int(counter))

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
B = [0] * len(A)
C = [0] * len(A)
mod = 10 ** 9 + 7
counter = 0
for i in range(N):
    B[i] = sum([A[i] > A[j] for j in range(0, N)])  # Aの中でAi>Ajとなる個数
    C[i] = sum([A[i] > A[j] for j in range(i, N)])  # Aの中でAi 以降で　Ai>Ajとなる個数

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

    counter = (counter + c) % mod
print(int(counter))

Submission status: Accepted

Solution code:
def main(n,k,a):

    mod = 10**9 + 7
    t1, t2 = 0, 0
    for i in range(n):
        for j in range(n):
            if a[i] > a[j]:
                t1 += 1
        for j in range(n - i - 1):
            if a[i] > a[j + i + 1]:
                t2 += 1

    count = (t1 * ((k * (k - 1)) // 2)) % mod
    count += (t2 * k) % mod
    print(int(count % mod))


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=map(int, input().split())
a=list(map(int, input().split()))

sf=[0]*n
sb=[0]*n

for i in range(n):
    for j in range(n):
        if i<j:
            if a[i]>a[j]:
                sf[i]+=1
        else:
            if a[i]>a[j]:
                sb[j]+=1
ans=0
for i in range(n):
    ans+=k*sf[i]+k*(k-1)*(sf[i]+sb[i])//2

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

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:
# jsc2019-qualB - Kleene Inversion
from collections import Counter
from itertools import accumulate


def main():
    N, K = tuple(map(int, input().split()))
    A = tuple(map(int, input().split()))
    MOD = 10 ** 9 + 7
    C = list(Counter(A).values())
    ac = list(accumulate(C[:-1]))
    x = sum(i * j for i, j in zip(C[1:], ac))
    y = 0
    for i, a in enumerate(A[:-1]):
        y += sum(b > a for b in A[i + 1 :])
    ans = (x * (1 + K) * K // 2) % MOD
    ans -= y * K
    ans %= MOD
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

mod = 10 ** 9 + 7
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

if k%2 == 0:
    sigmakp = (int(k/2) * (k+1)) % mod
    sigmakn = (int(k/2) * (k-1)) % mod
else:
    sigmakp = (int((k+1)/2) * k) % mod
    sigmakn = (int((k-1)/2) * k) % mod

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*(c<d)+k*-~k*(c>d)>>1for i,c in enumerate(a)for d in a[i:])%(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 = [[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

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

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)