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 = 1000000007

ans = 0
for i in range(len(A)):
    cnt1 = 0
    cnt2 = 0
    for j in range(i, i+len(A)):
        if A[i] > A[j%(len(A))]:
            if j < len(A):
                cnt1 += 1
            else:
                cnt2 += 1
    ans += (cnt1 * K * (K+1) // 2)
    ans += (cnt2 * (K-1) * K // 2)
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter
from heapq import heapify, heappop, heappush
from sys import stdin

mod = 1000000007

#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

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

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


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

    #ans = int(( 2*ini + (K-1)*diff ) * K / 2)
    ans = ((2*ini+(K-1)*diff) % (10**9+7)) * K % (10**9+7)
    ans = ans * mod_inv(2,mod) % (10**9+7)
    print(ans)

input = lambda: stdin.readline().rstrip()
main()

Submission status: Accepted

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

for i in range(len(a)):
    p=sum([1 for j in a[i:] if a[i]>j])
    q=sum([1 for j in a if a[i]>j])
   # print(p,q)
    s=int(p*k%(1000000000+7))
    t=int(q*(((k-1)*k)//2)%(1000000000+7))
    ans+=s+t


print(int(ans%(1000000000+7)))

Submission status: Accepted

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

# 自分自身の中で、転倒するような数 * N-1
# 最後の繰り返しは、転倒しないので別途計算
## これじゃダメで、転倒数はどんどん減少していくはず。

# 順序が関係するのは最初のブロックだけ
# あとは、繰り返しになる(繰り返し数が減っていく)

# まず、順序を含めた合算個数を調べる
count_with_seq = 0
deal = 0
for i in range(N) :
    ai = A_list[i]
    for k in range(i+1,N) :
        deal += 1
        ak = A_list[k]
        if (ai > ak) :
            # print(ai,ak)
            count_with_seq += 1

count_without_seq = 0
for ai in A_list :
    for ak in A_list :
        if (ai > ak) :
            count_without_seq += 1

# print(count_with_seq,count_without_seq)

# これらの塊の繰り返し数は、
# 初項：N回
# 初項以降 : sum(k) (1<=K<=n-1) 

total_count = count_with_seq * K
# print(total_count)
rep = (1 + (K-1)) * (K-1) // 2
total_count += count_without_seq * rep
# print(rep)
print(total_count % 1000000007)

Submission status: Accepted

Solution code:
# coding: utf-8
# from time import time

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

# start = time()

# C = [[A[i], i] for i in range(N)]
# C = []
# appeared = []
# for i in range(N):
#     if A[i] not in appeared:
#         C.append([A[i], i])
#         appeared.append(A[i])

C = [[A[i], i] for i in range(N)]

C = sorted(C, key=lambda x: x[0], reverse=False)
# print(C)

tento_dict = {C[0][1]: 0}  # i == 0
for i in range(1, N):
    if C[i][0] == C[i-1][0]:
        tento_dict[C[i][1]] = tento_dict[C[i-1][1]]
    else:
        tento_dict[C[i][1]] = i

# tento_dict = {C[i][1]: N-(i+1) for i in range(N)}
# print(tento_dict)

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

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

Submission status: Accepted

Solution code:
#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

nk = input().split(" ");
n = int(nk[0]);
k = int(nk[1]);
a = input().split(" ");

waru = 10 ** 9 + 7;

for i in range(n) :
	a[i] = int(a[i]);

kaisu = [0] * n;
usiro = [0] * n;

for i in range(n) :
	for j in range(n) :
		if a[i] > a[j] :
			kaisu[i] += 1;
			if i < j :
				usiro[i] += 1;

ans = 0;
for i in range(n) :
	ans += ((((((k-1)%waru) * (k%waru) )%waru) *mod_inv(2,waru)) * (kaisu[i]%waru) + ((k%waru)*(usiro[i]%waru))%waru)%waru;
		
	
print(int(ans%waru));

Submission status: Accepted

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

listl = [0]*n
listr = [0]*n

tmpmax = 0
for i in range(1,n):
    tar = lista[i]
    for j in range(i,-1,-1):
        if lista[j]<tar:
            #listl[i] = listl[j]+1
            #break
            listl[i] +=1

for i in range(n-2,-1,-1):
    tar = lista[i]
    for j in range(i,n):
        if lista[j]<tar:
            #listr[i] = listr[j]+1
            #break
            listr[i] += 1
            
            
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

ans = 0
i2 = mod_inv(2,((10**9)+7))
for i in range(n):
    f = (listl[i]*(k-1)+listr[i]*k)%((10**9)+7)
    t = (listr[i])%((10**9)+7)
    
    ans += int(((f+t)*k)*i2)
    
    ans = int(ans%((10**9)+7))
    
print(ans)

Submission status: Accepted

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


val = 0
for i in range(n):
    inv = 0
    sub = 0
    B = A[i + 1:] + A[:i]
    for j in range(n - 1):
        if A[i] > B[j] and j >= n - i - 1:
            inv += 1
            sub += 1
        elif A[i] > B[j]:
            inv += 1

    val += inv * k * (k + 1) // 2 - sub * k
    val %= 10 ** 9 + 7
    
print(val)

Submission status: Accepted

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

mlist=[0]*n
nlist=[0]*n

for i in range(n):
    for j in range(n):
        if alist[i]>alist[j] and i>j:
            mlist[i]+=1
        elif alist[i]>alist[j] and i<j:
            nlist[i]+=1

#print(mlist, nlist)
kotae=0
for i in range(n):
    if k%2==1:
        a1=k*int((k+1)/2)
        a2=k*int((k-1)/2)
    else:
        a1=int(k/2)*(k+1)
        a2=int(k/2)*(k-1)
    kotae+=nlist[i]*a1
    kotae+=mlist[i]*a2
    kotae=kotae%(10**9+7)

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
mod=1000000007
#mod=1777777777
pi=3.1415926535897932
IS=float('inf')

n,k=map(int,input().split())
a=[int(i) for i in input().split()]
b=a*2
ans=chk=0
for i in range(n-1):
    for j in range(i+1,n):
        if a[i]>a[j]:
            chk+=1
            chk%=mod

for i in range(n):
    for j in range(n,n*2):
        if b[i]>b[j]:
            ans+=1
            ans%=mod
t=k-1
t=t*(t+1)//2
print((chk*k%mod+ans*t%mod)%mod)

Submission status: Accepted

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

total = (K + 1) * K // 2
count = 0
for i, Ai in enumerate(A):
    for j in range(i, len(A)):
        if Ai > A[j]:
            count += 1 
sortA = sorted(A, reverse=True)
sort_count = 0
for i, sortAi in enumerate(sortA):
    for j in range(i, len(sortA)):
        if sortAi > sortA[j]:
            sort_count += 1 
            
sub = (sort_count - count) * K
print((total * sort_count - sub) % (10**9 + 7))

Submission status: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

class BIT:
    def __init__(self, n):
        # 0-indexed
        self.size = n
        self.tree = [0] * (n+1)
 
    def sum(self, i):
        s = 0
        i += 1
        while i > 0:
            s += self.tree[i-1]
            i -= i & -i
        return s
    
    # 区間和の取得 [l, r)
    def get(self, l, r=None):
        # 引数が1つなら一点の値を取得
        if r is None: r = l+1
        res = 0
        if r: res += self.sum(r-1)
        if l: res -= self.sum(l-1)
        return res

    # 値の追加：添字, 値
    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i-1] += x
            i += i & -i

# 1からnまでの等差数列の和
def get_sum(n): return (1+n)*n//2

N, K = MAP()
A = LIST()
M = max(A)

bit = BIT(M+1)
org = 0
for i in range(N-1, -1, -1):
    bit.add(A[i], 1)
    # 自分より右にある、自分より小さな数の個数
    org += bit.sum(A[i]-1)
bit = BIT(M+1)
org2 = 0
for i in range(N):
    bit.add(A[i], 1)
    # 自分より左にある、自分より小さな数の個数
    org2 += bit.sum(A[i]-1)

ans = (org*K+(org+org2)*get_sum(K-1)) % MOD
print(ans)

Submission status: Accepted

Solution code:
n,k=map(int, input().split())
a=list(map(int, input().split()))
cnt=0
for i in range(len(a)):
    for j in range(i+1,len(a)):
        if a[i]>a[j]:
            cnt+=1
ans=cnt*k
cnt2=0
aa=sorted(a,reverse=True)
for i in range(len(aa)):
    for j in range(i+1,len(aa)):
        if aa[i]>aa[j]:
            cnt2+=1
ans2=cnt2*((k*(k-1))//2)
print((ans+ans2)%((10**9)+7))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = [int(x) for x in input().split()]
ans_base = 0
ans_base_rev = 0
big = (10**9)+7
for i in range(N-1):
    for k in range(i + 1, N):
        if A[i] > A[k]:
            ans_base += 1
        elif A[i] < A[k]:
            ans_base_rev += 1

#ans_base = ans_base % big
#ans_base_rev = ans_base_rev % big
val_p = (K * (K + 1)) // 2
val_m = (K * (K - 1)) // 2
#val_m = val_m % big
#val_p = val_p % big
ans = ans_base * val_p + ans_base_rev * val_m
ans = ans % big
print(int(ans))

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
m = (10**9) + 7
after = sum([len(list(filter(lambda x: A[i] > x, A[i+1:]))) for i in range(N - 1)])%m
_all = sum([len(list(filter(lambda x: A[i] > x, A))) for i in range(N)])%m

k = (K*K-(K*(K+1)//2))%m

print((
  (after*K)%m
  +(_all*k)%m
)%m)

Submission status: Accepted

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

mod=10**9+7

# 単体の転倒数
first=0
for i in range(n-1):
    a=a_list[i]
    for j in range(i+1,n):
        if a>a_list[j]:
            first+=1

# 右に同じ列があったときの転倒数
rightnum=0            
for i in range(n):
    a=a_list[i]
    for a_all in a_list:
        if a>a_all:
            rightnum+=1

samecol=(k*(k-1)//2)%mod
ans=(samecol*rightnum)%mod
ans=(ans+first*k)%mod
print(ans)

Submission status: Accepted

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

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

for i in range(n):
    p=0
    for j in range(i):
        if a[j]>a[i]:
            p+=1
    l1.append(p)

ans=0
mod=10**9+7
for i in range(n):
    ans+=k*(2*l1[i]+(k-1)*(l[i]))//2
    ans=ans%mod
print(ans)

Submission status: Accepted

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

ans = 0
# 単調減少
for i in range(n-1):
    b = a[i]
    count = 0
    for j in range(i+1, n):
        if b > a[j]:
            count += 1
    if count == 0:
        continue
    ap = (k * (k+1) // 2)
    tmp = (count * ap)
    ans += tmp
    ans %= MOD

# それ以外
for i in range(n):
    b = a[i]
    count = 0
    for j in range(i):
        if b > a[j]:
            count += 1
    if count == 0:
        continue
    ap = ((k-1) * k // 2)
    tmp = (count * ap)
    ans += tmp
    ans %= MOD
print(int(ans))

Submission status: Accepted

Solution code:
import math
n,k=map(int, input().split())
a=list(map(int, input().split())) 
count=0
ans=0
x=0
y=0
y=(k+1)*k//2
y=y%(10**9+7)
b=sorted(a)
for i in range(n):
    for j in range(i,n):
        if a[i]>a[j]:
            count+=1
    for p in range(n):
        if b[p]==a[i]:
            x=p
            break
    
    ans+=count*k+x*(k-1)*k//2
    count=0
            

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

#+++++

mod = 7 + (10**9)
		
def main():
	n, k = map(int, input().split())
	aa_list=list(map(int, input().split()))
	
	ret = 0
	for i, v in enumerate(aa_list):
		a=len([x for x in aa_list[:i] if x < v])
		b=len([x for x in aa_list[i+1:] if x <v])
		ret += a*k*(k-1)//2
		ret += b*k*(k+1)//2
	print(ret%mod)
	
	
#+++++


if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
A = list(map(int, input().split()))
mod = 10**9 + 7
length = len(A)
R_down = [0]*length
L_down = [0]*length

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

    R_down[i] = count

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

    L_down[i] = count

R = sum(R_down)*k*(k+1)//2
L = sum(L_down)*(k-1)*k//2
ans = (R + L) % mod
print(int(ans))

Submission status: Accepted

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

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

import bisect

A.sort()
v2 = 0
for a in A:
    v2 += bisect.bisect_left(A, a)

mod = 10 ** 9 + 7
ans = (v1 * K) % mod

if K > 1:
    tmp = (K - 1) % mod
    tmp = (tmp * K // 2) % mod
    # print(tmp)
    ans += tmp * v2
ans = ans % mod

# for i in range(1, K):
#     ans += (v2 * i) % mod
#     ans = ans % mod
print(ans)

Submission status: Accepted

Solution code:
#print(sum(range(10)))45
n,k=map(int,input().split())
lis=list(map(int,input().split()))
count=0
for i in range(len(lis)):
  for j in range(i+1,len(lis)):
    if lis[i]>lis[j]:
      count+=1     
lista=[]
for i in lis:
  counta=0
  for j in lis:
    #counta=0
    if i>j:
      counta+=1
  lista.append(counta)
print((count*k+sum(lista)*(k*(k-1)//2))%(10**9+7))

Submission status: Accepted

Solution code:
N,K = [int(s) for s in input().split()]
ls=[int(s) for s in input().split()]
####まず一周の場合を求める
low=0
high=0
eq=0
for i in range(N):
  for j in range(i+1,N):
    if(ls[i]>ls[j]):
      low+=1
    elif(ls[i]<ls[j]):
      high+=1
    else:
      eq+=1
####K周の場合
ans=0
ans+=low*K*(K+1)//2
ans+=high*K*(K-1)//2
ans=ans%(1000000007)
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N, K = map(int, input().split())
A_list = list(map(int, input().split()))

def count_inversion(target_list):
    return sum(sum(m<n for m in target_list[i+1:]) for i,n in enumerate(target_list))

A_list_copy = A_list
invension_increase = 0
for i in set(A_list):
    max_num = max(A_list_copy)
    max_count = A_list_copy.count(max(A_list_copy))
    A_list_copy = [num for num in A_list_copy if num != max_num]
    invension_increase += max_count * len(A_list_copy)

ans_count = count_inversion(A_list) * K
ans_count += invension_increase * K * (K - 1) // 2

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

Submission status: Accepted

Solution code:
tmp = [int(i) for i in input().split(" ")]
n = tmp[0]
k = tmp[1]
a = [int(i) for i in input().split(" ")]
import numpy as np
a = np.array(a)
uni = np.unique(a)
co = [np.sum(a==i) for i in uni]
ind = np.array([np.sum(co[:uni.tolist().index(i)]) for i in a]).astype(np.int32)
c = 0

for i in range(len(a)):
    c += np.sum(a[i:]<a[i])
m = 10**9+7
tm = int(c)*int(k) % m
if k % 2 == 0:
    t = k * (k//2-1) + k//2
    t %= m
else:
    t = k * (k//2)
    t %= m
print((int(np.sum(ind))*t+tm) % m)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
N,K = list(map(int,input().split()))
A = list(map(int,input().split()))
a = N*[0]
b = N*[0]

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

print((sum(a)*K*(K+1)//2+sum(b)*K*(K-1)//2)%(10**9+7))

Submission status: Accepted

Solution code:
from sys import stdin
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()]
def count_inversion(sequence):
    r = [0]*len(sequence)
    l = [0]*len(sequence)
    for i in range(1,len(sequence),1):
        cnt_r = 0
        cnt_l = 0
        for j in range(i,len(sequence),1):
            if sequence[i-1] > sequence[j]:
                cnt_r += 1
            elif sequence[i-1] < sequence[j]:
                cnt_l += 1
        r[i-1] = cnt_r
        l[i-1] = cnt_l
    return sum(r),sum(l)
r,l = count_inversion(A)
ans = ((K*(K+1))//2)*r
ans += (((K*(K-1))//2))*l
ans = ans%mod
print(ans)

Submission status: Accepted

Solution code:
import sys

def process(data):
	count1 = 0
	count2 = 0

	N = int(data[0][0])
	K = int(data[0][1])
	A = list(map(int, data[1]))

	for i in range(len(A)-1):
		for j in range(i+1, len(A)):
			if A[i] > A[j]:
				count1 += 1
	A.reverse()
	
	for i in range(len(A)-1):
		for j in range(i+1, len(A)):
			if A[i] > A[j]:
				count2 += 1	

	count1 = count1 * K*(K+1)/2
	count2 = count2 * (K-1)*K/2

	count = count1 + count2

	count = count % (10**9+7)
	return count



def main():
	d = []
	for i in range(2):
		data = raw_input()
		data = data.split(" ")
		d.append(data)
	print(process(d))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

result = 0

if K == 1:
    B = A
    for i in range(N):
        for j in range(i+1, N):
            if B[i] > B[j]:
                result += 1
else:
    B = A + A
    for i in range(N):
        C = 0
        D = 0
        E = 0
        for j in range(i+1, N):
            if B[i] > B[j]:
                C += 1
        for j in range(N, N+i+1):
            if B[i] > B[j]:
                D += 1
        E = K * (K * (C + D) + C - D) // 2
        E = E % (10**9 + 7)
        result += E
    result = result % (10**9 + 7)

print(result)

Submission status: Accepted

Solution code:
import collections
# from scipy.special import comb
from scipy.misc import comb


NUM_MOD = 10 ** 9 + 7


len_arr, num_repeat = map(int, input().split(' '))
arr = list(map(int, input().split(' ')))

differ = [len(list(filter(arr[i].__gt__, arr[i+1:]))) for i in range(0, len_arr)]
ans_internal = sum(differ)
num_kind = len(collections.Counter(arr))

if num_kind == 1:
    ans_external = 0
else:
    differ = [len(list(filter(arr[i].__gt__, arr))) for i in range(0, len_arr)]
    ans_external = sum(differ)

num_comb = comb(num_repeat, 2, exact=True)
ans = num_comb * ans_external + num_repeat * ans_internal
# print(f"inter: {ans_internal}, ext: {ans_external}, {num_comb} {num_repeat}")

print(ans % NUM_MOD)
exit(0)

Submission status: Accepted

Solution code:
#!/snap/bin/pypy3
MOD = 10**9 + 7


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

    init = [0] * N
    diff = [0] * N
    for i, a in enumerate(A):
        init[i] = len(list(filter(lambda x: x < a, A[i:])))
        diff[i] = len(list(filter(lambda x: x < a, A)))

    ans = sum((K * (2 * ini + (K - 1) * dif) // 2) %
              MOD for ini, dif in zip(init, diff)) % MOD

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
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 I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n,k=LI()
  l1=LI()
  l2=sorted(l1)

  ans=0
  _ans=0
  for i,x in enumerate(l1):
    _l=sorted(l1[i:])
    ans+=bisect.bisect_left(_l,x)
    _ans+=bisect.bisect_left(l2,x)
  # print(ans,_ans)

  return (ans*k+(_ans*(k-1)*k//2))%mod


# main()
print(main())

Submission status: Accepted

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

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

    l = 0
    for j in range(i+1, N):
        if A[i]>A[j]:
            l += 1
    cnt += K*(l + l*K)//2

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

Submission status: Accepted

Solution code:

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

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

mod = 1000000007

need = (k * (k + 1)) // 2
need2 = ((k - 1) * k) // 2
ans = 0

freq = []
before = []
for i in range(0, 3000):
	freq.append(0)
	before.append(0)
	

for i in range(0, n):
	for j in range(i + 1, n):
		if(a[i] > a[j]):
			freq[i] += 1
			
	j = i - 1
	while j >= 0:
		if(a[i] > a[j]):
			before[i] += 1
		j -= 1
		
	ans += (freq[i] * need)
	ans += (before[i] * need2)

#print(ans)
print(ans % mod)

Submission status: Accepted

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

M = 1000000007

answer = 0
for i in range(n):
    p = 0
    q = 0
    for j in range(n):
        if a[j] < a[i]:
            p += 1
            if j > i:
                q += 1
    answer += q * k + p * k * (k - 1) // 2
    answer %= M

print(answer)

Submission status: Accepted

Solution code:
import bisect
mod = 10**9+7
def main():
    n,k=map(int,input().split(' '))
    a = list(map(int,input().split(' ')))
    a_fall= 0
    a_rev = sorted(a,reverse=True)
    u_cnt = 0
    for i in range(n-1):
        a_sorted = sorted(a[i+1:])
        a_fall += bisect.bisect_left(a_sorted,a[i])
        a_fall %=mod
    a_sorted = sorted(a)
    for i in a:
        u_cnt += bisect.bisect_left(a_sorted,i)
    ans = a_fall*k+u_cnt*(k-1)*k//2
    ans %= mod
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

m = (K-1)*K//2
val = count_ * m + count_self * K
            
print(divmod(val, 10**9+7)[1])

Submission status: Accepted

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

Submission status: Accepted

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

ans = 0

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

ansk = 0

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

print((ans * k + ansk * ((k-1)*k //2)) % (10**9 + 7))

Submission status: Accepted

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

Submission status: Accepted

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

a_sorted = sorted(a)

bit = [0] * 2001

inversion = 0
for i in range(n):
  bit[a[i]] += 1
  s = 0
  for j in range(a[i]+1):
    s += bit[j]
  inversion += i + 1 - s
  
inversion *= k
  
for i in range(n):
  inversion += (a_sorted.index(a[i]) * k * (k - 1)) // 2
  
print(inversion % int(10**9 + 7))

Submission status: Accepted

Solution code:
import bisect

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

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

res = 0
b = sorted(a)
for e in b:
    kw = bisect.bisect_right(b,e)
    res += n-kw

print((k*ass%mod+( (k*(k-1)//2)%mod )*res%mod)%mod)

Submission status: Accepted

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

a1=[int(i) for i in input().split()]
b1=[]
for i in range(len(a1)):
    b1.append([sum(x>a1[i] for x in a1[:i]),0])
#print(b1)
l=len(a1)
a1.extend(a1)
#print(a1)
for i in range(l):
    #print(i)
    b1[i][1]=sum(x>a1[i+l] for x in a1[:i+l])

c=0
for i in range(len(b1)):
    c+=(2*b1[i][0]+(k-1)*(b1[i][1]-b1[i][0]))*k//2
    if c>10**9+7:
        c=c%(10**9+7)

print(c)

Submission status: Accepted

Solution code:
mod = 10**9+7
n , k = map(int,input().split())
arr =[ int(i) for i in input().split() ]
cnt_tot = [ 0 for i in range(2005) ]
bit = [ 0 for i in range(2005) ]
def sum(r):
    global bit
    ret = 0
    while r >= 0:
        ret += bit[r]
        r = ( r & (r+1) ) - 1
    return ret

def add(idx, delta):
    global bit
    while idx < 2005:
        bit[idx] += delta
        idx = idx | (idx+1)

def sum2(l,r):
    return sum(r) - sum(l-1)

for i in range(n):
    cnt_tot[arr[i]] += 1
for i in range(1,2005):
    cnt_tot[i] += cnt_tot[i-1]

ans = 0
full = (k-1) * (k) * pow(2,mod-2,mod)
for i in range(n):
    ans += (n-cnt_tot[arr[i]])
ans = ans * full
# print(ans)
other = 0
for i in range(n):
    other += sum2(arr[i]+1,2004)
    add(arr[i],1)
other = other * k
# print(other)
ans += other

ans = ans % mod

print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
L = list(map(int, input().split()))
d = {}
Lsorted = sorted(L)
for i in range(n):
    idx = Lsorted.index(L[i])
    bigger = len([b for b in L[i:] if b<L[i]])
    d[i] = [bigger,idx]
# d= num:[x,y]
# x*k + y*k*(k-1)/2を全てのkeyに対して
res = 0
for key in d:
    [x, y] = d[key]
    res += x*k + y*k*(k-1)//2
print(res % (10**9 + 7))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int

def mergeSortInversions(arr):
    if len(arr) == 1:
        return arr, 0
    else:
        a = arr[:len(arr)//2]
        b = arr[len(arr)//2:]
        a, ai = mergeSortInversions(a)
        b, bi = mergeSortInversions(b)
        c = []
        i = 0
        j = 0
        inversions = 0 + ai + bi
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            c.append(a[i])
            i += 1
        else:
            c.append(b[j])
            j += 1
            inversions += (len(a)-i)
    c += a[i:]
    c += b[j:]
    return c, inversions

def mergeAndCountSplitInv(c, d):
    # c: left half, d: right half, both sorted
    nc = len(c)
    nd = len(d)
    b = [0] * (nc + nd)
    i, j = 0, 0
    splitInv = 0
    for k in range((nc + nd)):
        if i == nc: # c is used up
            b[k] = d[j]
            j += 1
            continue
        if j == nd: # d is used up
            b[k] = c[i]
            i += 1
            continue

        if c[i] <= d[j]: 
            b[k] = c[i]
            i += 1
        elif c[i] > d[j]:
            b[k] = d[j]
            splitInv += nc - i
            j += 1
    return b, splitInv

def sortCountInv(a):
    # a: list of int
    n = len(a)
    if n <= 1: # base case
        return a, 0
    c, leftInv = sortCountInv(a[ : n//2])
    d, rightInv = sortCountInv(a[n//2: ])
    b, splitInv = mergeAndCountSplitInv(c, d)
    # print(leftInv, rightInv, splitInv)
    return b, leftInv + rightInv + splitInv

def solve(N: int, K: int, A: "List[int]"):
    A_sort, inv = mergeSortInversions(A)
    t = [0] * N
    for i in range(1, N):
        if A_sort[i] > A_sort[i-1]:
            t[i] = i
        else:
            t[i] = t[i-1]
    count = inv * K + sum(t) * (K * (K-1))//2
    count = count % MOD
    print(count)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, K, A)

if __name__ == '__main__':
    main()