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())
data = list(map(int, input().split()))
mod = 10**9 + 7

invs = []
for idx in range(n):
    result = [0,0]
    for idx2 in range(n):
        if idx2 < idx:
            loc = 1
        elif idx2 > idx:
            loc = 0
        else:
            continue
        if data[idx2] < data[idx]:
            result[loc] += 1
    invs.append(result)
ans = 0
for aft, bef in invs:
    ans += aft*k
    m = (bef+aft)*(k-1)
    ans += (m*k)//2
print(ans%mod)

Submission status: Accepted

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

# 数列の自分より後方で自分より小さい数
c1 = sum([1 if a[i]>j else 0 for i in range(n) for j in a[i+1:]])

# 数列内で自分より小さい数
from collections import Counter
ca = Counter(a)

c2 = 0
for n1,cnt1 in ca.items():
    for n2,cnt2 in ca.items():
        if n2<n1:
            c2+=cnt2*cnt1

MOD=10**9+7
k %= MOD
ans = (c1*k)%MOD + (c2*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()))
A=a*2
base=0
matagu=0
for i in range(N):
  for j in range(i+1,2*N):
    if A[i]>A[j]:
      if j>=N:
        matagu+=1
      else:
        base+=1
baserep=K
matagurep=K*(K-1)//2
waru=10**9+7
ans=(base*baserep+matagu*matagurep)%waru
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun May 31 11:25:07 2020

