Problem:


Score : 300 points

Problem Statement

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

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

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

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

Constraints

All values in input are integers.

1 \leq N \leq 2000

1 \leq K \leq 10^9

1 \leq A_i \leq 2000

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

2 2
2 1

Sample Output 1

3

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

B_0 > B_1

B_0 > B_3

B_2 > B_3

Thus, the inversion number of B is 3.

Sample Input 2

3 5
1 1 1

Sample Output 2

0

A may contain multiple occurrences of the same number.

Sample Input 3

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

Sample Output 3

185297239

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



Sample input:
2 2
2 1


Sample output:
3

Submission status: Accepted

Solution code:
import math

def A():
    temp = input().split()
    M = int(temp[0])
    D = int(temp[1])

    if D<22:
        print(0)
        return
    
    ans = 0

    for i in range(1, M+1):
        for j in range(22, D+1):
            if (j%10) >= 2 and (j%10)*int(j/10) == i:
                ans += 1
    
    print(ans)

def B():
    temp = input().split()
    N = int(temp[0])
    K = int(temp[1])
    A = [int(i) for i in input().split()]

    basic_inv = 0
    for i in range(0, len(A)):
        for j in range(i+1, len(A)):
            if A[i] > A[j]:
                basic_inv += 1
    
    if K == 1:
        print(basic_inv)
        return

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

    
    s = (K*(K-1))//2
    num = s
    k_mod = K
    print(int(k_mod*basic_inv + num*inv)%(10**9+7))

    # #check
    # full = A*K
    # sum = 0
    # for i in range(0, len(full)):
    #     for j in range(i+1, len(full)):
    #         if full[i] > full[j]:
    #             sum += 1
    #             sum %= (10**9+7)
    
    # print("check:", sum)

B()

Submission status: Accepted

Solution code:
def getlist():
	return list(map(int, input().split()))

N, K = getlist()
A = getlist()

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

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

