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())
a=list(map(int,input().split()))
mod=10**9+7
c=[]
ans=0
for i in range(2002):
    c.append([0,0])
for i in range(n):
    c[a[i]][0]+=1
    for j in range(a[i]+1,2001):
        ans+=c[j][0]
for i in range(1999,-1,-1):
    c[i][0]+=c[i+1][0]
d=0
for i in a:
    d+=c[i+1][0]
print((k*ans+d*(k*(k-1))//2)%mod)

Submission status: Accepted

Solution code:
import bisect
from collections import deque
import sys
MAX_INT = int(10e9)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N,K = IL()
a = IL()

cnt = 0
for left in range(N):
  for right in range(left+1,N):
    if a[left] > a[right]:
      cnt += 1
cnt = (cnt*K) %mod

a.sort()
tmp = 0
for i in range(N-1):
  if a[i+1] > a[i]:
    tmp = i+1
  cnt += ((tmp*K*(K-1))//2) %mod

print(cnt %mod)

"""
2 1000000006
2 1

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

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
#10**9+7  で割った余り
#k = k %(10**9 + 7)
#その文字iより前に大きな数字
before_cnt = 0
#その文字より後に大きな数字
after_cnt = 0
n_list = list(map(int, input().split()))
for i in range(n-1):
  for j in range(i+1, n):
    if n_list[i] > n_list[j]:
      before_cnt+=1
    elif n_list[i] < n_list[j]:
      #print("i",i,"j",j)
      after_cnt+=1
      '''
      if i < j:
        after_cnt+=1
      else:
        before_cnt+=1
'''
kurikaesi = int((1 + k)*k//2)
#print("type",type(k),"kurikaesi",kurikaesi)
#print(after_cnt, before_cnt)
print(((after_cnt*(kurikaesi-k) + before_cnt*kurikaesi))%(10**9 + 7))

Submission status: Accepted

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

left, right = 0, 0
for i in range(len(an)):
    ref = an[i]
    left += len([a for a in an[0:i] if a < ref])
    right += len([a for a in an[i+1:] if a < ref])


k2 = k**2
ans = ((k2 + k) * right + (k2 - k) * left) // 2
print(ans % (10**9 + 7))

Submission status: Accepted

Solution code:
M, K = map(int, input().split())
A = list(map(int, input().split()))
cnt = 0
for i, Ai in enumerate(A):
  for Aj in A[i+1:]:
    if Ai > Aj:
      cnt += 1
cnt_sorted = 0
A_sorted = sorted(A, reverse=True)
for i, Ai in enumerate(A_sorted):
  for Aj in A_sorted[i+1:]:
    if Ai > Aj:
      cnt_sorted += 1
ans = cnt * K + cnt_sorted * K * (K-1) // 2
print(ans % (10 ** 9 + 7))

Submission status: Accepted

Solution code:
n, k = input().split()
n = int(n)
k = int(k)
A = [int(a) for a in input().split()]
m = 1000000007
inv = 0

count = 0

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

ans = inv*k + inv2*sum(range(k))

ans %= m
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n, k = map(int, input().split())
a = list(map(int, input().split()))

n_cnt = [0 for _ in range(2001)]
less = [0 for _ in range(2001)]
ress = [0 for _ in range(n)]
for i in a:
    n_cnt[i] += 1

tmp = 0
for i, c in enumerate(n_cnt):
    less[i] += tmp
    tmp += c

for i in range(n):
    cnt = 0
    tgt = a[i]
    for j in a[i+1::]:
        cnt += 1 if j < tgt else 0
    ress[i] = cnt


cnt = 0
for _a, less_r in zip(a, ress):
    less_all = less[_a]
    cnt +=  ((k*(k-1))//2) * less_all + less_r * k

print(cnt%1000000007)

Submission status: Accepted

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

right = []

for i in range(n):
    count = 0
    for j in range(n-i-1):
        if(a[i]>a[i+j+1]):
            count+=1
    right.append(count)
    


miman = [0 for i in range(2002)]

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

#print(right)
#print(miman[:6])

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 18
MOD = 10 ** 9 + 7


def LI():
    return list(map(int, sys.stdin.readline().split()))


def II():
    return int(sys.stdin.readline())


def LS():
    return list(map(list, sys.stdin.readline().split()))


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


def main():
    n, k = LI()
    a_s = LI()
    ts = [0 for i in range(n)]
    f_ts = [0 for i in range(n)]
    for i in range(n):
        for j in range(n):
            if a_s[j] < a_s[i]:
                ts[i] += 1
                if j > i:
                    f_ts[i] += 1
    sum_f = sum(f_ts)
    sum_ = sum(ts)
    if (k - 1) % 2 == 0:
        ans = (sum_f + int(sum_ * (k - 1) / 2)) % MOD
        print(int(ans) % MOD * k % MOD)
    else:
        ans = 2 * sum_f + sum_ * (k - 1) % MOD
        print(int(ans) % MOD * int(k / 2) % MOD)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
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

N, K = (int(i) for i in input().split())
A = [int(i) for i in input().split()]
bit = Bit(2000)
ans = 0
hist = [0] * 3
for i in range(min(K, 3)):
    for j in range(N):
        ans = ans + i*N + j - bit.sum(A[j])
        bit.add(A[j], 1)
    hist[i] = ans
if K <= 3:
    print(ans)
else:
    ans = hist[0]
    a = (hist[1] - hist[0])
    d = (hist[2] - hist[1]) - (hist[1] - hist[0])
    ans = ans + (K-1) * (2*a + (K-2)*d) // 2
    print(int(ans % (1000000007)))

Submission status: Accepted

Solution code:
from sys import stdin
import math
import fractions
from collections import deque
from collections import Counter
import itertools

INF = 10 ** 10

MOD = 10**9 + 7

N, K = [int(x) for x in stdin.readline().rstrip().split()]
A = [int(x) for x in stdin.readline().rstrip().split()]

inv_t = [0]+[1]
for i in range(2,5):
  inv_t += [inv_t[MOD % i] * (MOD - int(MOD / i)) % MOD]

cnt = 0

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

cnt = cnt % MOD

if K >= 2:
    cnt = (cnt * K) % MOD

cnt2 = 0

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

    cnt2 = cnt2 % MOD

    tmp = ( (((K) * (K-1)) % MOD)) * inv_t[2]

    cnt2 = (cnt2 * tmp) % MOD

cnt = (cnt + cnt2) % MOD

print(int(cnt))

Submission status: Accepted

Solution code:
from decimal import *
n, k = map(int,input().split())
a = list(map(int,input().split()))
inner = 0
outer = 0
for i in range(0,n):
    for j in range(0,n):
        if a[i] > a[j]:
            outer += 1
            if i < j:
                inner += 1

print((Decimal(((inner) * (k)) + Decimal((outer) * Decimal((k) * (k-1)) / 2))%(1000000007)))

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A =list(map(int,input().split()))
pre_a = A[0]
ans =0
def sum(n):
    if n%2==0:
        return  (1+n)*(n//2)
    else:
        return  (1+n)*(n//2)+(n//2+1)

sumk = sum(K)
sumk1 = sum(K-1)
for i,a in enumerate(A):
    counter =0
    for b in A[i+1:]:
        if a > b:
            counter += 1

    ans += counter*sumk
    back = 0
    for c in A[:i]:
        if c < a:
            back += 1
    
    ans += back*sumk1
print(ans%(10**9+7))

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = [int(i) for i in input().split()]
g = {}
ans = 0
for i, a in enumerate(A):
    g[a] = N
    for j, b in enumerate(A):
        if a < b:
            g[a] -= 1
        if  i < j and a > b:
            ans += 1

ans = ans * K
S = (K * (K-1))//2
for v in A:
    i = g[v]
    ans += S * (N - i)

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

Submission status: Accepted

Solution code:
import sys

def input(): return sys.stdin.readline()[:-1]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def MATINT(h): return [list(map(int, input().split())) for _ in range(h)]
def MATSTR(h): return [input() for _ in range(h)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
inf = float('inf')
mod = 10 ** 9 + 7

def main():
    N, K = MAP()
    A = LIST()
    count = 0
    if K % 2 == 0:
        tmp1 = int(K / 2)
        tmp2 = K - 1
    else:
        tmp1 = K
        tmp2 = int((K - 1) / 2)
    for i in range(N):
        count_all = 0
        count_ = 0
        for j in range(N):
            if A[i] > A[j]:
                count_all += 1
                if i < j:
                    count_ += 1
        count += count_ * K % mod
        count += (((tmp1 * tmp2) % mod) * count_all) % mod
        count = count % mod
        # import pdb; pdb.set_trace()
    print(int(count) % mod)

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

#　そのブロック内での転倒数
ans1 = 0
for i in range(N):
    for j in range(i+1,N):
        if A[i] > A[j]:
            ans1 += 1

#　２つのブロック内での転倒数
ans2 = 0
B = sorted(A)
now = B[0]
cnt = 0
for i in range(1,N):
    if now != B[i]:
        cnt = i
        ans2 += cnt
        now = B[i]
    else:
        ans2 += cnt

ans11 = ans1 * K
ans22 = ans2 * (K * (K-1) // 2)
ans = ans11 + ans22
print(ans % MOD)

Submission status: Accepted

Solution code:
import sys
inputs = sys.stdin.readlines()

from itertools import cycle
N, K = map(int, inputs[0].split())
A = list(map(int, inputs[1].split()))
B_ = A + A
MOD = 10 ** 9 + 7

N, K
list(A+A)

counts = [0, 0]
for i in range(N):
    for j in range(i, N):
        if B_[i] > B_[j]:
            counts[0] += 1
for s in range(1, N):
    for i in range(N-s):
        if B_[i+s] > B_[N-1+s]:
            counts[1] += 1
print((counts[0] * K*(K+1)//2 + counts[1] * K*(K-1)//2) % MOD)

Submission status: Accepted

Solution code:
import copy


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


n, k = map(int, input().split())
a = list(map(int, input().split()))
b = copy.deepcopy(a)
tmp = [0] * n
initial = bubble_sort(a)
ans = initial
for i in range(n):
    cnt = 0
    for j in b:
        if b[i] > j:
            cnt += 1
    tmp[i] = cnt
d = sum(tmp)
ans = k * (2 * initial + d * (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()))
MOD = 1000000007
num = 0;
for i in range(N):
    Bi = A[i]
    n1 = 0
    for j in range(i):
        Bj = A[j]
        if(Bi > Bj):
            n1 += 1
    num += (K*(K-1)*n1//2)%MOD
    n2 = 0
    for j in range(i+1, N):
        Bj = A[j];
        if(Bi > Bj):
            n2 += 1;
    num += (K*(K+1)*n2//2)%MOD
print(num%MOD)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline
sys.setrecursionlimit(1000000)


def getN():
    return int(input())


def getList():
    return list(map(int, input().split()))


import math
MOD = 10 ** 9 + 7

n, k = getList()
anums = getList()

space = [[] for i in range(2002)]
remain = [1 for j in range(n)]
yet = n

for i, x in enumerate(anums):
    space[x].append(i)


ans = 0
for s in space:
    if s:
        jump = 0
        ls = len(s)
        yet -= ls
        for num in s:
            jump += sum(remain[:num])
            remain[num] = 0
            # print(jump)
        ans += ls * (yet * (k * (k-1))) // 2
        ans += jump * k
        # print(ans, jump, yet)
        # remain[num] = 0

        ans %= MOD
        # yet -= len(s)
        # yet -= 1
print(ans)
# print((43 * (998244353*998244354) // 2) % MOD)

Submission status: Accepted

Solution code:
import copy
import sys

input = sys.stdin.readline
n, k = map(int, input().split())
a = list(map(int, input().split()))
b = copy.deepcopy(a)

cnta = 0
cntc = 0

w = 10 ** 9 + 7

e = [0] * len(a)

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]

            e[i] += 1
# print(e)

f = [0] * len(b)
for i in range(len(b)):
    for j in range(len(b)):
        if b[i] > b[j]:
            f[i] += 1
# print(f)

wa = (k*(k - 1)//2) * sum(f)  + sum(e) * k
print(wa % w)

Submission status: Accepted

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

mod = 10 ** 9 + 7
ans = 0

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


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

print(ans % mod)

Submission status: Accepted

Solution code:
cnt=[]
before=[]
MOD=1000000007
n,k=map(int,input().split())
arr=list(map(int,input().split()))

for i in range(0,3010):
    cnt.append(0);
    before.append(0);

for i in range(n):
    count=0
    count1=0
    for j in range(i+1,n):
        if(arr[i]>arr[j]):
            cnt[i]+=1


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


sum=0
sum1=0
for i in range(n):
    x=(k*(k+1))//2
    y=cnt[i]*x
    sum=sum+y
    a=(k*(k-1))//2
    b=before[i]*a
    sum1=sum1+b
c=sum+sum1
print((c)%MOD)

Submission status: Accepted

Solution code:
import sys
from pprint import pprint

def solve(n, k, a):
    aa = a + a
    tr_n_a = 0
    for i in range(0, n-1):
        for j in range(i+1, n):
            if a[i] > a[j]:
                tr_n_a += 1
    # print(tr_n_a)

    tr_n = 0
    s_a = sorted(a, reverse=True)
    for i in range(0, n-1):
        for j in range(i+1, n):
            if s_a[i] > s_a[j]:
                tr_n += 1
    # print(tr_n)

    if tr_n == 0:
        print(0)
    else:
        print((tr_n * k * (k - 1) // 2 + tr_n_a * k) % (10**9 + 7))

if __name__ == '__main__':
  n, k = map(int, sys.stdin.readline().strip().split(" "))
  a = list(map(int, sys.stdin.readline().strip().split(" ")))
  solve(n, k, a)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)

from math import factorial
n,k=map(int,input().split())
a=list(map(int,input().split()))
p=10**9+7

def combi(m, r):
    if m - r < r: r = m - r
    if r == 0: return 1
    if r == 1: return m

    nume = [m - r + j + 1 for j in range(r)]
    deno = [j + 1 for j in range(r)]

    for l in range(2,r+1):
        pivot = deno[l - 1]
        if pivot > 1:
            offset = (m - r) % l
            for j in range(l-1,r,l):
                nume[j - offset] /= pivot
                deno[j] /= pivot

    result = 1
    for l in range(r):
        if nume[l] > 1:
            result *= int(nume[l])

    return result

cnt=0
cnt2=0
if n==1:
    print("0")
else:
    for i in range(n-1):
        for j in range(i+1,n):
            if a[i]>a[j]:
                cnt+=1
    if k==1:
        coef=1
    else:
        for i in range(n-1):
            for j in range(i+1,n):
                if a[i] < a[j]:
                    cnt2+=1
        coef=combi(k,2)
    print(int((coef*(cnt+cnt2)+cnt*k) % p))

Submission status: Accepted

Solution code:
from collections import defaultdict

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    MOD = 10 ** 9 + 7
    A2 = A + A
    d2 = defaultdict(int)
    for i in range(2*N):
        for j in range(i,2*N):
            if A2[i] > A2[j]:
                d2[A2[i]] += 1

    d = defaultdict(int)
    for i in range(N):
        for j in range(i,N):
            if A[i] > A[j]:
                d2[A2[i]] -= 1
                d[A[i]] += 1
    ans = 0

    for key,value in d2.items():
        ans += (K * ((2 * d[key] + (K - 1) * (value - d[key])))) // 2
        
    print(int(ans) % MOD)

main()

Submission status: Accepted

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

print(c)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
a2 = a + a
def tentou (l):
    count = [0]*len(l)
    for i in range(len(l)-1):
        for j in range(i+1,len(l)):
            if l[i] > l[j]:
                count[i] += 1
    return count
if n == 1:
    print(0)
else:
    a_v = tentou(a)
    a2_v = tentou(a2)
    mergin = [x-y-y for (x,y) in zip(a2_v,a_v)]
    if k == 1:
        S = sum(a_v)
        result = S % ((10**9) + 7)
    else:
        for i in range(len(a_v)):
            a_v[i] = a_v[i]*(k*(k+1))//2 + mergin[i]*(k*(k-1))//2
        S = sum(a_v)
        result = S % ((10**9) + 7)
        print(result)

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


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

N, K = MAP()
A = LIST()

B = []
for i in range(2):
    for a in A:
        B.append(a)
# print(B)
tenchi1 = bubble_sort(A)
tenchi2 = bubble_sort(B)

ni = tenchi2-2*tenchi1
# print(ni)

# tenchi = bubble_sort(A)
# print(tenchi)
# wa1 = 0.5 * (K) * (K+1)
wa2 =  (K) * (K-1) // 2
# wa2 = wa2
# ans1 = wa1 * tenchi1
# print("wa1", wa1)
# print("wa2", wa2)
# print("tenchi1", tenchi1)
# print("tenchi2", tenchi2)
# print("ni", ni)
ans1 = K*tenchi1
ans2 = wa2 * ni
ans = ans1 + ans2

ans = ans % mod
print(ans)

Submission status: Accepted

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

    k2 = k**2-((k**2-k)//2)

    o = [0]*n
    for i in range(n):
        a1 = a[:i]
        a2 = a[i+1:]
        a1 = len([j for j in a1 if j < a[i]]) * (k2-k)
        a2 = len([j for j in a2 if j < a[i]]) * (k2)
        o[i] = a1+a2
    print(sum(o)%(10**9+7))

if __name__ == "__main__":
    f_b()

Submission status: Accepted

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

Submission status: Accepted

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


K_1 = Decimal(K)*Decimal(1+K) / Decimal(2)
K_2 = (K_1 - Decimal(K)) % Decimal(MOD)
K_1 %= Decimal(MOD)

res_next = [0 for i in range(N)]
for i in range(N):
    a = As[i]
    for j in range(i+1, N):
        if a > As[j]:
            res_next[i] += 1

res_prev = [0 for i in range(N)]

for i in range(N):
    a = As[i]
    for j in range(i):
        if a > As[j]:
            res_prev[i] += 1

ans = Decimal(0)

for i in range(N):
    ans += (Decimal(res_next[i]) * K_1) % Decimal(MOD)
    ans %= Decimal(MOD)
    ans += (Decimal(res_prev[i]) * K_2) % Decimal(MOD)
    ans %= Decimal(MOD)

print(int(ans))

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a_list = list(map(int, input().split()))
ans = 0
a_2_list = a_list * 2
sorted_a = sorted(a_list, reverse=True)

for i in range(n):
  for j in range(i+1, n):
    if a_list[i] > a_list[j]:
      ans += k

for i in range(n):
  indexes = [j for j, x in enumerate(sorted_a) if x == a_list[i]]
  ans += (n-indexes[-1]-1) * k*(k-1)//2%(10**9+7)

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

Submission status: Accepted

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

import sys
from functools import reduce

X = 10 ** 9 + 7

def main() -> int:
    ls = sys.stdin.read().splitlines()
    [n, k] = [int(x) for x in ls[0].split(' ')]
    xs = [int(x) for x in ls[1].split(' ')]
    first = [len([x for x in xs[:i] if x > xs[i]]) for i in range(n)]
    xsxs = xs * 2
    ds = [
            len([x for x in xsxs[:i] if x > xsxs[i]]) - first[i - n]
            for i in range(n, 2 * n)]
    ss = [k * (2 * first[i] + (k - 1) * ds[i]) // 2 for i in range(n)]
    print(sum(ss) % X)
    return 0


if __name__ == "__main__":
    exit(main())

# vim:fenc=utf-8 ff=unix ft=python ts=4 sw=4 sts=4 fdm=indent fdl=0 fdn=1:
# vim: si et cinw=if,elif,else,for,while,try,except,finally,def,class:

Submission status: Accepted

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

Submission status: Accepted

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

count = 0
for index, i in enumerate(a):
    for j in a[index+1:]:
        if i > j:
            count += k * (k + 1) // 2
        elif i < j:
            count += (k - 1) * k // 2

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

Submission status: Accepted

Solution code:
import numpy as np

MOD = 1000000007

def count_inv2(a):
    count = 0
    prev = a[a.shape[0] - 1]
    m = 1
    for j in range(a.shape[0] - 2, -1, -1):
        if prev > a[j]:
            count += m * (j + 1)
            prev = a[j]
            m = 1
        else:
            m += 1
    return count


def count_inv(a):
    count = 0
    for i in range(len(a)):
        for j in range(i + 1, len(a)):
            if a[i] > a[j]:
                count += 1
    return count


stdin = open(0, 'rb')
N, K = map(int, stdin.readline().split())
A = np.fromstring(stdin.readline(), dtype=np.int64, sep=' ')
x = count_inv(A)
y = count_inv2(np.sort(A))
ans = (K * x + K*(K - 1) // 2 * y) % MOD
print(ans)

Submission status: Accepted

Solution code:
n,k =map(int,input().split())
A =list(map(int,input().split()))
plus=[0]*(n)
C=[0]*2001
for i in range(n):
	for j in range(A[i]):
		C[j]+=1
# print(C[:5])
	plus[i]=C[A[i]]
count=0
for i in range(n):
	count+=plus[i]*(k)
	# print(count)
	count+=C[A[i]]*k*(k-1)//2
	count=count%(10**9+7)
# 	print(count)
# print(plus)
# print(C[:5])
print(count)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
Mod=10**9+7
ans_first=0
ans_sec=0
for i in range(len(A)-1):
  for j in range(i,len(A)):
    if A[i]>A[j]:
      ans_first+=1
for i in A:
  for j in A:
    if i > j:
      ans_sec+=1
if K%2==0:
  tmp=(2*ans_first+(K-1)*ans_sec)%Mod
  K=K//2
  ans=(tmp*K)%Mod
else:
  tmp=(ans_first+(K-1)//2*ans_sec)%Mod
  ans=(tmp*K)%Mod
print(ans)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A = list(map(int,input().split()))
MOD = 1000000007
cnt = 0
for i in range(N-1):
  for j in range(i+1,N):
    if ( A[i] > A[j] ):
      cnt += 1

AS = sorted(A, reverse=True)
sumn = 0
tmp = 0
for i in range(1,N):
  if AS[i] != AS[i-1]:
    tmp = i
  sumn += tmp


if K%2==0:
  mulk = K * ((K-1)//2) + (K//2)
else:
  mulk = K * ((K-1)//2)
mulk %= MOD 
#print( cnt, sumn , mulk, (N-1)//2 );
print ( ((cnt * K)%MOD  + (sumn * mulk) % MOD) %MOD)

Submission status: Accepted

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

    l = []
    r = []
    for i in range(N):
        lc = 0
        rc = 0
        for j in range(N):
            if A[i] > A[j]:
                if i > j:
                    lc += 1
                else:
                    rc += 1
        l.append(lc)
        r.append(rc)
        
    an = K * (K + 1) // 2 % mod
    for i in range(N):
        sum_r = an * r[i]
        sum_l = (an - K) * l[i]
        ans += sum_r + sum_l
        ans %= mod
	
    print(ans)


if __name__ == '__main__':
    p_b()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
ans=0
C=0
for t in range(n):
  for T in range(n):
    if a[t]>a[T]:
      C+=1
      C%=(10**9+7)
      
w=len(list(set(a)))
#if w!=1:
#  q=((w*(w-1))//2)%(10**9+7)
if w==1:
  print(0)
  exit()

if k>=2:
  e=((k*(k-1))//2)%(10**9+7)
elif k==1:
  e=1

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

count=0
for i in range(n):
  for j in range(n):
    if i<j:
      if a[i]>a[j]:
        count+=1
        count%=(10**9+7)
k%=10**9+7
ans+=(count*k)%(10**9+7)

ans%=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()))
kk=k-1

cnt=0
res=0
for i in range(n):
    cnt=0
    rev=0

    for j in range(i+1,n):
        if a[i]>a[j]:
            cnt+=1
        if a[i]<a[j]:
            rev+=1
    res+=rev*((kk+1)*kk)//2
    res+=cnt*((k+1)*k)//2
    res%=mod

print(res)

Submission status: Accepted

Solution code:
import copy

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

const = 1000000007
c = 0
d = 0

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

b = copy.deepcopy(a)

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

# print("c", c)

# print("d", d)

ans = c * k + d * (k * (k - 1) // 2)

print(int(ans) % const)

Submission status: Accepted

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right
from heapq import heappush, heappop

import re
# import numpy as np
# from scipy.misc import comb

# 再帰がやばいとき
import sys
sys.setrecursionlimit(10**9)

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e30)
MOD = int(1e9)+7 # 10^9 + 7

# field[H][W]
def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]

########

def count_inversion(sequence):
    count = 0
    for i in range(1,len(sequence),1):
        for j in range(i,len(sequence),1):
            if sequence[i-1] > sequence[j]:
                count += 1
    return count

def power_func(a,n,p):
  bi=str(format(n,"b"))#2進表現に
  res=1
  for i in range(len(bi)):
    res=(res*res) %p
    if bi[i]=="1":
      res=(res*a) %p
  return res

def main():
    N, K = l_inpl()
    A = l_inpl()
    a1 = count_inversion(A)
    b1 = (count_inversion(A*2) - count_inversion(A))
    b2 =  (count_inversion(A*3) - count_inversion(A*2))
    c1 = b2 - b1
    print((a1*K+c1*(K%MOD)*((K-1)%MOD)//2)%MOD)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import bisect
input = sys.stdin.readline
 
def main():
    n,k = map(int,input().split())
    a=list(map(int,input().split()))
    cnta=0
    cntb=0
    for i in range(n-1):
        for j in range(n-1-i):
            j+=i+1
            if(a[i]>a[j]):
                cnta+=1
    for i in range(n):
        for j in range(n):
            if(a[i]>a[j] and i!=j):
                cntb+=1
    cntak=int(  (cnta*k) % (1000000007)  )
    x=int(  ((k*(k-1))//2) % (1000000007)  )
    cntbk=int(  (cntb*x) % (1000000007)  )
    
    ans=int(  (cntak+cntbk) % (1000000007)  )
    
    print(ans)
    
main()

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


def bubble_sort(a):
    b = a[:]
    cnt = 0
    n = len(b)
    for i in range(n):
        for j in range(n - 1, i, -1):
            if b[j] < b[j - 1]:
                b[j], b[j - 1] = b[j - 1], b[j]
                cnt += 1
                cnt %= mod
    return cnt, b


mod = 10 ** 9 + 7

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

cnt, b = bubble_sort(a)
ans = cnt * k
ans %= mod
# print(ans)

b.sort(reverse=True)
# print(b)
dd = dict()

sm = 0
for i, bb in enumerate(b):
    if dd.get(bb, None) is None:
        dd[bb] = i
        sm += i
    else:
        sm += dd[bb]

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

print(ans)

Submission status: Accepted

Solution code:
from decimal import *

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

a = Decimal(str(K - 1))
b = Decimal(str(K))
c = Decimal(str(K + 1))

d = Decimal(a*b/2)
e = Decimal(b*c/2)

#print(a)
#print(b)
#print(c)
#print(d)
#print(e)

d = d % 1000000007
e = e % 1000000007

#print(d)
#print(e)

#count1 = (K * (K+1) / 2) % 1000000007
#count2 = ((K-1) * K / 2) % 1000000007
count1 = int(e)
count2 = int(d)

#print(count1)
#print(count2)

for i in range(N):

  for j in range(N):

    if A[i] > A[j]:
      if i < j:
        Ans = Ans + count1
      else:
        Ans = Ans + count2
      
      if Ans > 1000000007:
        Ans = Ans % 1000000007  


print(int(Ans))