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:
from collections import Counter

N, K = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7
A_sort0 = sorted(A)
A_sort = sorted(list(set(A)))
counter = Counter(A)
ans = 0
for i in range(len(A_sort)):
    if i == 0:
        continue
    else:
        q = A_sort0.index(A_sort[i])
        ans += (q * (K * (K-1) // 2) * counter[A_sort[i]])  % MOD
        index = A.index(A_sort[i])
        cnt = 0
        p = 0
        for j in range(index, N):
            if A_sort[i] > A[j]:
                cnt += 1 * p
            elif A_sort[i] == A[j]:
                p += 1
        ans = (ans + (cnt * K)) % MOD
print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
A = list(map(int, input().split()))
mod = pow(10,9)+7
ans_p1 = 0
for i in range(n):
    ans_p1 += sum([bool(A[i]>A[j]) for j in range(i+1,n)])

ans_p2 = 0
for i in range(n):
    ans_p2 += sum([bool(A[i]>A[j]) for j in range(n)])
print((ans_p1*k+ans_p2*k*(k-1)//2)%mod)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
M = 10**9+7
from collections import defaultdict

d = defaultdict(int)

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

            if i < j:
                lcl_cnt += 1

ans = lcl_cnt * K

for _, v in d.items():
    ans += (K-1)*v*K//2%M
    
print(ans%M)

Submission status: Accepted

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

mod = 10**9 + 7

# そもそも超えている
already = 0
for i in range(N):
    for j in range(i + 1, N):
        if (i == j):
            continue
        if (A[i] > A[j] and i < j):
            already += 1
already_count = already * K

L = []
L.extend(A)
L.extend(A)
count = 0
for i in range(len(L)):
    for j in range(i + 1, len(L)):
        if (i == j):
            continue
        if (L[i] > L[j] and i < j):
            count += 1
inc = count - (already * 2)

tousa_sum = ((K - 1) * (1 + (K - 1))) // 2
print((inc * tousa_sum + already_count) % mod)

Submission status: Accepted

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

def main(n,k,a):
    MOD=10**9+7

    t=0
    for i in range(n-1):
        for j in range(i+1,n):
            if a[i]>a[j]:
                t+=1
    
    s=0
    for i in range(n):
        for j in range(n):
            if a[j]<a[i]:
                s+=1
    
    x= ( (k*t)%MOD + ((k*(k-1)//2)%MOD)*s%MOD  )%MOD

    return x

if __name__=='__main__':
    n,k,a=readinput()
    ans=main(n,k,a)
    print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#https://scrapbox.io/pocala-kyopro/B_-_Kleene_Inversion
MOD = 1000000007
N,K = map(int,input().split())
A = list(map(int, input().split()))
ans = 0
for i in range(N):
    migi = 0
    zentai = 0
    for j in range(i,N):
        if A[i] > A[j]:
            migi += 1
    for j in range(N):
        if A[i] > A[j]:
            zentai += 1
            
    ans += migi * K % MOD
    ans %= MOD
    ans += (K-1)*K//2 % MOD * zentai % MOD
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
mod=10**9+7
n,k=map(int,input().split())
k1=(k*(k+1)//2)%mod
k2=(k*(k-1)//2)%mod
a=list(map(int,input().split()))
p=0
for i,j in enumerate(a):
    e=0
    for m in a[i:]:
        e+=j>m
    p=(p+(e*k1)%mod)%mod
for i,j in enumerate(a):
    e=0
    for m in a[:i]:
        e+=j>m
    p=(p+(e*k2)%mod)%mod
print(p)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
A=[int(i) for i in input().split()]
MOD = 10**9 + 7

def tent(a):
    t = len(a)
    res = 0
    for i in range(t-1):
        for j in range(i+1,t):
            if(a[i]>a[j]):
                res+=1
    return res
t1 = tent(A)
t2 = tent(A+A)-2*t1
ans = (t1*k%MOD + t2*(k*(k-1))//2%MOD)%MOD
print(ans)

Submission status: Accepted

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

MOD = 10**9 + 7


B = [0] * N

for i in range(len(A)-1):
    cnt = 0
    for j in range(i+1, len(A)):
        if A[j] < A[i]:
            cnt += 1
    B[i] = cnt
# print(B)


C = [0] * N

for i in range(len(A)):
    cnt = 0
    for j in range(len(A)):
        if j != i:
            if A[i] > A[j]:
                cnt += 1
    C[i] = cnt
# print(C)    

D = []
for i in range(N):
    tmp = B[i] * K + C[i] * K * (K-1) // 2 
    D.append(tmp % MOD)
print(sum(D)% MOD)

Submission status: Accepted

Solution code:
def m():
    MOD = 10 ** 9 + 7
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    if len(A) == 1:
        return 0
    l2r = 0
    for i in range(N):
        prev = A[i]
        for j in range(i, N):
            if prev > A[j]:
                l2r += 1
    r2l = 0
    for i in range(N - 1, -1, -1):
        prev = A[i]
        for j in range(i, -1, -1):
            if prev > A[j]:
                r2l += 1

    ans1 = K * (K + 1) // 2 * l2r % MOD
    ans2 = (K - 1) * K // 2 * r2l % MOD
    return (ans1 + ans2) % MOD


print(m())

Submission status: Accepted

Solution code:
n,k,*a = map(int,open(0).read().split())
mod = 10**9+7
t1 = 0
for i in range(n-1):
  for j in range(i+1,n):
    if a[i]>a[j]:
      t1+=1
t2 = 0
c = 0
for i in sorted(list(set(a))):
  dc = a.count(i)
  t2 += c*dc
  c += dc
print((t1*k+t2*k*(k-1)//2)%mod)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
mod=1000_000_000+7
l=[0]*n
r=[0]*n
total=[0]*n
for i in range(n):
    for j in range(n):
        if a[i]>a[j]:
            if i>=j:
                l[i]+=1
            else:
                r[i]+=1
            total[i]+=1


ans=0

for i in range(n):
    ans+=(total[i]*k*(k+1))//2 
    ans-=k*l[i]

print(ans%mod)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = [int(x) for x in input().split()]
b = [sorted(a).index(a[i]) for i in range(n)]
p = [b[i] * (k*(k+1)//2)for i in range(n)]
q = [0] * n
for i in range(n):
    num = 0
    for j in range(i,n):
        if a[j] > a[i]:
            num += 1
    q[i] = num
ans = sum(p)-sum(q)*k
print(ans%1000000007)

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, *A = map(int, open(0).read().split())
    tree = BIT(2000)
    x = 0
    for i, a in enumerate(A, 1):  # internal inversion
        tree.add(a, 1)
        x += i - tree.sum(a)
    y = -x
    for i, a in enumerate(A, 1):  # external inversion
        tree.add(a, 1)
        y += i + N - tree.sum(a)
    MOD = 10 ** 9 + 7
    print((x * K + y * K * (K - 1) // 2) % MOD)


if __name__ == "__main__":
    main()

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:
# B - Kleene Inversion
from typing import Optional, Sequence


class BinaryIndexedTree:
    """Binary Indexed Tree (Fenwick Tree)
    Each operation runs in O(logN).

    References:
        http://hos.ac/slides/20140319_bit.pdf
    """

    __slots__ = ["_size", "_tree", "is_zero_origin"]

    def __init__(
        self,
        size: int,
        initial_values: Optional[Sequence[int]] = None,
        is_zero_origin: bool = True,
    ):
        self._size = size
        self._tree = [0] * (size + 1)
        self.is_zero_origin = is_zero_origin
        if initial_values:
            self._build(initial_values)

    def _build(self, initial_values: Sequence[int]):
        for i, a in enumerate(initial_values):
            self.add(i, a)

    def add(self, index: int, value: int) -> None:
        """Add value to tree[index], O(logN)."""
        if self.is_zero_origin:
            index += 1
        while index <= self._size:
            self._tree[index] += value
            index += index & -index

    def sum(self, index: int) -> int:
        """Return the sum of [1, index] in O(logN)."""
        ret = 0
        while index > 0:
            ret += self._tree[index]
            index -= index & -index
        return ret

    def range_sum(self, left: int, right: int) -> int:
        """Return the range sum of [left, right] in O(logN)."""
        if not self.is_zero_origin:
            left -= 1
        return self.sum(right) - self.sum(left)


def main():
    N, K, *A = map(int, open(0).read().split())
    tree = BinaryIndexedTree(2000, is_zero_origin=False)
    x = 0
    for i, a in enumerate(A, 1):  # internal inversion
        tree.add(a, 1)
        x += i - tree.sum(a)
    y = -x
    for i, a in enumerate(A, 1):  # external inversion
        tree.add(a, 1)
        y += i + N - tree.sum(a)
    MOD = 10 ** 9 + 7
    print((x * K + y * K * (K - 1) // 2) % MOD)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import defaultdict

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

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

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

x = ((t)*(k)*(k-1))//2
y = inner*k
print(int((x+y)%mod))

Submission status: Accepted

Solution code:
from collections import defaultdict

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

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

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

x = (t*k*(k-1))//2
y = inner*k
print(int((x+y)%mod))

Submission status: Accepted

Solution code:
from collections import defaultdict
d = defaultdict(int)

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

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

d = sorted(d.items())
outer = 0
cnt = d[0][1]
for k, v in d[1:]:
  outer += cnt * v
  cnt += v
outer *= K*(K-1)//2

print((inner + outer)%(10**9+7))

Submission status: Accepted

Solution code:
N,K = map(int, input().split())
A = list(map(int,input().split()))
t = 0
for i in range(N-1):
  for j in range(N-i-1):
    if A[i] > A[j+i+1]:
      t += 1
u = 0
for i in range(N):
  for j in range(N):
    if A[i]>A[j]:
      u += 1
T = t%(10**9+7)
U = u%(10**9+7)
Z=K*(K-1)//2%(10**9+7)
Y=T*K%(10**9+7)
X=U*Z%(10**9+7)
ans = (Y+X)%(10**9+7)
print(ans)

Submission status: Accepted

Solution code:
N,K = map(int, input().split())
A = list(map(int,input().split()))
t = 0
for i in range(N-1):
  for j in range(N-i-1):
    if A[i] > A[j+i+1]:
      t += 1
u = 0
for i in range(N):
  for j in range(N):
    if A[i]>A[j]:
      u += 1
T = t%(10**9+7)
U = u%(10**9+7)
Z=K*(K-1)//2%(10**9+7)
Y=T*K%(10**9+7)
X=U*Z%(10**9+7)
ans = (Y+X)%(10**9+7)
   
print(ans)

Submission status: Accepted

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

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

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
#from decimal import *

N, K = MAP()

A = LIST()

whole = [0]*N
first = [0]*N

for i in range(N):
	for j in range(N):
		if A[j] < A[i]:
			whole[i] += 1
			if i < j:
				first[i] += 1

ans = 0
for i in range(N):
	ans += (K*first[i]%mod + whole[i]*(K-1)*K//2%mod)%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
inner_cnt = 0
outer_cnt = 0
for i in range(N):
    for j in range(N):
        if A[i] > A[j]:
            outer_cnt += 1
            if j > i:
                inner_cnt += 1
ans = inner_cnt * K
ans %= MOD
ans += outer_cnt * K * (K - 1) // 2
ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
from decimal import Decimal

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

def tosa(a,n,d):
    s = Decimal(n / 2) * (2*a+(n-1)*d)
    return int(s)

if N == 1:
    print(ans)
    exit()

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

d = N*(N-1)//2
print(tosa(ans,K,d-cnt)%mod)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率

def input(): return sys.stdin.readline()[:-1]
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 10**9+7
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    #N = int(input())
    N, K = map(int, input().split())
    A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    count=0
    la=len(A)
    for i in range(0,la-1):
        for j in range(i+1,la):
            ai,aj=A[i],A[j]
            if ai>aj:
                count+=1
    
    asrt=sorted(list(A))
    d=dict()

    rui=0
    for i,a in enumerate(asrt):
        if a in d:
            continue
        else:
            d[a]=i

    ans=(count*K)%mod
    
    for a in A:
        order=d[a]
        ans=(ans+((K*(K-1)//2)%mod*order)%mod)%mod

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
MOD = int(1e9) + 7
N,K = map(int,input().split())
A = list(map(int, input().split()))
ans = 0
inv = pow(2,MOD-2,MOD)
for i in range(N):
    cnt = 0
    for j in range(N):
        if A[i] > A[j]:
            cnt += 1
    ans += (cnt * K * (K-1) * inv) % MOD
    for j in range(i,N):
        if A[i] > A[j]:
            ans += K
            ans %= MOD
    ans %= MOD
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
N,K = IL()
A = IL()
count = 0
for i in range(N):
  for j in range(i+1,N):
    if A[i]>A[j]:
      count += 1
count2 = 0
for i in range(N):
  for j in range(N):
    if A[i]>A[j]:
      count2 += 1
print(((count*K)+(count2*(K-1)*K//2))%MOD)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7

def solve():
    N, K = map(int, input().split())
    A = list((map(int, input().split())))
    
    ans = 0
    for i, ai in enumerate(A):
        left = 0
        right = 0
        for j in range(i):
            if ai > A[j]:
                left += 1
        for j in range(i+1, N):
            if ai > A[j]:
                right += 1
        
        ans += (K*(K+1)*right//2) + (K*(K-1)*left//2)
        
    return ans % MOD
    
print(solve())

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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


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

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[42]:


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


# In[44]:


ans1 = 0
ans2 = 0
for i,a in enumerate(A):
    for j,a_ in enumerate(A):
        if i > j:
            if a > a_:
                ans2 += 1
        if i < j:
            if a > a_:
                ans1 += 1
                ans2 += 1
print((ans1*K + ans2*(K*(K-1)//2))%(10**9+7))


# In[ ]:

Submission status: Accepted

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

num1 = 0
num2 = 0

for i in range(N):
    for j in range(N):
        if i > j:
            if l[i] > l[j]:
                num2 += 1
        if j > i:
            if l[i] > l[j]:
                num1 += 1
                num2 += 1

print((num1 * K + num2 * (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()))
count1 = 0
for i in range(N):
    for j in range(i+1,N):
        if A[i]>A[j]:
            count1 += 1
count2 = 0
for i in range(N):
    for j in range(N):
        if A[i]>A[j]:
            count2 += 1
count1sum = count1*K
count2sum = K*(0+count2*(K-1))//2
print((count1sum+count2sum)%(10**9+7))

Submission status: Accepted

Solution code:
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(i + 1, n):
        if a[i] > a[j]:
            cnt1 += 1

for i in range(n):
    for j in range(n):
        if a[i] > a[j]:
            cnt2 += 1
print(((cnt1 * k + cnt2 * k * (k - 1) // 2)) % (10 ** 9 + 7))

Submission status: Accepted

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

Submission status: Accepted

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

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

cnt_each=0
for i in A:
  for j in A:
    if i>j:
      cnt_each +=1

cnt_A = (K*cnt_self)%p
cnt_B = ((K*(K-1)//2)*cnt_each)%p
ans = (cnt_A+cnt_B)%p

#print(cnt_A,cnt_B)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def inversion(A,N,K,M):
    B = [0 for _ in range(N)]
    C = [0 for _ in range(N)]
    #B[i]:i<j且つA[i]>A[j]を満たすjの個数
    #C[i]:A[i]<A[j]を満たすjの個数
    for i in range(N):
        for j in range(i+1,N):
            if A[i] > A[j]:
                B[i] += 1

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

    output = sum(B) * K
    output += sum(C) * K * (K-1) //2
    output %= M

    return output

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

    print(inversion(A,N,K,M))

if __name__ == "__main__":
    main()