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:
def main():
  
  n,k=map(int,input().split())
  a=tuple(map(int,input().split()))
  
  count=lambda arr,now:sum(element<now for element in arr)
  
  ans=0
  prime=10**9+7
  
  for i in range(n):
    left=count(a[:i],a[i])
    right=count(a[i+1:],a[i])
    res=(k-1)*k//2*(right+left)+right*k
    ans+=res%prime
    
  print(ans%prime)

if __name__=="__main__":
  main()

Submission status: Accepted

Solution code:
def main():
  
  n,k=map(int,input().split())
  a=list(map(int,input().split()))
  
  count=lambda arr,now:sum(element<now for element in arr)
  
  ans=0
  prime=10**9+7
  
  for i in range(n):
    left=count(a[:i],a[i])
    right=count(a[i+1:],a[i])
    res=(k-1)*k//2*(right+left)+right*k
    ans+=res%prime
    
  print(ans%prime)

if __name__=="__main__":
  main()

Submission status: Accepted

Solution code:
def main():
  
  n,k=map(int,input().split())
  a=list(map(int,input().split()))
  
  count=lambda arr,now:sum(element<now for element in arr)
  b=[[count(a[:i],a[i]),count(a[i+1:],a[i])] for i in range(n)]

  ans=0
  prime=10**9+7
  
  for x in b:
    left=x[0]
    right=x[1]
    res=(k-1)*k//2*(right+left)+right*k
    ans+=res%prime
    
  print(ans%prime)

if __name__=="__main__":
  main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = [int(i) for i in input().split()]
mod = 10**9+7
x = 0
y = 0

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

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

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = [int(i) for i in input().split()]
ans = 0
m = max(a)+2
cnt1 = [0]*m
cnt2 = [0]*n
mod = 10**9+7

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

for i in range(1,len(cnt1)):
    cnt1[i] += cnt1[i-1]