ans1x = int(((K - 1) * K) // 2) % 1000000007
ans1 = ans1x * s % 1000000007
ans2 = K * x % 1000000007
print((ans1 + ans2) % 1000000007)

Submission status: Accepted

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

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

inv_sorted_A = 0
for i in range(0,N):
  for j in range(0,N):
    if i<j and sorted_A[i] < sorted_A[j]:
      inv_sorted_A += 1

if K == 1:
  print(inv_A)
else:  
  count = inv_sorted_A * K * (K-1) // 2  + inv_A * K 
  print(count % 1000000007)

Submission status: Accepted

Solution code:
def count_inversion(sequence):
    count = 0
    for i in range(1,len(sequence)):
        for j in range(i,len(sequence)):
            if sequence[i-1] > sequence[j]:
                count += 1
    else:
        count = count%MAX
    return count%MAX

def count_bigger(sequence):
    count = 0
    for num1 in sequence:
        for num2 in sequence:
            if num1 < num2:
                count += 1
    else:
        count = count%MAX
    return count%MAX

MAX = 10**9 +7
N, K = map(int,input().split())
A = list(map(int,input().split()))
ans = (count_bigger(A))%MAX

ans *= (K*(K-1)//2)%MAX
ans += ((K%MAX)*count_inversion(A))%MAX
print(int(ans%MAX))

Submission status: Accepted

Solution code:
def inpl(): return list(map(int, input().split()))

N, K = inpl()
A = inpl()
MOD = 10**9+7
ans = 0
for i in range(N):
    d0 = 0
    d1 = 0
    for j in range(i):
        d0 += A[i] > A[j]
    for j in range(i, N):
        d1 += A[i] > A[j]
    ans = (ans + K*(d1 + d1*K)//2 + (K-1)*(d0 + d0*(K - 1))//2)%MOD

print(ans)

Submission status: Accepted

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

n, k = map(int, input().split())
a = list(map(int, input().split()))
a = a + a
#print(a)
l = [0 for _ in range(2*n)]
for j in range(1, 2 * n):
	cnt = 0
	for i in range(j):
		if a[i] > a[j]:
			cnt += 1
	l[j] = cnt
base = sum(l[:n])
inc = sum(l[n:])
inc -= base
if k == 1:
	print(base)
else:
	print((base * k + inc * k * (k - 1) // 2) % (int(1e9 + 7)))

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
c = 0
mod = (int)(1e9+7)
num = [0 for _ in range(2001)]
for v in a:
  num[v]+=1
for i in range(1,2001):
  num[i]+=num[i-1]
s = set(a)
for v in s:
  c += (num[v]-num[v-1])*num[v - 1]
nn = k-1
if (nn%2==0):
  mul = int((nn//2)*(nn-1))
  mul+=nn
else:
  mul = (nn//2 +1)*nn
now = mul*c
now%=mod
total = 0
for i in range(n-1):
  for j in range(i+1,n):
    if a[i]>a[j]:
      total+=1
total*=k
total%mod
final = total+now
print(final%mod)

Submission status: Accepted

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

for i in range(N):
    for j in range(i+1,N):
        if A[i]>A[j]:
            res_p += 1
        if A[-i-1]>A[-j-1]:
            res_n += 1
res = (K * res_p)
res += (res_p + res_n) * (K * (K-1) // 2)
print(int(res % P) )

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

Submission status: Accepted

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

a=list(map(int,input().split()))
tentou1=0
for i in range(len(a)):
  for j in range(i+1,len(a)):
    if(a[i]>a[j]):
      tentou1+=1
a.sort()
a.reverse()
stentou=0
for i in range(len(a)):
  for j in range(i+1,len(a)):
    if(a[i]>a[j]):
      stentou+=1
answer=tentou1*K + stentou*K*(K-1)//2
print(answer%1000000007)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
N,K =map(int,input().split())
a = list(map(int,input().split()))
# print(a*K)
count = 0
dis = 0
mod = (10**9+7)
for i in a:
    for k in a:
        if k < i:
            count +=1
        count %= mod
for i in range(N):
    for k in a[i:]:
        if k<a[i]:
            dis += 1
        dis %= mod
print(int((K * dis + K * (K - 1) * count // 2) % mod))

Submission status: Accepted

Solution code:
import numpy as np
count = np.count_nonzero
N, K = list(map(int, input().split()))
A = np.array(list(map(int, input().split())))
div = 1000000007
s = 0
s2 = 0
for i, n in enumerate(A):
    tmp = A < n
    s += count(tmp[i+1:])
    s2 += count(tmp)

print(((s * K) + (s2 * (K-1) * K // 2)) % div)

Submission status: Accepted

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

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

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

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

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

# external inversion
Y = -X
for i, p in enumerate(A):
    bit.add(p, 1)
    Y += i + N + 1 - bit.sum(p)

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

Submission status: Accepted

Solution code:
MOD = 10**9 + 7

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

numInvs = [0] * N
for i, Ai in enumerate(As):
    for Aj in As[i+1:]:
        if Ai > Aj:
            numInvs[i] += 1

nums = [0] * N
for i, Ai in enumerate(As):
    for Aj in As:
        if Ai > Aj:
            nums[i] += 1

ans = 0
for numInv, num in zip(numInvs, nums):
    ans += numInv*K % MOD
    ans += num*K*(K-1)//2 % MOD
    ans %= MOD

print(ans)

Submission status: Accepted

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

a=list(map(int,input().split()))
tentou1=0
for i in range(len(a)):
  for j in range(i+1,len(a)):
    if(a[i]>a[j]):
      tentou1+=1
a.sort()
a.reverse()
stentou=0
for i in range(len(a)):
  for j in range(i+1,len(a)):
    if(a[i]>a[j]):
      stentou+=1
answer=int(tentou1*K + int(stentou*K*(K-1)//2))
print(answer%1000000007)

Submission status: Accepted

Solution code:
import numpy as np
N, K = list(map(int, input().split()))
A = np.array(list(map(int, input().split())))
div = 1000000007
s = 0
s2 = 0
for i, n in enumerate(A):
    tmp = A < n
    s += np.count_nonzero(tmp[i+1:])
    s2 += np.count_nonzero(tmp)

print(((s * K) + (s2 * (K-1) * K // 2)) % div)

Submission status: Accepted

Solution code:
# kleene Inversion

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

ca = 0
cb = 0

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

count = ca * k + cb * (k*(k-1))//2
print(count % _mod)

Submission status: Accepted

Solution code:
# kleene Inversion

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

ca = 0
cb = 0

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

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

count = ca * k + cb * (k*(k-1))//2
print(count % _mod)

Submission status: Accepted

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

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

mod = 10**9+7
li = [0]*n
li2 = [0]*n

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

print((sum(li2)*k+sum(li)*(k-1)*k//2)%mod)

Submission status: Accepted

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

MOD = 10**9 + 7

ansR = 0
ansL = 0

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

ans = ansR*(k+1)*k//2%MOD + ansL*(k-1)*k//2%MOD

print(int(ans%MOD))

Submission status: Accepted

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

Submission status: Accepted

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

mod = 10**9 + 7
intra, inter = 0, 0
for i in range(N):
    ai = A[i]
    for j in range(i, N):
        aj = A[j]
        if ai > aj:
            intra += 1
    for j in range(i + 1):
        aj = A[j]
        if ai > aj:
            inter += 1

ans = (intra * K * (K + 1) // 2) % mod
ans += (inter * (K - 1) * K // 2) % mod
print(ans % mod)

Submission status: Accepted

Solution code:
import numpy as np
N, K   = map(int, input().split())
A=np.array(list(map(int, input().split())))
right=[]
left=[]
for i in range(N):
    right.append(np.count_nonzero(A[i:] < A[i]))
    left.append(np.count_nonzero(A[:i] < A[i]))
ans=sum(right)*(K*(1+K)//2)+sum(left)*((K-1)*K//2)
print(ans%(10**9+7))

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = [int(i) for i in input().split()]
g = {}
ans = 0
for i, a in enumerate(A):
    g[a] = N
    for j, b in enumerate(A):
        if a < b:
            g[a] -= 1
        if  i < j and a > b:
            ans += 1

ans = ans * K
S = (K * (K-1))//2
m = 10**9 + 7
for v in A:
    i = g[v]
    ans += S * (N - i) % m

print(ans % m)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
#1行で複数入力
input_list=list(map(int,input().split()))

#数列全体で自分より小さい数がいくつあるか
all_value = {i:0 for i in input_list}
for i in set(input_list):
    for j in input_list:
        if i> j:
            all_value[i]+=1

            
first_value = {i:0 for i in range(len(input_list))}

for i in range(len(input_list)-1):
    for j in range(i,len(input_list)):
        if input_list[i]>input_list[j]:
            first_value[i]+=1


# all_valueが公差
# first_valueがしょこう

count=0
for pos,i in enumerate(input_list):
    count += first_value[pos]*K+all_value[i]*(K-1)*K//2

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

Submission status: Accepted

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

    def __iter__(self):
        psum = 0
        for i in range(self.size):
            csum = self.sum(i+1)
            yield csum - psum
            psum = csum
        raise StopIteration()

    def __str__(self):  # O(nlogn)
        return str(list(self))

    def sum(self, i):
        # [0, i) の要素の総和を返す
        s = 0
        while i>0:
            s += self.tree[i]
            i -= i & -i
        return s

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

    def __getitem__(self, key):
        return self.sum(key+1) - self.sum(key)

    def __setitem__(self, key, value):
        # 足し算と引き算にはaddを使うべき
        self.add(key, value - self[key])

mod = 10**9+7
N, K = map(int, input().split())
A = list(map(int, input().split()))
bit = Bit(max(A)+1)
ans = 0
for i, a in enumerate(A):
    ans += i - bit.sum(a+1)
    bit.add(a, 1)
ans *= K
from itertools import combinations
cnt = 0
for a, b in combinations(A, 2):
    if a!=b:
        cnt += 1
cnt *= K*(K-1)//2
ans += cnt
print(ans%mod)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

MOD = 10 ** 9 + 7

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

a_single = 0
a_multi = 0

for i, ai in enumerate(a):
    for j, aj in enumerate(a):
        if ai > aj:
            a_multi += 1
            if j > i:
                a_single += 1

ans = 0
ans = (a_single * k % MOD + ans) % MOD
ans = (k * (k - 1) // 2 % MOD * a_multi % MOD + ans) % MOD

print(ans)

Submission status: Accepted

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

mod = 10**9+7


rightlist = [0 for i in A_list]
alllist = [0 for i in A_list]

for i in range(len(A_list)):
    ct1 = 0
    ct2 = 0
    a = A_list[i]
    right = A_list[i:]
    
    for j in right:
        #print(a,j)
        if a > j:
            ct1+=1
    
    for j in A_list:
        if a > j:
            ct2+=1
    rightlist[i] = ct1
    alllist[i] = ct2


R = int(sum(rightlist))
A  =int(sum(alllist))
K = int(K%mod)
R = int(R%mod)
A = int(A%mod)

ans = int(int(R*K)+A*int(K*(K-1)//2))
print(ans%mod)

Submission status: Accepted

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

tmp_list = [0]*n
for i in range(n):
    cnt = 0
    for a in a_list:
        if a_list[i] > a:
            cnt += 1
    tmp_list[i] = cnt
res = k * (2*count + sum(tmp_list) * (k-1)) // 2 
print(res % (10**9+7))

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

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

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

x = 0
y = 0

n, k = an()
a = list(an())

mod = int(1e9)+7
ans = 0

for i, ai in enumerate(a):
  for j in range(i+1, n):
    if ai > a[j]:
      x += 1
  
  for j in range(i+1):
    if ai > a[j]:
      y += 1

ans += x * f(k)
ans += y * f(k - 1)
print(ans % mod)

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

cnt = cnt % MOD

cnt2 = 0

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

    cnt2 = cnt2 % MOD

ans = cnt*K + cnt2*((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()))

AA = A + A

AA_re = list(reversed(AA))
A_re = list(reversed(A))

ans0 = 0
for i in range(N):
    a = A_re[i]
    for j in range(i + 1, N):
        b = A_re[j]
        if a < b:
            ans0 += 1


ans1 = 0
for i in range(N):
    a = AA_re[i]
    for j in range(i + 1, 2 * N):
        b = AA_re[j]
        if a < b:
            ans1 += 1


sa = ans1 - ans0
m = 10 ** 9 + 7
matu = ans0 + sa * (K - 1)
ans = (ans0 + matu) * K // 2

if K == 0:
    print(int(ans0))
    exit()

ans = ans % m


print(int(ans))

Submission status: Accepted

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

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

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

ans = t1 * k + t2 * 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()))

AA = A + A

AA_re = list(reversed(AA))
A_re = list(reversed(A))

ans0 = 0
for i in range(N):
    a = A_re[i]
    for j in range(i + 1, N):
        b = A_re[j]
        if a < b:
            ans0 += 1


ans1 = 0
for i in range(N):
    a = AA_re[i]
    for j in range(i + 1, 2 * N):
        b = AA_re[j]
        if a < b:
            ans1 += 1


sa = ans1 - ans0
m = 10 ** 9 + 7


matu = ans0 + sa * (K - 1)
c = ans0 + matu

ans = c * K // 2

if K == 0:
    print(int(ans0))
    exit()

ans = ans % m


print(int(ans))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
div = 1000000007
s = 0
ss = 0

for i, a in enumerate(A):
    for j in A[i+1:]:
        if a > j:
            s += 1

for i in A:
    for j in A:
        if i > j:
            ss += 1

print(((s * K) + (ss * K * (K-1) // 2)) % div)

Submission status: Accepted

Solution code:
def main():
    M=10**9+7
    n,k=map(int,input().split())
    r1=k*(k+1)//2%M
    r2=k*(k-1)//2%M
    *a,=map(int,input().split())
    ans=0
    for i,t in enumerate(a):
        tem=0
        for j,u in enumerate(a):
            if u<t:
                if j<i:tem+=r2
                else:tem+=r1
        ans+=tem
        ans%=M
    print(ans)
main()

Submission status: Accepted

Solution code:
M = 10**9+7
import sys
input = sys.stdin.readline
def main():
    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))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
n,k=map(int,input().split())
a=list(map(int,input().split()))
b,c=0,0
mod=10**9+7
for i in range(n):
    for j in range(i+1,n):
        if a[i]>a[j]:
            b+=1
    for j in range(i):
        if a[i]>a[j]:
            c+=1

print((b*k*(k+1)//2+c*(k-1)*k//2)%mod)

Submission status: Accepted

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

MOD = 10**9 + 7

ansR = 0
ansL = 0

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


ansR %= MOD
ansL %= MOD
Rn = (k+1)*k//2%MOD
Ln = (k-1)*k//2%MOD

ans = int(ansR*Rn)%MOD + int(ansL*Ln)%MOD

print(int(ans%MOD))

Submission status: Accepted

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

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

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

ans = k * ans1 + k * (k-1) // 2 * ans2
ans %= 10 ** 9 + 7

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

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

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

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

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

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

  print(ans)

main()

Submission status: Accepted

Solution code:
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)

#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 = list(map(int, input().split()))
A = list(map(int, input().split()))
div = 1000000007
s = 0
ss = 0

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

for i in A:
    for j in A:
        if i > j:
            ss += 1

print(((s * K) + (ss * K * (K-1) // 2)) % div)

Submission status: Accepted

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

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

mod=10**9+7

print((k*(k+1)*rcount+k*(k-1)*lcount)//2%mod)

Submission status: Accepted

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

Submission status: Accepted

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

for i in range(N):
    for j in range(i+1,N):
        if A[i]>A[j]:
            res_p += 1
        if A[-i-1]>A[-j-1]:
            res_n += 1
res = (res_p + res_n) * K * (K+1) // 2 - (K * res_n)


print(res % P)

Submission status: Accepted

Solution code:
INF = 1000000007

n, k = map(int, input().split())
a = list(map(int, input().split()))
sum1 = 0
sum2 = 0
for i in range(n):
    for j in range(n):
        if i == j:
            continue    
        if a[i]>a[j]:
            if i <j:
                sum1+=1
            else:
                sum2 +=1
ans = sum1+sum2
x = sum1*k
y = ans *((k*(k-1))//2)
print(int((x+y)%INF))

Submission status: Accepted

Solution code:

# https://atcoder.jp/contests/jsc2019-qual/tasks/jsc2019_qual_b

import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop

def main():
    n, k = map(int, input().split())
    al = list(map(int, input().split()))
    down1 = 0
    for i in range(n-1):
        for j in range(i+1,n):
            if al[i] > al[j]:
                down1 += 1

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

    mod = 10**9 + 7
    print((down1 * k + down2 * k * (k - 1) // 2) % mod)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# coding: utf-8

list1 = input().split()
list2 = input().split()
N = int(list1[0])
K = int(list1[1])
a = [int(i) for i in list2]

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

res = ((cnt_l * K * (K+1) // 2) + (cnt_r * (K-1) * K //2)) % (10**9 + 7)

print(int(res))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    def c(x,y):
        if x > y:
            return 1
        else:
            return 0
    n,k = map(int,input().split())
    x = 1000000007
    kk = int(k*(k-1)//2)%x
    a = list(map(int,input().split()))
    c1 = []
    c2 = []
    for i in range(n):
        l = [c(a[i],p) for p in a]
        c1.append(sum(l))
        c2.append(sum(l[i:]))
    ans = ((sum(c1)%x)*kk)%x+((sum(c2)%x)*k)%x
    print(ans%x)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, Counter, deque
from itertools import accumulate, permutations, combinations
from operator import itemgetter
from bisect import bisect_left, bisect_right, bisect
from heapq import heappop, heappush
from fractions import gcd
from math import ceil, floor, sqrt, cos, sin, pi, factorial
from copy import deepcopy

# If you use recursive call, uncomment this code
#sys.setrecursionlimit(10**6)

MOD = 10**9+7

class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )

def main():
    N,K = map(int, input().split())
    aa = list(map(int, input().split()))
    ans = ModInt(0)

    # inside aa
    tmp = 0
    for i in range(N):
        for j in range(i,N):
            if i == j:
                continue
            if aa[i]>aa[j]:
                tmp += 1
    ans += tmp * K

    # between two aa
    tmp = 0
    for i in range(N):
        for j in range(N):
            if aa[i]>aa[j]:
                tmp += 1
    ans += tmp * (K*(K-1)//2)
    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
ans = 0
fflag = 0
bflag = 0

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

ans = ((fflag+bflag)*k*(k+1)//2 - fflag*k)%mod
print(ans)