@author: NEC-PCuser
"""

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

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

tentosu = 0

MOD = 1000000007

for i in range(0, N):
    a = 0
    d = 0
    """
    for j in range(0, N):
        if (i == j):
            continue
        if (i < j and A[i] > A[j]):
            a += 1
        if (A[i] > A[j]):
            d += 1
    """
    for j in range(0, N):
        if (A[i] > A[j]):
            d += 1
    for j in range(i, N):
        if (A[i] > A[j]):
            a += 1
    
    
    tentosu += a * K + (K - 1) * K * d // 2;
    
print(tentosu % MOD)

Submission status: Accepted

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

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

k = (K * (K-1) // 2) % mod
ans = ans + (tmp * K % mod) + (tmp2 * k % mod)
print(ans % mod)

Submission status: Accepted

Solution code:
from collections import Counter
from itertools import combinations
n, k = map(int, input().split())
A = list(map(int, input().split()))

mod = 10**9 + 7
inv_num = 0
for left, right in combinations(A, 2):
    if left > right:
        inv_num += 1
#print(inv_num)

acc_num = 0
counter = Counter(A)
rest = n
for key in sorted(counter.keys(), reverse=True):
    rest -= counter[key]
    acc_num += rest * counter[key]

total = (inv_num * k) % mod
total += ((acc_num % mod) * ((k * (k - 1) // 2) % mod)) % mod
total %= mod
print(total)

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):
    cnt = 0
    cnt2 = 0
    for j in range(n):
        if a[i] > a[j]:
            cnt += 1
            if i < j:
                cnt2 += 1
    ans += (cnt*(k-1)*k//2 % mod) + cnt2*k
    ans %= mod
    # print(ans, cnt)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,k = map(int,input().split())
A = list(map(int,input().split()))
ans = 0
MOD = 10**9+7
for i in range(N):
    for j in range(i+1,N):
        if A[i] > A[j]:
            ans += k*(k+1)//2
        elif A[i] < A[j]:
            ans += 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()))
ans = 0
for i in range(n):
    cnt1 = 0
    cnt2 = 0
    for j in range(n):
        if j <= i and a[i] > a[j]:
            cnt1 += 1
        elif j > i and a[i] > a[j]:
            cnt2 += 1
    ans += ((cnt2 * k) + ((cnt1 + cnt2) * k * (k - 1) // 2)) % (10 ** 9 + 7)
print(ans % (10 ** 9 + 7))

Submission status: Accepted

Solution code:
def answer(arr, k):
    _mod = (10**9+7)
    left = 0
    right = 0
    for i in range(len(arr)):
        for j in range(i, len(arr)):
            if arr[i] > arr[j]:
                left += 1
            if arr[i] < arr[j]:
                right += 1
    
    left = (left * (k*(k+1))//2)
    right = (right * (k*(k-1))//2)
    return int((left+right)%_mod)
    
n, k = map(int, input().split())
arr = list(map(int, input().split()))
print(answer(arr, k))
# print(answer2(arr, k))

Submission status: Accepted

Solution code:
import bisect
N, K = map(int, input().split())
a = list(map(int, input().split()))
MOD = 10**9 + 7
ans = 0
a.reverse()
lst2 = sorted(a)
memo = {}
for i in range(N):
    if not a[i] in memo:
        memo[a[i]] = bisect.bisect_left(lst2, a[i])
    ans += K * (K - 1) // 2 *memo[a[i]]

for i in range(1, N):
    lst = sorted(a[0:i])
    k1 = bisect.bisect_left(lst, a[i])
    ans += k1 * K
    ans %= MOD

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):
    for j in range(N):
        if A[i] > A[j]:
            if i > j:
                ans += k*(k-1)//2
            elif i < j:
                ans += 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()))

mod = 10**9 + 7
result = 0
count = [0] * 2001

# リスト内での繰り返し
for a in A:
    count[a-1] += 1
    result += K * sum(count[a:])
    result %= mod

kn = 0
# 前のループに存在する自分より大きい数
count = [i for i in count if i != 0]
total = sum(count) % mod

for i in count:
    total -= i
    kn += total * i
    kn %= mod

result += kn * K*(K-1)//2
result %= 10**9 + 7

print(result)

Submission status: Accepted

Solution code:
#第1回日本最強プログラマー学生選手権-予選-B
n,k = map(int,input().split())
a = list(map(int,input().split()))

EPS = 10**9 + 7

cnt = 0
#リストの中身を見る
for i in range(n-1):
    for j in range(i,n):
        if a[i] > a[j]:
            cnt += 1
        
soto = 0
#リスト外
for i in range(n):
    for j in range(n):
        if a[i] > a[j]:
            soto += 1
            
soto = soto * k * (k-1) // 2

result = cnt * k + soto

print(result % EPS)

Submission status: Accepted

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

    mod = 10 ** 9 + 7

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

        ans += tmp_2 * K * (K+1) // 2
        ans += (tmp_1-tmp_2) * (K-1) * K // 2
        ans %= mod

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

'''
k=4,a_input=[5,2,4,1]の場合を考える
5 2 4 1 5 2 4 1 5 2 4 1 5 2 4 1 

例えば、4に着目すると
5 2 [4] <1> |5 <2> 4 <1> |5 <2> 4 <1> |5 <2> 4 <1>
1 + 2 + 2 + 2
1 + 2 + 2
1 + 2
1 + 0
で総数を求めることができる
左側の1は(a内の右側でa_i>a_jの個数)*k

それ以外は等差数列の和として
(初項+最終項)*項数/2
= n*(k-1)*k/2
で求めることができる

あとは各数字ごとにこれを足し合わせる
'''
ans=0
for i in range(n):
    tmp1=0#内部の個数
    tmp2=0#a列全体の個数
    for j in range(n):
        if i==j:
            continue
        if j>=i+1:
            if a_input[i]>a_input[j]:
                tmp1+=1
        if a_input[i]>a_input[j]:
            tmp2+=1
    ans+=tmp1*k
    ans+=tmp2*(k-1)*k//2
print(ans%(10**9+7))

Submission status: Accepted

Solution code:
import numpy as np

n, k = map(int, input().split())
arr = np.array(list(map(int, input().split())))

# グループ内（初項）
a = 0
for i in range(n - 1):
    a += np.where(arr[i + 1:] < arr[i])[0].shape[0]

# グループ間（差）
d = 0
for i in range(n):
    d += np.where(arr < arr[i])[0].shape[0]

mod = 10**9 + 7

ans = (a + a + d * (k - 1)) * k // 2 % mod

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

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

# グループ内（初項）
start = 0
for i in range(n - 1):
    start += np.where(a[i + 1:] < a[i])[0].shape[0]

# グループ間（差）
coef = 0
for i in range(n):
    coef += np.where(a < a[i])[0].shape[0]

mod = 10**9 + 7

ans = (start + start + coef * (k - 1)) * k // 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

same = 0
for i, ei in enumerate(a):
    for j, ej in enumerate(a[i+1:], i + 1):
        if ei > ej:
            same += 1
            same %= mod

other = 0
for ei in a:
    for ej in a:
        if ei > ej:
            other += 1
            other %= mod

ans = same * k + other * 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()))
mod=10**9+7

micro=0
for i in range(N):
    for j in range(i):
        if A[i]<A[j]:
            micro+=1
A.sort()
macro=[0]
for i in range(1,N):
    if A[i-1]==A[i]:
        macro.append(macro[-1])
    else:
        macro.append(i)

ans=(micro*K+sum(macro)*K*(K-1)//2)%mod
print(ans)

Submission status: Accepted

Solution code:
INF = 10 ** 9 + 7

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

# 単体のA内で発生するケース
inv = 0
for i in range(N-1):
    for j in range(i+1, N):
        if A[i] > A[j]:
            inv += 1
inv = inv * K

# 異なるA間で発生するケース
ini = 0
for k in range(N):
    for l in range(N):
        if A[k] > A[l]:
            ini += 1
ini = ini * K * (K-1) // 2
ans = (inv+ini) % INF
print(ans)

Submission status: Accepted

Solution code:
mod = 10**9 + 7
n,k = map(int,input().split())
A = list(map(int,input().split()))
# その数より右にあるもの
ans = 0
for i in range(n):
    migi = 0
    a = A[i]
    for j in range(i+1,n):
        if a > A[j]:
            migi += 1
    ans += migi * k
    ans %= mod
# 全体で、その数よりも小さいもの(ループするので)
for i in range(n):
    zen = 0
    a = A[i]
    for j in range(n):
        if a > A[j]:
            zen += 1
    # 等差数列のやつ 初項は0, 項数はk,末項はzen * (k-1)
    ans += ((zen*(k-1) * k //2)%mod)
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
import sys, re
from math import ceil, floor, sqrt, pi, factorial#, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left
from functools import reduce
# input = sys.stdin.readline 
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_list(N): return [s_list() for _ in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7

def mod_cmb(n: int, k: int, p: int) -> int:
    if n < 0 or k < 0 or n < k: return 0
    if n == 0 or k == 0: return 1
    if (k > n - k):
        return mod_cmb(n, n - k, p)
    c = d = 1
    for i in range(k):
        c *= (n - i)
        d *= (k - i)
        c %= p
        d %= p
    return c * pow(d, p - 2, p) % p

def main():
    n, k = i_map()
    num_list = i_list()

    first = 0
    second = 0

    for i in range(n):
        for j in range(i+1,n):
            if num_list[i] > num_list[j]:
                first += 1
        for j in range(n):
            if num_list[j] < num_list[i]:
                second += 1
    
    ans = first * k + k * (k-1) * second // 2

    print(ans%MOD)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np

def main():
    n, k = map(int, input().split())
    A = np.array(list(map(int, input().split())))
    MOD = 10 ** 9 + 7
    #転倒数、Aの中で
    C1 = np.array([0] * n)
    C2 = np.array([0] * n)
    for i in range(n):
        C1[i] = np.count_nonzero(A[i:] < A[i])
        C2[i] = np.count_nonzero(A < A[i])
    c1,c2 = C1.sum(),C2.sum()
    ans = 0
	
    ans += c1 * k % MOD
    ans += c2 * (k * (k - 1) // 2 % MOD)

    print(ans % MOD)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
readlines = sys.stdin.readlines
ns = lambda: readline().rstrip() # input string
ni = lambda: int(readline().rstrip()) # input int
nm = lambda: map(int, readline().split()) # input multiple int 
nl = lambda: list(map(int, readline().split())) # input multiple int to list

n, k = nm()
values = nl()
a = 0
b = 0

for i, v in enumerate(values):
    tmp_a = 0
    cnt_b = 0
    for j, v_c in enumerate(values):
        if v > v_c:
            tmp_a += 1
            if i > j:
                cnt_b += 1
    tmp_b = tmp_a * k - cnt_b
    a -= tmp_a
    b += tmp_b
    
print((a * k * (k + 1) // 2 + (b - a) * k) % (10 ** 9 + 7))

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
mod = 10**9+7
a = list(map(int,input().split()))
c = [0]*n
b = []
import bisect
for i in range(n-1,-1,-1):
    c[i] = bisect.bisect_left(b,a[i])
    bisect.insort_left(b,a[i])
    
ans = 0
for i in c:
    ans += i*k

for i in range(n):
    c[i] = bisect.bisect_left(b,a[i])
    
sk = k*(k-1)//2
for i in c:
    ans += i*sk

print(ans%mod)

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):
    l = 0
    for j in range(i+1,n):
        if  A[i] > A[j]:
            l += 1
    ans1 += l
    m = 0
    for j in range(i+1):
        if A[i] > A[j]:
            m += 1
    ans2 += l+m
print((ans1*k+ans2*(k*(k-1)//2))%(10**9+7))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

MOD = 10 ** 9 + 7

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

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

ans = K * tento1 + (K * (K - 1)) // 2 * tento2
ans = ans % MOD
print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = [int(_) for _ in 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

dic = dict()
for i in range(n):
    if a[i] in dic:
        dic[a[i]] += 1
    else:
        dic.setdefault(a[i], 1)
dic = sorted(dic.items())
cnt = 0
s = dic[0][1]
for i in range(1, len(dic)):
    cnt += s * dic[i][1]
    s += dic[i][1]
rep = k * (k-1) // 2
ans = (ans + cnt * rep) % MOD
print(ans)

Submission status: Accepted

Solution code:
import sys
#import numpy as np
import math
from fractions import Fraction
import itertools

input=sys.stdin.readline
n,k=map(int,input().split())
a=list(map(int,input().split()))
p=[0]*n
q=[0]*n
ans=0
mod=10**9+7
for i in range(n):
    for j in range(n):
        if a[i]>a[j]:
            if i>j:
                p[i]+=1
            elif i<j:
                q[i]+=1
                
for i in range(n):
    ans+=(k*q[i]+((p[i]+q[i])*k*(k-1)//2)%mod)%mod
    ans=ans%mod
print(int(ans%mod))

Submission status: Accepted

Solution code:
#coding: utf-8
N, K = map(int, input().split())
A = list(map(int, input().split()))
ans = 0
mod = 10**9 + 7
jun = [0 for _ in range(N)]
inv = [0 for _ in range(N)]
for i in range(N):
    for j in range(N):
        if j < i:
            if A[i] < A[j]:
                jun[i] += 1
        else:
            if A[i] < A[j]:
                inv[i] += 1
for i in range(N):
    ans += K * (jun[i] * (K+1) + inv[i] * (K-1)) // 2
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
def resolve():
    '''
    code here
    '''
    N, K = [int(item) for item in input().split()]
    A_list = [int(item) for item in input().split()]

    mod = 10**9+7

    base_n = 0

    for i in range(N):
        for j in range(i+1,N):
            if A_list[i] > A_list[j]:
                base_n += 1
    
    all_n = 0
    for i in range(N):
        for j in range(N):
            if A_list[i] > A_list[j]:
                all_n += 1


    print(((base_n*K)+all_n*(K-1)*K//2)%mod)





if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
n,k,*a=map(int,open(0).read().split());s=t=0;r=range(n)
for i in r:
 for j in r:s+=j>i and a[j]<a[i];t+=a[j]<a[i]
print((s*k+k*~-k//2*t)%(10**9+7))

Submission status: Accepted

Solution code:
MOD = 10**9+7
n, k, *a = map(int, open(0).read().split())
s = t = 0
for i in range(n):
  s += sum(j>i and a[j]<a[i] for j in range(n))
  t += sum(a[j]<a[i] for j in range(n))
print((s*k + k*~-k//2*t) % MOD)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
l = list(map(int,input().split()))
mod = 10**9+7
a = 0
for i in range(n):
  b = l[i]
  t = (len([1 for m in l if  m<b])%mod)*(int( (k-1)%mod*k//2)%mod)%mod
 # print(i,b,t)
  s = (len([1 for m in l[i:] if m<b])%mod)*k%mod
#  print(s)
  a += (s+t)%mod
print(a%mod)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
MOD = int(1e9) + 7


def wa(n, a):
    return ((n*(n+1))//2 * a) % MOD


ans = 0
# 内部の転倒数
for n in range(N):
    # 内部
    a = 0
    nA = A[n+1:]
    t = A[n]
    for na in nA:
        if t > na:
            a += 1
    temp = wa(K, a)
    ans += temp
    ans = ans % MOD

    # 外部
    b = 0
    nA = A[:n+1]
    for na in nA:
        if t > na:
            b += 1
    temp = (b * K*(K-1)//2)%MOD
    ans += temp
    ans = ans % 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
pair = 0
for i in range(N):
    for j in range(i+1, N):
        if A[i] > A[j]:
                cnt += 1

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

v = (K * (K-1) // 2) % mod * pair % mod
print((cnt * K % mod + v) % mod)

Submission status: Accepted

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

ans = 0

for i, a in enumerate(A):
    L, R = 0, 0
    for j, b in enumerate(A):
        if b < a:
            if j < i:
                L += 1
            else:
                R += 1
    ans += (L + R) * K * (K - 1) // 2
    ans += R * K

ans = ans % N
print(int(ans))

Submission status: Accepted

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

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

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

A.sort(reverse=True)
count_ = 0
for i in range(len(A)-1):
  for j in range(i, len(A)):
    if A[i] > A[j]:
      count_ += 1

sum1 = count * K

K = K-1
sum = K*(K+1)//2

sum2 = count_ * sum
print((sum1 + sum2)%mod)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from bisect import bisect_left
N, K = map(int, input().split())
A = list(map(int, input().split()))
B = sorted(A)
p = 10**9+7

list1 = [bisect_left(B,A[i]) for i in range(N)]
list2 = [bisect_left(sorted(A[i+1:]),A[i]) for i in range(N)]
ans = 0
for i in range(N):
  ans += list2[i] * K
  ans %= p
  tmp = K * (K-1) // 2
  ans += list1[i] * tmp
  ans %= p
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
cnt1 = 0
cnt2 = 0
seen = []
for i in a:
    for j in seen:
        if i<j:
            cnt1 += 1
    seen.append(i)
for i in a:
    for j in seen:
        if i<j:
            cnt2 += 1
ans = cnt1*k+cnt2*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()))
cnt = 0
l = []
for i in range(n):
    for j in range(n):
        if a[i] > a[j]:
            cnt += (k + 1) * k // 2 if j > i else k * (k - 1) // 2
print(cnt % 1000000007)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
b = a + a
c = 0
for i in range(len(a)):
    for j in range(i + 1, len(a)):
        if a[i] > a[j]:
            c += 1
d = 0
for i in range(len(b)):
    for j in range(i + 1, len(b)):
        if b[i] > b[j]:
            d += 1
d -= c * 2
def modpow(n, p, mod):
    r = 1
    while p > 0:
        if p & 1 == 1:
            r = r * n % mod
        n = n * n % mod
        p >>= 1
    return r
def modinv(n, mod):
    return modpow(n, mod - 2, mod)
MOD = 10 ** 9 + 7
ans = (k - 1) * d % MOD
ans += 2 * c
ans %= MOD
ans *= k
ans %= MOD
ans *= modinv(2, MOD)
ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
A = list(map(int,input().split()))
lA = len(A)
mod=10**9+7
cnt1=0
for i in range(lA):
    for j in range(i+1,lA):
        if A[i] > A[j]:
            cnt1+=1
cnt2=0
for i in range(lA):
    for j in range(lA):
        if A[i] > A[j]:
            cnt2+=1
print((cnt1*k+cnt2*(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
num_1 = 0
num_2 = 0
for i in range(N):
  for j in range(N):
    if j < i:
      if A[j] < A[i]:
        num_2 += 1
    elif j > i:
      if A[j] < A[i]:
        num_1 += 1
        num_2 += 1
K1 = (K)*(K-1)//2%MOD
print((num_1*K + num_2 * K1)%MOD)

Submission status: Accepted

Solution code:
import sys

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

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

Submission status: Accepted

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

mod = 10 ** 9 + 7

ai = 0
bi = 0

for i in range(N-1):
    for j in range(i+1, N):
        if(A[i] > A[j]):
            ai += 1
            ai %= mod

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

ansa = ai * K % mod
ansb = K * (K-1) // 2 % mod
ansb = ansb * bi % mod
ans = (ansa + ansb) % mod
print(ans)

Submission status: Accepted

Solution code:
import sys


def main():
    N, K = map(int, sys.stdin.readline().split())
    A = list(map(int, sys.stdin.readline().split()))

    count1 = 0
    count2 = 0

    for i in range(N - 1):
        for j in range(i + 1, N):
            if A[i] > A[j]:
                count1 = count1 + 1
            if A[i] != A[j]:
                count2 = count2 + 1
    count1 = count1 * K
    count2 = count2 * (K * (K - 1) // 2)

    ans = (count1 + count2) % 1000000007
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#第一回日本最強プログラマー学生選手権-予選- -B Kleene Inversion
"""
リストをk回繰り返したものの、転倒数の個数を求めよ
先ず純粋に与えられたリスト内での転倒数を求めた後、
それを1~k倍したものを足し合わせる
"""
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
mod = 10**9+7

n,k = map(int,readline().split())
lst1 = list(map(int,readline().split()))
fall = 0
fall_al = 0
for i in range(n-1):
    for j in range(i+1,n):
        if lst1[i] > lst1[j]:
            fall += 1
lst1.sort(reverse=True)
for i in range(n-1):
    for j in range(i+1,n):
        if lst1[i] > lst1[j]:
            fall_al += 1

def reydeoro(n):
    return n*(n+1)//2
print((fall*k+fall_al*reydeoro(k-1))%mod)

Submission status: Accepted

Solution code:
n,k,*a=map(int,open(0).read().split())
mod=10**9+7
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 i in range(n):
  for j in range(n):
    if a[i]<a[j]:
      y+=1
print((x*k+y*k*(k-1)//2)%mod)

Submission status: Accepted

Solution code:
import sys
import bisect

MOD = pow(10, 9)+7
readline = sys.stdin.readline

def main():
    N, K = map(int, readline().split())
    A = list(map(int, readline().split()))
    init = []
    for i in range(N):
        cnt = 0
        for j in range(0, i):
            if A[j] < A[i]:
                cnt += 1
        init.append(cnt)
    
    Atmp = A.copy()
    Atmp.sort()
    large = []
    for i in range(N):
        large.append(bisect.bisect_left(Atmp, A[i]))

    ans = 0
    for i in range(N):
        a0 = large[i]*K-init[i]
        b = large[i]
        ans += K*a0 - ((K*(K-1))//2)*large[i]
        ans %= MOD
    print(ans%MOD)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
def main():
    N, K = (int(_) for _ in input().split())
    A = [int(_) for _ in input().split()]

    R, L = [], []
    for i in range(N):
        cr = cl = 0
        for j in range(N):
            if i == j: continue
            if A[i] > A[j]:
                if i > j: cl += 1
                if i < j: cr += 1
        R.append(cr)
        L.append(cl)

    output = 0
    for i in range(N):
        output += (K*R[i] + K*(K-1)*(R[i]+L[i])//2)
        output %= MOD
    print(output)
    return

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

C1 = [0]*n
C2 = [0]*n

for i in range(n):
    for j in range(n):
        if A[i] > A[j]:
            if j >= i:
                C1[i] += k*(k+1)//2
            else:
                C2[i] += (k-1)*k//2
ans = 0
#print(C1)
#print(C2)
for i in range(n):
    ans += C1[i]+C2[i]
print(ans%mod)

Submission status: Accepted

Solution code:
import sys
import re
import math
import collections
import decimal
import bisect
import itertools

import copy

# import heapq
# from collections import deque
# import decimal

# sys.setrecursionlimit(100001)
INF = sys.maxsize
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n, k = ns()
    a = na()

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

    ans = total * (k * (k - 1) // 2) % MOD

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

    res = (ans + cnt) % MOD

    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import re
import math
import collections
import decimal
import bisect
import itertools

import copy

# import heapq
# from collections import deque
# import decimal

# sys.setrecursionlimit(100001)
INF = sys.maxsize
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n, k = ns()
    a = na()

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

    ans = total * (k * (k - 1) // 2) % MOD

    cnt = 0
    for i in range(n):
        for j in range(i):
            if a[j] > a[i]:
                cnt += 1
                cnt %= MOD
    cnt = cnt * k % MOD

    res = (ans + cnt) % MOD

    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
import functools
import math
import scipy
import fractions
import itertools

def solve():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    hoge, huga = 0, 0
    piyo = 10**9+7
    for i in range(n-1):
        for j in range(i, n):
            if a[i] > a[j]:
                hoge += 1
    hoge *= k
    for i in range(n):
        for j in range(n):
            if i != j:
                if a[i] > a[j]:
                    huga += 1
    huga *= (k*(k-1))//2
    print((hoge+huga)%piyo)
    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

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

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

outer = 0

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

print((inner + outer) % mod )