Problem:


Score : 300 points

Problem Statement

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

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

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

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

Constraints

All values in input are integers.

1 \leq N \leq 2000

1 \leq K \leq 10^9

1 \leq A_i \leq 2000

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

2 2
2 1

Sample Output 1

3

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

B_0 > B_1

B_0 > B_3

B_2 > B_3

Thus, the inversion number of B is 3.

Sample Input 2

3 5
1 1 1

Sample Output 2

0

A may contain multiple occurrences of the same number.

Sample Input 3

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

Sample Output 3

185297239

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



Sample input:
2 2
2 1


Sample output:
3

Submission status: Accepted

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

NUM = int(10**9 + 7)

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

count = 0
sorted_nums = sorted(nums)
mult = 1
for i in range(n - 1):
    if sorted_nums[i] < sorted_nums[i + 1]:
        count += (n - i - 1) * mult
        mult = 1
    else:
        mult += 1
res += count * (k - 1) * k // 2
print(res % NUM)

Submission status: Accepted

Solution code:
from bisect import bisect_left

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

num = []
num2 = []
ret = 0
for i in range(N):
    ind = N-1-i
    j = bisect_left(num, A[ind])
    num.insert(j, A[ind])
    ret += j
    
count = 0
a = {}
for i in range(N):
    if A[i] in a:
        a[A[i]] += 1
    else:
        a[A[i]] = 1

ret2 = N * (N-1)//2 - ret
for e in a.values():
    ret2 -= (e * (e-1))//2

ret *= K * (K+1)//2
ret2 *= K * (K-1)//2
ret += ret2
ret %= mod
print(ret)

Submission status: Accepted

