Problem:


Score : 300 points

Problem Statement

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

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

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

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

Constraints

All values in input are integers.

1 \leq N \leq 2000

1 \leq K \leq 10^9

1 \leq A_i \leq 2000

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

2 2
2 1

Sample Output 1

3

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

B_0 > B_1

B_0 > B_3

B_2 > B_3

Thus, the inversion number of B is 3.

Sample Input 2

3 5
1 1 1

Sample Output 2

0

A may contain multiple occurrences of the same number.

Sample Input 3

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

Sample Output 3

185297239

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



Sample input:
2 2
2 1


Sample output:
3

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def sum_arithmetic_seq(a, d, n):
    return n * (2 * a + (n - 1) * d) // 2

def main():
    N, K = [int(x) for x in input().split()]
    A = [int(x) for x in input().split()]

    MOD = 10 ** 9 + 7

    B = [0] * N
    C = [0] * N
    for i in range(N):
        for j in range(i):
            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

    ans = sum(B) * K
    ans %= MOD
    ans += sum_arithmetic_seq(0, sum(C), K)
    ans %= MOD
    print(ans)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def merge_sort(A):
    N = len(A)
    if N < 2:
        return A, 0
    mid = N//2
    left, left_count = merge_sort(A[:mid])
    right, right_count = merge_sort(A[mid:])
    total_count = left_count+right_count
    lowers = 0
    answer = []
    for l in left:
        while lowers < len(right) and right[lowers] < l:
            answer.append(right[lowers])
            lowers += 1
        total_count += lowers
        answer.append(l)
    while lowers < len(right):
        answer.append(right[lowers])
        lowers += 1
    return answer, total_count