for i in range(n):
    ans = (ans + cnt1[a[i]]*(k*(k-1))//2%mod + cnt2[i]*k%mod)%mod

print(ans)

Submission status: Accepted

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

P = 10**9+7

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

K1 = (K*(K+1)//2)%P
K2 = (K*(K-1)//2)%P

ans = (ans1*K1+ans2*K2)%P

print(ans)

Submission status: Accepted

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

P = 10**9+7

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

K1 = (K*(K+1)//2)%P
K2 = (K*(K-1)//2)%P

ans = (ans1*K1+ans2*K2)%P

print(ans)

Submission status: Accepted

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

P = 10**9+7

ans = 0
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        if A[i] > A[j]:
            if i < j:
                ans += K*(K+1)//2
                ans %= P
            else:
                ans += K*(K-1)//2
                ans %= P
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


class PriorityQueue:
    def __init__(self, l=[]):
        self.__q = l
        heapq.heapify(self.__q)
        return

    def push(self, n):
        heapq.heappush(self.__q, n)
        return

    def pop(self):
        return heapq.heappop(self.__q)


MOD = int(1e09) + 7
INF = int(1e15)


def calc(N):
    return sum(int(x) for x in str(N))


def main():
    # sys.stdin = open("sample.txt")
    N, K = Scanner.map_int()
    A = Scanner.map_int()
    ans = 0
    for i in range(N):
        c = 0
        for j in range(i):
            if A[i] > A[j]:
                c += 1
        ans += ((K - 1) * (K) // 2) * c
        ans %= MOD
        c = 0
        for j in range(i+1, N):
            if A[i] > A[j]:
                c += 1
        ans += (K * (K + 1) // 2) * c
        ans %= MOD
    print(ans)
    return


if __name__ == "__main__":
    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):
  rightsmallcnt = 0
  for j in range(i+1, n):
    if a[i] > a[j]:
      rightsmallcnt += 1
  allsmallcnt = 0
  for j in range(n):
    if a[i] > a[j]:
      allsmallcnt += 1
  cnt += rightsmallcnt * k + allsmallcnt * (((k-1)**2+(k-1))//2)
print(cnt % (10**9+7))

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
Alist = list(map(int, input().split()))
ans = 0

for i in range(N):
    a, b = 0, 0
    A = Alist[i]
    for j in range(N):
        if Alist[j] < A:
            b += 1
            if j > i:
                a += 1
    ans += a * K + b * (K**2 - (K * (K + 1)) // 2)
    # print(i, A, a, b)
print(ans % (10**9 + 7))

Submission status: Accepted

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

for i in range(n-1):
  for j in range(i+1, n):
    if a[i] > a[j]:
      t += 1
      
a.sort()
l = [ i for i in range(n) ]
for i in range(1, n):
  if a[i] == a[i-1]:
    l[i] = l[i-1]
s = sum(l)
    
print((k*t%1000000007 + s*k*(k-1)//2%1000000007)%1000000007)

Submission status: Accepted

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

for i in range(n-1):
  for j in range(i+1, n):
    if a[i] > a[j]:
      t += 1
      
a.sort()
l = [ i for i in range(n) ]
for i in range(1, n):
  if a[i] == a[i-1]:
    l[i] = l[i-1]
s = sum(l)
    
print((k*t%1000000007 + s*k*(k-1)//2%1000000007)%1000000007)

Submission status: Accepted

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

cnt=0
a=a*2
l=[[0,0] for i in range(n)]
for i in range(n):
    for j in range(i+1,n+i):
        if a[i]>a[j] and j<=n-1:
            l[i][0]+=1
        elif a[i]>a[j] and j>n-1:
            l[i][1]+=1

for i in range(n):
    num=l[i][0]
    num1=l[i][1]
    cnt+=num*k*(k+1)//2+num1*(k-1)*k//2

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

Submission status: Accepted

Solution code:
div = 10 ** 9 + 7

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

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

ans *= K
ans += count * (K - 1) * K // 2
ans %= div

print(ans)

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):
    for j in range(n):
        if a[i] > a[j]:
            if i < j:
                x += 1
            else:
                y += 1

print((x*(k**2-((k-1)*k//2)) + y*(k**2-((1+k)*k//2))) % (10**9+7))

Submission status: Accepted

Solution code:
import numpy as np
N, K = [int(i) for i  in input().split()]
A= [int(i) for i  in input().split()]
A=np.array(A)
ans =0
for i in range(N):
    ans += np.count_nonzero(A[:i]<A[i])*K*(K-1)//2
    ans += np.count_nonzero(A[i+1:]<A[i])*K*(K+1)//2

print(ans%1000000007)

Submission status: Accepted

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

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

k = K * (K - 1) // 2
res = s * k + t * K
print(res % (10 ** 9 + 7))

Submission status: Accepted

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

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

ans = 0
ans += counter * K
ans += counter2 * (K * (K - 1) // 2)
print(ans % mod)

Submission status: Accepted

Solution code:
import bisect

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

order = sorted(lst)

ans = 0
for i in range(n):
    cnt = 0
    x = lst[i]
    for j in range(i+1,n):
        y = lst[j]
        if x>y:
            cnt += 1
    ans += cnt*k + (k*(k-1)//2)*bisect.bisect_left(order, x)
    ans %= mod
print(ans%mod)

Submission status: Accepted

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

cnt = [[0, 0] for i in range(n)]
for i in range(n):
    a = A[i]
    for af in A[:i]:
        if af < a:
            cnt[i][0] += 1
    for al in A[i:]:
        if al < a:
            cnt[i][0] += 1
            cnt[i][1] += 1

ans = 0
for c in cnt:
    ans += (c[1]*k + c[0]*k*(k-1)//2) % (10**9+7)

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

Submission status: Accepted

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

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

print((inv * K + sma * K * (K - 1) // 2) % MOD)

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]:
      a+=1
for i in range(N):
  for j in range(N):
    if A[i]>A[j]:
      b+=1
a*=K
b*=K*(K-1)//2
a%=(10**9+7)
b%=(10**9+7)
print((a+b)%(10**9+7))

Submission status: Accepted

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

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

Submission status: Accepted

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

cnt = 0
cnt_ = 0
for i in range(n):
  cnt_ += len(list(k for k in a_list if k > a_list[i]))
  for j in range(i+1,n):
    if a_list[i] > a_list[j]:
      cnt += 1

ans = (cnt_) * (k * (k-1) // 2) % MOD + (cnt * k) % MOD

print(ans % MOD)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from itertools import combinations, accumulate
n,m = map(int,input().split())
a = list(map(int,input().split()))
mod = 10**9+7
ans = 0
ls = [0]*2001
for i in a:
  ls[i] += 1
accls = list(accumulate(ls))
for i,j in combinations(a,2):
  if i>j:
    ans += 1
ans = ans*m%mod
for i in range(1,2001):
  if ls[i]>=1:
    ans = (ans + ls[i]*accls[i-1]*m*(m-1)//2)%mod
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
import functools
stdin = sys.stdin
mod = 10**9 + 7

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
sa = lambda h: [list(map(int, stdin.readline().split())) for i in range(h)]

n, k = na()
a = na()
cl = 0
cr = 0
for i in range(n-1):
    for j in range(i+1,n):
        if a[i] < a[j]:
            cl += 1
        if a[i] > a[j]:
            cr += 1
ans = (cr*k %mod + (cl+cr) * k*(k-1)//2) % mod
print(ans)

Submission status: Accepted

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

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

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

inside %= mod
outside %= mod

ans = 0

ans += (inside*k)%mod
ans += ((1+k-1)*(k-1)*pow(2,mod-2,mod)*outside)%mod

print(ans % mod)

Submission status: Accepted

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


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

    x = 0
    for i in range(N-1):
        for j in range(i+1, N):
            if A[i] > A[j]:
                x += 1
    y = 0
    for i in range(N):
        for j in range(N):
            if A[i] > A[j]:
                y += 1
    ans = x * K + y * K * (K-1) // 2
    ans %= mod
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
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 list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n,k = LI()
    a = LI()
    r = 0
    for i in range(n):
        for j in range(i+1,n):
            if a[i] > a[j]:
                r += 1
    r *= k
    r %= mod
    u = [0] * (max(a)+1)
    for c in a:
        u[c] += 1
    for i in range(len(u)-1):
        u[i+1] += u[i]
    kk = (k-1) * k // 2 % mod
    for c in a:
        r += u[c-1] * kk
        r %= mod

    return r


print(main())

Submission status: Accepted

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


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


def inversion(a):
    "転倒数を求める"
    d = {av: i+1 for i, av in enumerate(sorted(a))}
    b = Bit(len(a))
    ans = 0
    for i, av in enumerate(a):
        ans += i-b.sum(d[av])
        b.add(d[av], 1)
    return ans


MOD = 10**9+7
L = len(set(A))

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

Submission status: Accepted

Solution code:
from sys import exit, stdin
N, K = [int(_) for _ in stdin.readline().rstrip().split()]
A = [int(_) for _ in stdin.readline().rstrip().split()]

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

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

Submission status: Accepted

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

onel = []

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

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

ans = 0
for i, j in zip(onel, alll):
   ans += k*i + (k-1)*k*j//2
   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

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

B = sorted(A)[::-1]
ob = 0
t = B[0]
c = 0
for i in range(N):
    if t > B[i]:
        t = B[i]
        c = i
        ob += c
    else:
        ob += c
        
ans = (((ib * K) % mod) + (ob * (((K * (K-1)) // 2) % mod)) % mod) % mod
print(ans)

Submission status: Accepted

Solution code:
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)
    # divisors.sort()
    return divisors
def examA():
    M, D = LI()
    c = D//10
    ans = 0
    for i in range(2,M+1):
        d = make_divisors(i)
#        print(d)
        for j in range(len(d)//2):
            cur0 = d[j*2+1]; cur10 = d[j*2]
            if cur10==1:
                continue
            if cur0<=9:
                if cur10<c:
                    ans +=1
#                    print(cur10,cur0)
                elif cur10==c and cur0+cur10*10<=D:
                    ans +=1
#                    print(cur10,cur0)
        for j in range(len(d) // 2):
            cur0 = d[j * 2];cur10 = d[j * 2+1]
            if cur0 == 1:
                continue
            if cur10 <= 9:
                if cur10 < c:
                    ans += 1
                elif cur10 == c and cur0 + cur10 * 10 <= D:
                    ans += 1
        if len(d)%2==1:
            cur0 = d[-1]; cur10 = d[-1]
            if cur10==1:
                continue
            if cur0<=9:
                if cur10<c:
                    ans +=1
#                    print(cur10,cur0)
                elif cur10==c and cur0+cur10*10<=D:
                    ans +=1
#                    print(cur10,cur0)
    print(ans)
    return

class Bit():
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
        return
    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
        return
def examB():
    N, K = LI()
    A = LI()
    bit = Bit(max(A))
    cur = 0
    for i, a in enumerate(A):
        bit.add(a, 1)
        cur += i + 1 - bit.sum(a)
    As = 0
    A.sort()
    now = 0
    for i in range(1,N):
        if A[i]!=A[i-1]:
            now = i
        As += now
#    print(cur,As)
    ans = (As*(K**2) - (As-2*cur)*K)//2
    ans %=mod
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,inf
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examB()

Submission status: Accepted

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

MOD = 10 ** 9 + 7
in_A, out_A = 0, 0

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

print((in_A * K + out_A * 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
ans = 0

# 普通の転倒数を求める
normal = 0
for i in range(N):
    for j in range(i+1, N):
        if A[i] > A[j]:
            normal += 1
un_normal = 0
for i in range(N):
    for j in range(N):
        if A[i] > A[j]:
            un_normal += 1
print((normal * K + un_normal * K * (K-1) // 2) % mod)

Submission status: Accepted

Solution code:
from collections import defaultdict
from bisect import bisect_left
def bubble_sort(A):
    cnt = 0
    for i in range(len(A)):
        for j in range(len(A)-1, i, -1):
            if A[j] < A[j-1]:
                A[j], A[j-1] = A[j-1], A[j]
                cnt += 1
    return cnt

def main():
    N,K = map(int,input().split())
    A = [int(x) for x in input().split()]
    mod = 10**9 + 7
    
    falls = bubble_sort(A)
    rank = 0
    for i in A:
        rank += bisect_left(A,i)
        
    falls_all = (falls*K)%mod
    rank_all  = ((K*(K-1))//2)%mod
    rank_all  = (rank_all*rank)%mod

    print((falls_all+rank_all)%mod) 
    




if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
mod = int(1e+9 + 7)
c, d = 0, 0
for i in range(N-1):
  for j in range(i+1, N):
    if A[i] > A[j]:
      d += 1
    elif A[i] < A[j]:
      c += 1
kip = ((K * (K + 1)) // 2) % mod
pip = ((K * (K - 1)) // 2) % mod
S = (d * kip) % mod + (c * pip) % mod
S %= mod
print(S)

Submission status: Accepted

Solution code:
import sys
from collections import Counter
from itertools import accumulate, combinations

read = sys.stdin.read
N, K, *A = map(int, read().split())
mod = 10 ** 9 + 7

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

answer = 0

if K > 1:
    b = Counter(A)
    cnt1 = [j for i, j in sorted(b.items())]
    n = list(accumulate(cnt1))
    n = sum(i * j for i, j in zip(cnt1[1:], n[:-1]))

    answer += n * (K * (K - 1) // 2 % mod)
    answer %= mod

answer += cnt * K
answer %= mod
print(answer)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
N, K = map(int,input().split())
A = list(map(int,input().split()))
num1,num2 = 0,0
for i in range(N-1):
  for j in range(i+1,N):
    if A[i]>A[j]: num1 += 1

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

val1 = num1*(K*(K+1)//2)%MOD
val2 = num2*(K*(K-1)//2)%MOD
print((val1+val2)%MOD)

Submission status: Accepted

Solution code:
import numpy as np

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

a = np.array(a)
c = np.sort(a)[::-1]
MOD = 10 ** 9 + 7
count = 1
ans = 0
d = 0
e = 0
for i in a:
    b = a[count:n]
    d += len(c[c < i])
    e += len(b[b < i])
    count += 1

ans = (e * k + k*(k-1)//2 * d)
ans %= MOD

print(int(ans))

Submission status: Accepted

Solution code:
import sys
import numpy as np

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N, K = rl()
MOD = 10 ** 9 + 7
A = np.array(rl())
B = np.array([])
answer = 0
add = 0
for a in A:
    answer += (B > a).sum()
    add += (A > a).sum()
    B = np.append(B, a)
answer *= K
answer %= MOD
time = (K-1) * K // 2 % MOD
answer += add * time
print(answer%MOD)
#50

Submission status: Accepted

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

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

Tinter = 0
B = [l for l in A]
B.extend(B)
for i in range(len(A)):
  temp = A[i]
  for j in range(len(A), len(A)*2):
    if temp > B[j]:
      Tinter += 1

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

Submission status: Accepted

Solution code:
import numpy as np

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

cnt1 = 0
cnt2 = 0
for i in range(n - 1):
    cnt1 += (a[i + 1:] < a[i]).sum()

for i in range(n):
    cnt2 += (a < a[i]).sum()

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

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
mod=10**9+7
count1=0
for i in range(N-1):
    for m in range(i+1,N):
        count1+=A[i]>A[m]



count2=0
for i in range(N-1):
    for m in range(i+1,N):
        count2+=A[i]<A[m]

#print(count1,count2)
count=count1*((K*(K+1)//2)%mod)
count%=mod
count+=count2*(((K-1)*K//2)%mod)
count%=mod


print(count)

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-1):
    for j in range(i+1, n):
        if A[i] > A[j]:
            ans += 1
ans *= k
ans %= MOD

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = [int(i) for i in input().split()]
mod = 10 ** 9 + 7

ret = 0
ca = [0] * (2001)
cb = [0] * (2001)

for i in range(N) :
    ca[A[i]] += 1
    ca[A[i]] %= mod
    
for i in range(2000) :
    ca[i + 1] = (ca[i + 1] + ca[i]) % mod

for i in range(N - 1, -1, -1) :
    ret += K * sum(cb[:A[i]]) + K * (K - 1) * ca[A[i] - 1] // 2
    ret %= mod
    cb[A[i]] += 1
    
print(ret)

Submission status: Accepted

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

MOD = 1000000007  # type: int


def solve(N: int, K: int, A: "List[int]"):
    ## 一つの場合の転倒数を数えていく
    tentousuu = dict()
    all_tentousuu = dict()
    for a in range(0,2001):
        tentousuu[a] = 0
        all_tentousuu[a] = 0 

    for i in range(0,N):
        for j in range(0,N):
            if j<i and A[j]>A[i]:
                tentousuu[A[i]]+=1
            
            if A[i]<A[j]:
                all_tentousuu[A[i]] += 1
    
    one_to_k_sum = (K)*(K-1)//2
    answer = 0
    for a in range(0,2001):
        answer += tentousuu[a]*K+all_tentousuu[a]*one_to_k_sum
    
    print(answer%MOD)
    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 - 1 - 0 + 1)]  # type: "List[int]"
    solve(N, K, A)

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
cnt_lst_before=[0]*n
cnt_lst_after=[0]*n
cnt_a=0
for i in range(n):
    for j in range(n):
        if i<j and a[i]>a[j]:
            cnt_lst_after[i]+=1
        elif i>j and a[i]>a[j]:
            cnt_lst_before[i]+=1
if k==1:
    print(sum(cnt_lst_after))
else:
    print((sum(cnt_lst_after)*(k*(k+1)//2)+sum(cnt_lst_before)*(k*(k-1)//2)%mod)%mod)

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

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

one_tento = 0
for i in range(n-1):
    for j in range(i+1,n):
        if array[i] > array[j]:
            one_tento += 1
one_tento = int(one_tento)

two_tento = 0
for i in range(n):
    for j in range(n):
        if array[i] > array[j]:
            two_tento += 1
two_tento = int(two_tento)

result1 = (one_tento * k) % (7 + 10**9)
result2 = ((two_tento % (7 + 10**9)) * ((k * (k - 1) // 2) % (7 + 10**9))) % (7 + 10 **9)
result3 = (result1 + result2) % (7 + 10**9)
print(int(result3))

Submission status: Accepted

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