Solution code:
MOD = 1000000007
N, K = [int(x) for x in input().split()]
A_list = [int(x) for x in input().split()]
sorted_A_list = sorted(A_list)
ans = 0
for i, A in enumerate(A_list):
    n = sorted_A_list.index(A)
    tmp = ((K * (K-1) * n)//2) % MOD
    for a in A_list[i+1:]:
        tmp += K * (A > a)
    ans = (ans+tmp) % MOD
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = [int(x) for x in input().split()]
p = 10 ** 9 + 7
S = [0] * 2001
D = [0] * 2001
cnt = 0
for i, a in enumerate(A):
  D[a] += 1
  j = a
  r = 0
  while j:
    r += S[j]
    j -= j & -j
  cnt += i - r
  j = a
  while j <= 2000:
    S[j] += 1
    j += j & -j
cnt = cnt * K % p
k = 0
for d in D[::-1]:
  cnt += d * k * K * (K - 1) // 2
  k += d
  cnt %= p
print(cnt)

Submission status: Accepted

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

C = [0] * N
D = [0] * N

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

ans = (K * sum(C) + K * (K-1) // 2 * sum(D)) % (10 ** 9 + 7)
print(ans)

Submission status: Accepted

Solution code:
import sys, math
from collections import deque

readline = sys.stdin.readline

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

P = 10**9 + 7

aL = [0] * N
aR = [0] * N

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

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

ans = 0
for n in range(N):
    x = K * (K - 1) // 2 % P
    ans += x * (aL[n] + aR[n]) + K * aR[n]
    ans %= P

print(ans)

Submission status: Accepted

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


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

mae = [0] * N
ushiro = [0] * N
for i in range(N):
    for j in range(N):
        if i == j: continue
        if j < i and A[i] > A[j]:
            mae[i] += 1
        elif i < j and A[i] > A[j]:
            ushiro[i] += 1

ans = 0
for i in range(N):
    if K >= 2:
        ans += K*(2+(K-1))//2*ushiro[i] + (K-1)*(2+(K-2))//2*mae[i]
    else:
        ans += ushiro[i]


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

Submission status: Accepted

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

print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from fractions import gcd
# import queue
# from collections import Counter
# from itertools import accumulate
# from functools import reduce

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

def combination_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)

big_prime = 1000000007

"""
# 標準入力取得
## 文字列
 =  sys.stdin.readline().rstrip()
 =  list(sys.stdin.readline().rstrip())

## 数値
 =  int(sys.stdin.readline())
 =  map(int, sys.stdin.readline().split())
 =  list(map(int, sys.stdin.readline().split()))
 =  [list(map(int,list(sys.stdin.readline().split()))) for i in range(N)]
"""
# elem 前後で自分未満のものをカウント * K
N, K =  map(int, sys.stdin.readline().split())
L =  list(map(int, sys.stdin.readline().split()))

cnt = 0
for l1 in L:
    for l2 in L:
        if l1 > l2:
            cnt += 1
prev = 0
for i in range(N):
    for j in range(i, -1, -1):
        if L[i] > L[j]:
            prev += 1
if cnt == 0:
    print(0)
else:
    # print((cnt * K * K - K * (K - 1)// 2) % big_prime)
    print((cnt * K * K - cnt * K * (K -1) // 2 - prev * K) % big_prime)

Submission status: Accepted

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

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

print( count )

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import bisect

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

mod = 10**9 + 7

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

ans = reverse * k % mod

if k == 1:
    print(ans)
else:
    k -= 1
    a.sort()
    m = n
    for ai in a:
        i = bisect.bisect_right(a, ai)
        count = n - i
        ans += count * k * (k+1) // 2 % mod
        ans %= mod
    print(ans)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7

def mult(a, b):
  return ((a % MOD) * (b % MOD)) % MOD

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

def solve():
  N, K = map(int, input().split())
  A = [int(i) for i in input().split()]
  n = count_inversion(A)
  m = count_inversion(A * 2) - 2 * n

  return (mult(n, K) + mult(m, (K * (K - 1)) // 2)) % MOD

print(solve())

Submission status: Accepted

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

cnt = 0
pres = []
for a in As:
    for p in pres:
        if p > a:
            cnt += 1
    pres.append(a)

kcnt = 0
for a in As:
    for p in pres:
        if p > a:
            kcnt += 1

if K == 1:
    print(cnt)
else:
    print(((cnt * K) % (10**9 + 7) + (kcnt * (K - 1) * K // 2) % (10**9 + 7)) % (10**9 + 7))

Submission status: Accepted

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

left_under_nums = [0 for i in range(N)]
right_under_nums = [0 for i in range(N)]

for i in range(N):
    for j in range(i+1, N):
        if As[i] > As[j]:
            if j < i: # left
                left_under_nums[i] += 1
            elif j > i: # right
                right_under_nums[i] += 1
        elif As[j] > As[i]:
            if i < j: # left
                left_under_nums[j] += 1
            elif i > j: # right
                right_under_nums[j] += 1

#print(left_under_nums)
#print(right_under_nums)

M = 10 ** 9 + 7

out = 0
keisu = (K)*(K-1) // 2
for i in range(N):
    all_num = left_under_nums[i] + right_under_nums[i]
    out += (right_under_nums[i] * K)
    out = out % M
    out += ( all_num * keisu )
    out = out % M

print(out)

Submission status: Accepted

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

t1 = [0]
for i in range(1,N):
    tentou = 0
    for j in range(i):
        if(A[j]>A[i]):
            tentou += 1
    t1.append(tentou)

t2 = []
for i in range(0,N-1):
    tentou = 0
    for j in range(i+1,N):
        if(A[i]<A[j]):
            tentou += 1
    t2.append(tentou)
t2.append(0)

answer=0
for i in range(N):
    answer += t1[i]*K
    answer += (t1[i]+t2[i])*K*(K-1)//2

print(answer % 1000000007)

Submission status: Accepted

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


from collections import Counter
c = Counter(a)
keys = list(c.keys())
keys.sort()
tmp1 = 0
tmpsum = 0
for key in keys:
    tmp1 += c[key] * tmpsum
    tmpsum += c[key]

tmp2 = 0
counter = [0] * 2000
for _a in reversed(a):
    if _a > 1:
        tmp2 += sum(counter[:_a-1])
    counter[_a-1] += 1

print((tmp1 * (k-1) * k // 2 + tmp2 * k) % (10 ** 9 + 7))

Submission status: Accepted

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

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

ans = 0

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

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

Submission status: Accepted

Solution code:
n, k = list(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

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

Submission status: Accepted

Solution code:
from collections import Counter

mod = 10 ** 9 + 7
N, K = map(int, input().split())
A = list(map(int, input().split()))
L = [0] * (max(A) + 1)
ans = 0
for i in A[::-1]:
    L[i] += 1
    ans += sum(L[:i])
Cnt = dict([(0, 0)])
for i in range(1, len(L)):
    Cnt[i] = L[i] + Cnt[i - 1]
ans = ans * K % mod
for i in A:
    ans = (ans + Cnt[i - 1] * (K - 1) * K // 2) % mod
print(ans)

Submission status: Accepted

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

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

mod = 10**9+7
ans = 0
for i in range(n):
  a = 0
  b = 0
  for j in range(n):
    if j < i and ls[j] < ls[i]:
      a += 1
    if  ls[j] < ls[i]:
      b += 1
  a = b-a
  ans += (a+b*k)*k-b*(1+k)*k//2
  
  ans %= mod
print(ans)

Submission status: Accepted

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

count_left = [0 for i in range(n)]
count_right = [0 for i in range(n)]

for i in range(len(A)):
    for j in range(i):
        if A[i] < A[j]:
            count_left[i] += 1
    
    for j in range(i + 1, n):
        if A[i] < A[j]:
            count_right[i] += 1

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

Submission status: Accepted

Solution code:
# a = int(input())
# n, *a = map(int, open(0))
N, K = map(int, input().split())
A = list(map(int, input().split()))
# S = input()
A_memo = []
for i in range(N):
    tmp = [0, 0]
    for j in range(N):
        if A[i] > A[j]:
            if j < i:
                tmp[0] += 1
            else:
                tmp[1] += 1
    A_memo.append(tmp)

cnt = 0
for i in range(N):
    cnt += A_memo[i][0] * (K-1)*(K)//2 + A_memo[i][1] * (K+1)*(K)//2

print(int(cnt % 1000000007))

Submission status: Accepted

Solution code:
"""
N = int(input())
A, B = map(int,input().split())
lst = [list(map(int,input().split())) for i in range(M)]
A = list(map(int,input().split()))
"""

import bisect

mod = int(1e9+7)

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

A_sorted = sorted(A)


left = []
total = []
for i in range(N):
  left_i = bisect.bisect_left(sorted(A[:i+1]), A[i])
  total_i = bisect.bisect_left(A_sorted, A[i])
  left.append(left_i)
  total.append(total_i)
  
#print(left)
#print(total)

ans = 0
for i in range(N):
  ans += ((K-1)*K//2 % mod) * left[i]
  ans += (K*(K+1)//2 % mod) * (total[i] - left[i])
  ans = 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()))

r = [[]] * n
for i in range(n):
  r[i] = [len([x for x in a[:i] if a[i] > x]), len([x for x in a[i+1:] if a[i] > x])]

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

Submission status: Accepted

Solution code:
import sys
from itertools import combinations
N, K = [int(i) for i in sys.stdin.readline().split()]
a_ls = [int(i) for i in sys.stdin.readline().split()]
lbt = 0
rbt = 0
for combi in combinations(a_ls,2):
    if combi[0] > combi[1]:
        lbt += 1
    elif combi[1] > combi[0]:
        rbt += 1
cnt = 0
cnt += lbt * int(K * (K-1) // 2 + K)
cnt += rbt * int(K * (K-1) // 2)
cnt %= (10 ** 9 + 7)
print(cnt)

Submission status: Accepted

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

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

Submission status: Accepted

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

a_sort = sorted(a)

ans = 0
for i in range(n):
    a_back = a[i:]
    a_back.sort()
    x = a_sort.index(a[i])
    y = a_back.index(a[i])
    ans += k*(k-1)*x//2+ + k*y
    ans %= MOD

print(ans)

Submission status: Accepted

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

ans=0

for i in range(N):
    first_num = len([x for x in A[i+1:] if A[i]>x])
    roop_num = len([x for x in A if A[i]>x])
    ans += first_num*K
    ans += roop_num*(K*(K-1))//2

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

print(str(ans))

Submission status: Accepted

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

Submission status: Accepted

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

s = k * ((k - 1) // 2)
if (k - 1) % 2 != 0:
    s += (k - 1) // 2 + 1

res = 0
for i in range(n):
    for j in range(n):
        if j == i:
            continue
        if a_list[i] > a_list[j]:
            if i < j:
                res += s + k
            else:
                res += s

res %= mod
print(int(res))

Submission status: Accepted

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

right = [0] * N
left = [0] * N

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


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

ans = 0
for i in range(N):
    ans += K * (1 + K) // 2 * right[i] % MOD
    ans += (K - 1) * K // 2 * left[i] % MOD
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
from itertools import permutations,groupby
import sys
import bisect
import string
alp=string.ascii_lowercase
sys.setrecursionlimit(10**6)
def SI():
    return input().split()
def MI():
    return map(int,input().split())
def I():
    return int(input())
def LI():
    return [int(i) for i in input().split()]
YN=['Yes','No']
mo=10**9+7
#mo=998244353
#input=sys.stdin.readline

n,k=MI()
a=LI()
c=[0]*(2000+10)
t=[0]*(2000+10)
for i in range(n):
    c[a[i]]+=1
    tmp=0
    for j in range(i):
        tmp+=1 if a[j]>a[i] else 0
    t[i]=tmp

A=[0]
for i in c:
    A+=[i+A[-1]]
q=0
for i in range(n):
    q+=A[a[i]]
#q=sum(A[:-1])
q%=mo
q*=k*(k-1)//2
q%=mo

ans=k*sum(t)%mo
ans+=q
print(ans%mo)
#print(c,A,t,ans%mo)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
#B
import sys
#sys.setrecursionlimit(100000)

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

tmp = input().split()
a = list(map(lambda a: int(a), tmp))

b=[]
c=[]
for i in range(0,n):
	b.append(0)
	c.append(0)

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

sum=0
tmp=0
for i in range(0,n):
	sum+=b[i]
	tmp+=c[i]
sum*=k
sum+=tmp*k*(k-1)//2

sum%=1000000007

#print(tmp)
print(sum)

#print(a)
#print(b)
#print(c)