def solve():
    N, K = read_ints()
    A = read_ints()
    _, left_greater = merge_sort(A)
    _, right_greater = merge_sort(A[::-1])
    modulo = 10**9+7
    return (K*(K+1)//2*left_greater+K*(K-1)//2*right_greater)%modulo


if __name__ == '__main__':
    print(solve())

Submission status: Accepted

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

npr=np.zeros(max(a)+1)
for i in a:
    npr[i:] += 1

ruiseki=list(npr)
sm1=0
for i in a:
    sm1 += ruiseki[i-1]

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

sm2=0
for i in a:
    sm2 += npr[i-1]
    npr[i:] -= 1

ans2=(sm2*k)%(10**9+7)

ans=(ans1+ans2)%(10**9+7)
print(int(ans))

Submission status: Accepted

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

lst=[0]*(max(a)+1)
for i in a:
    lst[i]+=1

ruiseki=[0]*(max(a)+1)
for i,j in enumerate(lst):
    ruiseki[i] = ruiseki[i-1]+j
sm1=0
for i in a:
    sm1 += ruiseki[i-1]

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

npr=np.array(ruiseki)
sm2=0
for i in a:
    sm2 += npr[i-1]
    npr[i:] -= 1

ans2=(sm2*k)%(10**9+7)
ans=(ans1+ans2)%(10**9+7)

print(ans)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
b = a
ans = 0
for i in range(n):
    x = 0
    y = 0
    for j in range(i):
        if a[i] > a[j]:
            x += 1
    for j in range(n):
        if a[i] > b[j]:
            y += 1
    ans += y * ((1 + k) * k // 2) - x * k
    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
f = 0
d = 0

for i in range(n):
    a.append(a[i])

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

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

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

Submission status: Accepted

Solution code:
def main():
    MOD = 10**9 + 7
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    left_smaller = [0]*N
    right_smaller = [0]*N
    for i, a in enumerate(A):
        left_smaller[i] = sum(b < a for b in A[:i])
        right_smaller[i] = sum(b < a for b in A[i+1:])

    ans = sum((l*(K)*(K-1)//2%MOD + r*(K+1)*(K)//2%MOD)%MOD for l, r in zip(left_smaller, right_smaller))%MOD
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import math
import itertools
import collections
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()

NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()

def main():

    N, K = NMI()
    A = NLI()
    
    cnt = 0
    for i in range(len(A)-1):
        for j in range(i+1,len(A)):
            if A[i] > A[j]:
                cnt += 1
    
    repeat = 0
    ls = [0 for _ in range(len(A))]
    for k in range(len(A)):
        repeat += len([x for x in A if x < A[k]])

    
    print((cnt*K + repeat * (((K-1)*K)//2))%MOD)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
mod=10**9+7

n,k = map(int,input().split())
l = list(map(int,input().split()))
l2 = l+l

x=0
for i in range(n-1):
    for j in range(i,n-1):
        if l[i] > l[j+1]:
                x+=1

y=0
for i in range(2*n-1):
    for j in range(i,2*n-1):
        if l2[i] > l2[j+1]:
                y+=1

y-=(2*x)

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

Submission status: Accepted

Solution code:
def resolve():
  N, K = map(int, input().split(" "))
  A = [int(x) for x in input().split(" ")]
  maxA = max(A)
  base = 10**9+7
  # counter_of_A = [0]*(maxA+1)
  integra_of_counter = [0]*(maxA+1)

  # A の転倒数を数える。
  inversion_num_of_first_A = 0
  for a in reversed(A):
    if a > 1:
      inversion_num_of_first_A += integra_of_counter[a-1]
    
    for x in range(a, maxA+1):
      integra_of_counter[x] += 1


  # B の 2 番目の転倒数を数える
  inversion_num_of_second_A = 0
  for a in reversed(A):
    if a > 1:
      inversion_num_of_second_A += integra_of_counter[a-1]
    
    for x in range(a, maxA+1):
      integra_of_counter[x] += 1
  # print(integra_of_counter)
  # print(inversion_num_of_second_A)

  # print("K =", K, "a =", inversion_num_of_first_A, "d =", inversion_num_of_second_A - inversion_num_of_first_A)
  if K%2 == 0:
    result = K//2 * (2*inversion_num_of_first_A%base + (K-1)*(inversion_num_of_second_A - inversion_num_of_first_A)%base)
  else:
    result = (inversion_num_of_first_A%base + ((K-1)*(inversion_num_of_second_A - inversion_num_of_first_A)//2)%base)*K
  result %= base

  print(result)

if __name__ == "__main__":
  resolve()

Submission status: Accepted

Solution code:
def resolve():
  N, K = map(int, input().split(" "))
  A = [int(x) for x in input().split(" ")]
  maxA = max(A)
  base = 10**9+7
  # counter_of_A = [0]*(maxA+1)
  integra_of_counter = [0]*(maxA+1)

  # A の転倒数を数える。
  inversion_num_of_first_A = 0
  for a in reversed(A):
    if a > 1:
      inversion_num_of_first_A += integra_of_counter[a-1]
    
    for x in range(a, maxA+1):
      integra_of_counter[x] += 1


  # B の 2 番目の転倒数を数える
  inversion_num_of_second_A = 0
  for a in reversed(A):
    if a > 1:
      inversion_num_of_second_A += integra_of_counter[a-1]
    
    for x in range(a, maxA+1):
      integra_of_counter[x] += 1
  # print(integra_of_counter)
  # print(inversion_num_of_second_A)

  # print("K =", K, "a =", inversion_num_of_first_A, "d =", inversion_num_of_second_A - inversion_num_of_first_A)
  if K%2 == 0:
    result = K//2 * (2*inversion_num_of_first_A%base + (K-1)*(inversion_num_of_second_A - inversion_num_of_first_A)%base)
  else:
    result = (inversion_num_of_first_A%base + ((K-1)*(inversion_num_of_second_A - inversion_num_of_first_A)//2)%base)*K
  result %= base

  print(result)
if __name__ == "__main__":
  resolve()

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,k = list(map(int, input().split()))
a = list(map(int, input().split()))
v = 0
v2 = 0
M = 10**9+7
for i in range(n):
    v += sum(a[i]<a[j] for j in range(i))
    v2 += sum(a[i]<a[j] for j in range(n))
#     print(v,v2)
ans = v*k
ans += v2*(k-1)*k//2
print(ans%M)

Submission status: Accepted

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

N, K = cin()
A = cin()
INF = 10 ** 9 + 7

cnt1 = 0
l = len(A)
for i in range(l):
    for j in range(i + 1, l):
        cnt1 += (A[i] > A[j])
        
AA = A + A
l = len(AA)
cnt2 = 0
for i in range(l):
    for j in range(i + 1, l):
        cnt2 += (AA[i] > AA[j])

ans = K * cnt1 + (cnt2 - 2 * cnt1) * K * (K - 1) // 2
print(ans % INF)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import bisect_right
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
MOD = 10**9+7
N,K = map(int,input().split())
A = list(map(int,input().split()))
d = defaultdict(int)
for a in A:
    d[a] += 1
ans = 0
for i in range(1,2001):
    c = 0
    for j in range(0,i):
        c += d[j]
    ans += c*d[i]*((K-1)*K)//2
    ans %= MOD
for i in range(len(A)):
    a = A[i]
    for j in range(i+1,len(A)):
        if a > A[j]:
            ans += K
ans %= MOD
print(ans)

Submission status: Accepted

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

cnt = 0
for i in range(n-1):
    tmp = 0
    for j in range(i+1,n):
        if L[i] > L[j]:
            cnt +=1
cnt2 = 0
li = []
for i in range(n):
    tmp = 0
    for j in range(n):
        if L[i] > L[j]:
            cnt2 +=1

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

Submission status: Accepted

Solution code:
import sys, math
from functools import lru_cache
from collections import defaultdict
sys.setrecursionlimit(500000)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]

def main():
    N, K = mi()
    A = list(mi())
    c = 0
    d = 0

    for i in range(N-1):
        for j in range(i+1, N):
            if A[i] > A[j]:
                c += 1
    
    for i in range(N):
        for j in range(N):
            if A[i] < A[j]:
                d += 1

    ans = (K*(K-1)//2)%MOD
    ans *= d
    ans %= MOD
    ans += (K*c)%MOD
    ans %= MOD

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

mod=10**9+7
ans=0
cnt=0
for i in range(n):
    for j in range(i+1,n):
        ans+=k if a[i]>a[j] else 0
        cnt+=0 if a[i]==a[j] else 1

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

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

print((cnt1+cnt2)%(10**9+7))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

H=(K*(K-1))//2

X=0
M=10**9+7
I=(M+1)//2

for i in range(N):
    P,Q,S,V=0,0,0,0
    for j in range(N):
        if A[i]<A[j]:
            P+=1
            if j<i:
                S+=1
        if A[i]>A[j]:
            Q+=1
            if i<j:
                V+=1
    X+=K*(S+V)+H*(P+Q)
    X%=M
print((X*I)%M)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
d={}
key=[]
n_in=0
n_out=0
ans=0
#k%=(10**9+7)
for i in range(n):
    try:
        d[a[i]]+=1
    except:
        d[a[i]]=1
        key.append(a[i])
        key.sort()
    ind=key.index(a[i])
    for j in range(ind+1,len(key)):
        n_in+=d[key[j]]
for val in a:
    ind=key.index(val)
    for j in range(ind+1,len(key)):
        n_out+=d[key[j]]

ans+=n_in*k
ans+=n_out*(k-1)*k//2
ans%=10**9+7
print(ans)

Submission status: Accepted

Solution code:
n,k = map(int, input().split())
al = list(map(int, input().split()))
inner_invs = [0]*n
outer_invs = [0]*n

for i in range(n):
    inner_cnt = 0
    outer_cnt = 0
    for j in range(n):
        if al[i] > al[j]:
            if i < j:
                inner_cnt += 1
                outer_cnt +=1
            elif i > j:
                outer_cnt += 1
    inner_invs[i] = inner_cnt
    outer_invs[i] = outer_cnt


ans = 0
MOD = 10**9+7

for v in outer_invs:
    ans += v*k*(k-1)//2
    ans %= MOD

for v in inner_invs:
    ans += v*k

print(ans%MOD)

Submission status: Accepted

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

mod = 10**9+7
res = 0

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

print(res)

Submission status: Accepted

Solution code:
import sys
from collections import Counter

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    N, K = map(int, readline().split())
    A = list(map(int, readline().split()))
    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
                else:
                    ans += K * (K - 1) // 2
                ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
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
            cnt %= mod
print(cnt % mod)

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

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

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

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

Submission status: Accepted

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

b1list=alist
b2list=alist+alist

ans_k1=0
for i in range(N):
  for j in range(i+1,N):
    if b1list[i]>b1list[j]:
      ans_k1+=1
ans_k2=0
for i in range(2*N):
  for j in range(i+1,2*N):
    if b2list[i]>b2list[j]:
      ans_k2+=1      

diff_k12=ans_k2-2*ans_k1
#print(ans_k1,ans_k2,diff_k12)

answer=ans_k1*K+diff_k12*K*(K-1)//2
answer%=MOD
print(answer)

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

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

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

print(ans%MOD)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys,math,collections,itertools
input = sys.stdin.readline
m = 10**9+7
N,K = list(map(int,input().split()))
A = list(map(int,input().split()))
Aaf = []
Aall = []
for i in range(N):
    cntall= 0
    cntaf = 0
    for j in range(N):
        if A[i]>A[j]:
            cntall +=1
            if i < j :
                cntaf += 1
    Aaf.append(cntaf)
    Aall.append(cntall)

cnt=0
for a0,a1 in zip(Aaf,Aall):
    cnt += (K*a0+a1*K*(K-1)//2)%m
print(cnt%m)

Submission status: Accepted

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

K_seq_sum1 = K*(K+1)//2
K_seq_sum2 = K*(K-1)//2
# print(K_seq_sum)
# その中での転倒数と
# 自分より低い数を持っておく
inv_num_in_original_list = []
inv_num_all_list = []
diff_lst = []
res = 0
for n1, a1 in enumerate(A_list):
    cnt1 = 0
    cnt2 = 0
    for n2, a2 in enumerate(A_list):
        if a1 > a2:
            cnt2 += 1
            if n1 < n2:
                cnt1 += 1
    diff = cnt2 - cnt1
    # a1から見たときの数を出す
    # (自分のリストの中での転倒の数 * K回) + (自分より左のリストとの転倒数)
    # res_tmp = cnt1 * K + cnt2 * K_seq_sum
    # res += res_tmp s
    res_tmp = diff * K_seq_sum2 + cnt1 * K_seq_sum1
    res += res_tmp
    res = int(res % (10**9+7))
print(res)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
num=[]
for i in range(n):
    num.append([a[i],i])
s1= lambda val: val[0]
num.sort(key=s1)
num1=0
num[0].append(0)
for i in range(1,n):
    if num[i][0]==num[i-1][0]:
        num[i].append(num1)
    else:
        num1=i
        num[i].append(num1)
num2=0
num3=0
s2=lambda val: val[1]
num.sort(key=s2)
for i in range(n):
    num2+=num[i][2]
    for j in range(i):
        if num[i][0]>num[j][0]:
            num3+=1
ans=((num2-num3)*k)%(10**9+7)
ans+=(num2*((((k-1)*k)//2)%(10**9+7)))%(10**9+7)
print(ans%(10**9+7))

Submission status: Accepted

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

ans = 0
mod = 10**9+7

for n in range(N):
    for i in range(N):
        if A[n] > A[i]:
            if n<i:ans += (K*(K+1)//2)%mod
            else:ans+=(K*(K-1)//2)%mod

print(ans%mod)

Submission status: Accepted

Solution code:
# A内で完結するものと、連結したときに変わるものがある
#
# 3 4 2 1 2 -> 3+3+1+0+0 = 7
# 3 4 2 1 2 | 3 4 2 1 2 -> (3*2)+(1*1+3*2)+(1*2)+0+(1*1) + 7 = 16 + 7
# 3 4 2 1 2 | 3 4 2 1 2 | 3 4 2 1 2 -> (3*3)+(2*1+3*3)+(1*3)+0+(2*1) + 16+7 = 25+16+7
# Aについて、i<jなるjでAi>Ajになるものがk個、Ai<Ajになるものがk-1個ある
# k=3で考えると
# 順方向: (m*3)+(m*3)+(m*1)+(0)+(0), m=1~3 = 7+14+21=42
# 逆方向：(0)+(m*1)+(0)+(0)+(m*1), m=1~2 = 2+4=6 （逆方向はk-1個）
# 合わせて48となりこれは上記で試してたのと等しい
# ということで、それぞれ等差数列の和が使えそう
n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = 10**9 + 7

# 順方向
base = 0
for i in range(n):
    for j in range(i, n):
        if a[i] > a[j]:
            base += 1
# 逆方向
additional = 0
for i in range(n):
    for j in range(i):
        if a[i] > a[j]:
            additional += 1

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

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A_LIST = list(map(int, input().split()))
MOD = 10 ** 9 + 7
t = 0
tr = 0
ans = 0
for i in range(N):
    for j in range(i + 1, N):
        if A_LIST[i] > A_LIST[j]:
            t += 1
    for k in range(N):
        if A_LIST[i] > A_LIST[k]:
            tr += 1
ans += t * K % MOD
ans += tr * (K - 1) * K // 2 % MOD
print(ans % MOD)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import itertools

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

internal = 0
for a0, a1 in itertools.combinations(A, 2):
    if a0 > a1:
        internal += 1

external = 0
for a0, a1 in itertools.permutations(A, 2):
    if a0 > a1:
        external += 1

ans = internal * K + external * K * (K - 1) // 2
ans = int(ans) % m
print(ans)

Submission status: Accepted

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

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

cnt_sum = sum(cnt)
x = ((K - 1) * K // 2) % mod

ans += cnt_sum * x
ans %= mod
print(ans)

Submission status: Accepted

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

i=0
L=0
R=0
while i<N:
    j=0
    while j<N:
        L+=(j<i and A[i]>A[j])
        R+=(i<j and A[i]>A[j])
        j+=1
    i+=1

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

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


class BinaryIndexTree:
    def __init__(self, n):
        self.size = n
        self._container = [0] * (n + 1)
        self.depth = n.bit_length()

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

    def add(self, i, x):
        if i == 0:
            return
        while i <= self.size:
            self._container[i] += x
            i += i & (-i)

    def lower_bound(self, x):
        if x == 0:
            return 0

        s = 0
        idx = 0
        for i in range(self.depth, -1, -1):
            k = idx + (1 << i)
            if k <= self.size and s + self._container[k] < x:
                s += self._container[k]
                idx += 1 << i
        return idx + 1

    def __repr__(self):
        return str(self._container)


def main():
    n, k = map(int, readline().split())
    a = list(map(int, readline().split()))
    bit = BinaryIndexTree(2000)

    p = 0
    q = 0
    for x in a[::-1]:
        p += bit.sum(x - 1)
        bit.add(x, 1)

    for i in range(2, 2001):
        q += (bit.sum(i) - bit.sum(i - 1)) * bit.sum(i - 1)

    ans = p * k + q * (k - 1) * k // 2
    print(ans % MOD)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
from math import sqrt, pi
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

N, K = getNM()
A = getList()

# 同じ列内でそれ以降に含まれるもの
same = [0] * N
for i in range(N):
    cnt = 0
    for j in range(i + 1, N):
        if A[i] > A[j]:
            cnt += 1
    same[i] = cnt

# 列内全体で 前の物も含む
roop = [0] * N
for i in range(N):
    cnt = 0
    for j in range(N):
        if A[i] > A[j]:
            cnt += 1
    roop[i] = cnt

ans = 0
for i in range(N):
    ans += ((same[i] * K) + (roop[i] * K * (K - 1) // 2)) % mod
    ans %= mod
print(ans % mod)

Submission status: Accepted

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

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

sA = sorted(A)
C = [0]*n
for i in range(1,n):
  if sA[i-1] == sA[i]:
    C[i] = C[i-1]
  else:
    C[i] = i

ans = (t*k) % mod
multi = k*(k-1)//2

for i in range(n):
  ans = (ans + (C[i]*multi) ) %mod
  
print(ans)

Submission status: Accepted

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

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

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

Submission status: Accepted

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

smaller = [0]*N
reverse = [0]*N
for i in range(N):
    for j in range(N):
        if j == i: continue
        if A[i] > A[j]:
            smaller[i] += 1
            if i < j:
                reverse[i] += 1

ans = (K*sum(reverse)%MOD + ((K*(K-1)//2)%MOD)*sum(smaller))%MOD
print(ans)

Submission status: Accepted

Solution code:
import itertools


def solve():
    N, K = [int(x) for x in input().split()]
    A = [int(x) for x in input().split()]

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

    M = 10**9 + 7
    # オーバーフロー対策で掛け算毎に剰余をとる
    a = cntA * K % M
    b = ((K - 1) * K // 2) % M * cntB % M
    print((a + b) % M)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
#-*-coding:utf-8-*-
import sys
input=sys.stdin.readline
from itertools import combinations

def main():
    n,k = map(int,input().split())
    A = list(map(int,input().split()))
    counter=0
    mod = 10**9+7
    
    for i  in range(n-1):
        for j in range(i+1,n):
            if A[i] > A[j]: counter+=1

    y =0
    for a1 in A:
        for a2 in A:
            if a1 > a2: y+=1

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

if __name__=="__main__":
    main()