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 = 1000000007

ans = 0

for i in range(n):
    # 内部での転倒数
    cnt = 0
    for j in range(i):
        if a[i] < a[j]:
            cnt += 1

    # 全体
    cnt2 = 0
    for j in range(n):
        if a[i] < a[j]:
            cnt2 += 1

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

print(ans)

Submission status: Accepted

Solution code:
from sys import stdin

n, k = map(int, stdin.readline().rstrip().split())
a = map(int, stdin.readline().rstrip().split())

a = list(a) 
count = 0 
for i in range(1, n):
    for j in range(i):
        if a[j] > a[i]:
            count += 1
import copy
b = copy.copy(a)
b.sort()
count *= k
import bisect
ans2 = 0
for i in range(n):
  ans2 += bisect.bisect_left(b, a[i])
print((count + ans2 * (((k-1)* k)//2))%(1000000007))

Submission status: Accepted

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

def sum_n(n):
    return (n * (n+1))//2

ans = 0
left = [0] * N
right = [0] * N
for i in range(N):
    a = Alist[i]
    in_left = True
    for j in range(N):
        if i == j:
            in_left = False
            continue
        else:
            if Alist[j] < a:
                if in_left:
                    left[i] += 1
                else:
                    right[i] += 1
    ans += right[i] * sum_n(K)
    ans += left[i] * sum_n(K-1)
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(300000)
from collections import defaultdict

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


N, K = MI()
A = LMI()

# P[i] := i番目より後ろにA[i]より小さい数がいくつあるか
# U[i] := A全体でA[i]より小さい数がいくつあるか
P = [0] * N
U = [0] * N
d = defaultdict(int)
for i, a in enumerate(reversed(A)):
    i = N - 1 - i
    cnt = 0
    for j in range(a):
        cnt += d[j]
    P[i] = cnt
    d[a] += 1
for i, a in enumerate(A):
    cnt = 0
    for j in range(a):
        cnt += d[j]
    U[i] = cnt

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def count_section_by_zero(data):
  count = 0
  flg = False
  start = 0
  for i, d in enumerate(data):
    if flg is False and d != 0:
      count += 1
      flg = True
      
    if d == 0:
      flg = False
  return count

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

def input_list_str():
  return list(map(str, input().split()))

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

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

# 2で割り切れる回数
def divide_two(arg):
  c = 0
  while True:
    if c >= 2:
      break
    if arg % 2 != 0:
      break
    arg //= 2
    c += 1
  return c

# 素因数分解
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

def main():
  n,k = input_list()
  a = input_list()
  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 += k*(k-1) // 2 + k
        ans %= mod
      elif i > j and a[i] > a[j]:
        ans += k*(k-1) // 2
        ans %= mod
  print(ans)
import math
import fractions
import collections
import itertools
from functools import reduce
main()

Submission status: Accepted

Solution code:
import copy
N,K=map(int,input().split())
A=list(map(int,input().split()))
tentou1=0
tentou2=0
l2=copy.deepcopy(A)
l2.extend(A)
p=10**9+7
#print(l2,A)
for i in range(N):
    for j in range(i+1,N):
        #print(i,j)
        if A[i]>A[j]:
            tentou1=tentou1+1
for i in range(2*N):
    for j in range(i+1,2*N):
        if l2[i]>l2[j]:
            tentou2=tentou2+1
#print(tentou1,tentou2)
n=(tentou2-tentou1)-tentou1
#for i in range(10):
#    print((i*(3*tentou1-tentou2)+n*(i*(i+1))//2)%p)

print((K*(3*tentou1-tentou2)+n*(K*(K+1))//2)%p)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from bisect import bisect_left


class BIT:  # 0-indexed
    def __init__(self, n):
        self.tree = [0] * (n + 1)
        self.tree[0] = None

    def sum(self, i):  # a_0 + ... + a_{i} #閉区間
        s = 0
        i += 1
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def range(self, l, r):  # a_l + ... + a_r 閉区間
        return sum(r) - sum(l - 1)

    def add(self, i, x):
        i += 1
        while i <= n:
            self.tree[i] += x
            i += i & -i


n, k = map(int, readline().split())
a = list(map(int, readline().split()))
s_a = sorted(a)
mod = 10 ** 9 + 7
bit = BIT(n)
res = [0] * n
ans = 0
for i, b in enumerate(a):
    j = bisect_left(s_a, b)
    res[i] = i - bit.sum(j)
    bit.add(j, 1)
for i, b in enumerate(a):
    ans += k * res[i]
    ans %= mod
    j = bisect_left(s_a, b)
    ans += (k * (k - 1) // 2 % mod) * (n - bit.sum(j))
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
P = 10**9 + 7

N, K = map(int, input().split())
A = [int(i) for i in input().split()]

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

y1 = (K * (K+1) // 2) % P
y2 = ((K-1) * K // 2) % P

ans = (x1*y1 + x2*y2) % P
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):
    left = 0
    right = 0
    for j in range(N):
        if A[i] > A[j]:
            if j < i:
                left += 1
            else:
                right += 1
    
    ans += right * K * (K+1) // 2
    ans += left * K * (K-1) // 2

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

Submission status: Accepted

Solution code:
MOD = 10**9+7

def resolve():
  ans = 0
  q1 = 0
  n, k = map(int, input().split())
  a = list(map(int, input().split()))
  c = [0] * n  # 自分より小さい値が全体に何個あるか
  for i in range(n):
    for j in range(i, n):
      if a[i] > a[j]:
        q1 += 1  

  ans = q1 * k % MOD

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

  s = (k * (k - 1)) // 2
  s %= MOD

  ans += (s * q2) % MOD

  print(int(ans % MOD))
  return  

if __name__ == "__main__":
  resolve()

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
MOD=10**9+7
ans=0
C=[0 for _ in range(max(A)+1)]
for i in range(N-1):
    for j in range(i+1,N):
        a=A[j]-A[i]
        if a<0:
            #ans+=1
            C[A[i]]+=1
D=[0 for i in range(max(A)+1)]
for i in range(N):
    for j in range(N):
        if i==j:
            continue
        a=A[i]-A[j]
        if a>0:
            D[A[i]]+=1

for i in range(len(C)):
    a=K*C[i]%MOD
    ans+=a
k=(K*(K-1))//2
k=k%MOD
for i in range(len(D)):
    b=k*D[i]%MOD
    ans+=b
print(ans%MOD)

Submission status: Accepted

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

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

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

tmp1 = (K-1)*K//2 %mod * q2 %mod
tmp2 = q1*K%mod
ans = (tmp1 + tmp2)%mod
print(int(ans))

Submission status: Accepted

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

Before = []
After = []

for i in range(n):
    now = A[i]
    before = 0
    after = 0
    for j in range(i):
        if now > A[j]:
            before += 1
    for l in range(i+1,n):
        if now > A[l]:
            after += 1
    Before.append(before)
    After.append(after)

ans = 0
mod = 10**9+7
for i in range(n):
    if k%2 == 0:
        multi_one = int(k/2) * (k-1) % mod
        multi_two = int(k/2) * (k+1) % mod 
    else:
        multi_one = int((k-1)/2) * k % mod
        multi_two = int((k+1)/2) * k % mod
    plus = multi_one*Before[i]%mod + multi_two*After[i]%mod
    ans = (ans + plus) % mod

print(ans)

Submission status: Accepted

Solution code:
def solve():
    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 i < j and A[i] > A[j]:
                ans += K*(K-1) // 2 + K
                ans %= mod
            elif i > j and A[i] > A[j]:
                ans += K*(K-1) // 2
                ans %= mod
    
    print(ans)

if __name__ == '__main__':
    solve()

Submission status: Accepted

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

def main():
    N,M = map(int,input().split())
    a = list(map(int,input().split()))
    MOD = 10**9+7
    
    num = 0
    for i in range(N):
        for j in range(i+1,N):
            if a[i] > a[j]:
                num += 1

    if M == 1:
        print(num%MOD)
    else:
        num *= M
        num %= MOD
        a += a
        count = 0
        for i in range(N):
            for j in range(N,2*N):
                if a[i] > a[j]:
                    count += 1

        count *= ((M*(M-1))//2)
        count %= MOD
        num += count
        print(num%MOD)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
a = a
b = a*2
a1 = 0
a2 = 0
m = 10**9+7
for i in range(n):
    a1 += len([j for j in a[i:] if j < a[i]])
for i in range(2*n):
    a2 += len([j for j in b[i:] if j < b[i]])

ans =((a1*k*(k+1)//2) + ((a2 - 3*a1) * (k-1)*k//2 % m) % m) % m

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    length, repeat = map(int, input().split())
    sequence = list(map(int, input().split()))
    mod = 10 ** 9 + 7
    base_inversion = 0
    inter_inversion = 0
    count = [0] * 2001
    for i in range(length):
        count[sequence[i]] += 1
        for j in range(i + 1, length):
            if sequence[i] > sequence[j]:
                base_inversion += 1
    for i in range(length):
        inter_inversion += sum(count[:sequence[i]])
    print((base_inversion * repeat + inter_inversion * repeat * (repeat - 1) // 2) % mod)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import Counter
def input():
    return sys.stdin.readline()[:-1]


def main():

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

    fall_count_in = 0
    fall_count_out = 0
    for i,ai in enumerate(A):
        for j,aj in enumerate(A):
            if i == j:
                continue
            if ai > aj:
                fall_count_out += 1
                if i < j:
                    fall_count_in += 1

    ans = fall_count_out * K * (K-1) // 2 + fall_count_in * K
    print(ans % MOD)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
l=list(map(int,input().split()))
sl=sorted(l)
ten=0
jiten=0
for i in range(n):
    for j in range(n):
        if l[i]>l[j]and i<j:ten+=1
        if l[i]<l[j]:jiten+=1
print((ten*k+jiten*(k*(k-1))//2)%1000000007)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
l=list(map(int,input().split()))
sl=sorted(l)
ten=0
for i in range(n):
    for j in range(n):
        if l[i]>l[j]and i<j:ten+=1
pre=sl[0]
jiten=0
c=0
for i,x in enumerate(sl):
    if x==pre:jiten+=c
    else:
        jiten+=i
        c=i
        pre=x

print((ten*k+jiten*(k*(k-1))//2)%(10**9+7))

Submission status: Accepted

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n, k, *a = map(int, open(0).read().split())

MOD = int(1e9+7)
m = MOD -2
re = 1
s = 2
while m:
        if m&1: re = re*s % MOD
        s = s * s % MOD
        m >>= 1
f = (k+1) * k * re
g = k * (k-1) * re

l = r = 0
for i in range(n):
        for j in range(n):
                if a[i]>a[j]:
                        if i>j: l += 1
                        else: r += 1
print((l*g+r*f) % MOD)

Submission status: Accepted

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

    #A内での転倒数t1
    bit = BinaryIndexedTree(2001)
    t1 = Mint()
    for i,a in enumerate(reversed(A)):
        t1 += bit.query(a-1)
        bit.add(a,1)
    
    #ひとつ左のAへの転倒数t2
    t2 = Mint()
    for a in A:
        t2 += bit.query(a-1)

    K2 = K * (K - 1) // 2
    ans = t1 * K + t2 * K2
    print(ans)

class BinaryIndexedTree:
    def __init__(self, n=None, f=lambda x,y:x+y, zero=0, initial_values=None):
        assert(n or initial_values)
        self.__f, self.__z, = f, zero
        self.__n = n if n else len(initial_values)
        self.__dat = [zero] * (self.__n + 1)
        if initial_values:
            for i in range(1, self.__n + 1): self.add(i, initial_values[i-1]) #slow

    def add(self, i, v):
        i += 1
        while i <= self.__n:
            self.__dat[i] = self.__f(self.__dat[i], v)
            i += -i&i

    def query(self, r):
        r += 1
        ans = self.__z
        while r:
            ans = self.__f(ans, self.__dat[r])
            r -= -r&r
        return ans
    
class Mint:
    def __init__(self, value=0, mod=10**9+7):
        self.value = ((value % mod) + mod) % mod
        self.mod = mod

    @staticmethod
    def get_value(x): return x.value if isinstance(x, Mint) else x

    def inverse(self):
        a, b = self.value, self.mod
        u, v = 1, 0
        while b:
            t = a // b
            b, a = a - t * b, b
            v, u = u - t * v, v
        return (u + self.mod) % self.mod

    def __repr__(self): return str(self.value)
    def __eq__(self, other): return self.value == other.value
    def __neg__(self): return Mint(-self.value, self.mod)
    def __hash__(self): return hash(self.value)
    def __bool__(self): return self.value != 0

    def __iadd__(self, other):
        self.value = (self.value + Mint.get_value(other)) % self.mod
        return self
    def __add__(self, other):
        new_obj = Mint(self.value, self.mod)
        new_obj += other
        return new_obj
    __radd__ = __add__

    def __isub__(self, other):
        self.value = (self.value - Mint.get_value(other) + self.mod) % self.mod
        return self
    def __sub__(self, other):
        new_obj = Mint(self.value, self.mod)
        new_obj -= other
        return new_obj
    def __rsub__(self, other):
        new_obj = Mint(Mint.get_value(other), self.mod)
        new_obj -= self
        return new_obj

    def __imul__(self, other):
        self.value = self.value * Mint.get_value(other) % self.mod
        return self
    def __mul__(self, other):
        new_obj = Mint(self.value, self.mod)
        new_obj *= other
        return new_obj
    __rmul__ = __mul__

    def __ifloordiv__(self, other):
        other = other if isinstance(other, Mint) else Mint(other, self.mod)
        self *= other.inverse
        return self
    def __floordiv__(self, other):
        new_obj = Mint(self.value, self.mod)
        new_obj //= other
        return new_obj
    def __rfloordiv__(self, other):
        new_obj = Mint(Mint.get_value(other), self.mod)
        new_obj //= self
        return new_obj

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from fractions import gcd
from math import sqrt,asin,degrees
from collections import deque,defaultdict,Counter
from heapq import heapify,heappop,heappush
from copy import deepcopy
from itertools import accumulate,permutations
from bisect import bisect_left,bisect_right

N, K = map(int,input().split())
A = [int(i) for i in input().split()]

MOD = 10**9 + 7

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

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

tmp = (K * (K - 1)) // 2 % MOD

ans = (K * B) % MOD
ans = (ans + tmp * C) % MOD

print(ans)

Submission status: Accepted

Solution code:

mod = 1000000007

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

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

    print(ans)


if __name__ == '__main__':
    main()

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 STR(): return input()
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 = sys.maxsize
mod = 10 ** 9 + 7
n,k = MAP()
a = LIST()
b = [0 for _ in range(n)] #その配列のあとで
c = [0 for _ in range(n)] #配列全体で
for i in range(n):
    for j in range(i+1, n):
        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
tt = k * (k - 1) // 2
ans = (k * sum(b) % mod + tt * sum(c) % mod) % mod
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_right

mod = 10**9+7
N, K = map(int, input().split())
A = list(map(int, input().split()))
A_front = []
A_sorted = sorted(A)
ans = 0
for a in A:
    ans += (N - bisect_right(A_sorted, a)) * K*(K-1)//2
    ans %= mod
    i = bisect_right(A_front, a)
    ans += (len(A_front) - i) * K
    ans %= mod
    A_front.insert(i, a)
print(ans)

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
class BIT:
  def __init__(self, n):
    self.n = n
    self.data = [0] * (n + 1)
    self.el = [0] * (n + 1)
  def sum(self, i):
    s = 0
    while i > 0:
      s += self.data[i]
      i -= i & -i
    return s
  def add(self, i, x):
    self.el[i] += x
    while i <= self.n:
      self.data[i] += x
      i += i & -i
  def get(self, i, j = None):
    if j is None:
      return self.el[i]
    return self.sum(j) - self.sum(i)

fwk = BIT(2001)
res = 0
for i in range(N):
  res += fwk.get(a[i], 2001)
  res %= mod
  fwk.add(a[i], 1)
res *= K
res %= mod

for i in range(N):
  res += (K * (K - 1) // 2) % mod * fwk.get(a[i], 2001) % mod
  res %= mod
print(res)

Submission status: Accepted

Solution code:
def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# mを法とするaの乗法的逆元
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

# nCr mod m
# modinvが必要
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10 ** 9 + 7):
    r = min(r, n - r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i + 1, mod) % mod
    return res

n, k = map(int, input().split())
dat = list(map(int, input().split()))
datAfter = [0] * n
datSelf = [0] * n
numAfter = 0
numSelf = 0
m = 10**9 + 7
for i in range(n):
    for j in range(i+1, n):
        if dat[i] > dat[j]:
            numAfter += 1
for i in range(n):
    for j in range(n):
        #print(dat[i], dat[j])
        if dat[i] > dat[j]:
            numSelf += 1
res = 0
res += numAfter * k
res += numSelf * combination(k, 2)
res %= m
#print(numSelf, numAfter, res)
print(res)

Submission status: Accepted

Solution code:
N, K=map(int, input().split())
A=list(map(int, input().split()))
A+=A
tmp=[0]*2001
S1=[0]*N
S2=[0]*N
for i in range(1, N):
  tmp[A[i-1]]+=1
  S1[i]=sum(tmp[A[i]+1:])
tmp[A[-1]]+=1
S2[0]=sum(tmp[A[0]+1:])
for i in range(1, N):
  tmp[A[i-1]]+=1
  S2[i]=sum(tmp[A[i]+1:])
S2=[S2[i]-S1[i] for i in range(N)]
print((K*sum(S1)+sum(S2)*K*(K-1)//2)%(10**9+7))

Submission status: Accepted

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

cnt_list = [[0, 0] for _ in range(N)]
for i in range(N):
    right = 0
    left = 0
    for j in range(N):
        if i < j:       # right
            if A[i] > A[j]:
                right += 1
        else:           # left
            if A[i] > A[j]:
                left += 1
    cnt_list[i][0] = left
    cnt_list[i][1] = right
ans = 0
for i in range(N):
    left = cnt_list[i][0]
    right = cnt_list[i][1]
    ans += left * (K - 1) * K // 2
    ans += right *  K * (K + 1) // 2
    ans %= mod
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
mod = 10**9+7
ans =0
for i in range(N):
    df = 0
    db = 0
    for j in range(i):
        if A[j] < A[i]:
            df +=1
    for k in range(i+1,N):
        if A[k] < A[i]:
            db +=1
    D = K*(K+1)//2
    L = D * (df+db) - K * df
    L %= mod
    ans +=L
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_right
n, k, *a = map(int, sys.stdin.read().split())

mod = 1000000007
ans = 0
for i in range(n-1):
    for j in range(i+1, n):
        if a[i] > a[j]:
            ans += 1
ans = k * ans % mod
a.sort()
cnt = 0
for ai in a:
    cnt += n - bisect_right(a, ai)
ans += (k * (k - 1) // 2) % mod * cnt
print(ans % mod)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,k = map(int, input().split())
a = list(map(int, input().split()))
soa = sorted(a)
import bisect
ans=0
for i in range(len(a)):
    cnt = bisect.bisect_left(soa,a[i])
    slf=0
    for j in range(i,len(a)):
        if a[i] > a[j]:
            slf+=1
    sm = k*(k-1)*cnt // 2 + slf*k
    ans+=sm
mod=10**9+7
print(ans%mod)

Submission status: Accepted

Solution code:
class BinaryIndexedTree:
    def __init__(self, N):
        self.N = N
        self.bit = [0] * (self.N+1)

    def sum(self, i):
        res = 0
        while i > 0:
            res += self.bit[i]
            i -= i & -i
        return res

    def add(self, i, x):
        while i <= self.N:
            self.bit[i] += x
            i += i & -i

MOD=10**9+7
class Fp(int):
    def __new__(self,x=0):return super().__new__(self,x%MOD)
    def inv(self):return self.__class__(super().__pow__(MOD-2,MOD))
    def __add__(self,value):return self.__class__(super().__add__(value))
    def __sub__(self,value):return self.__class__(super().__sub__(value))
    def __mul__(self,value):return self.__class__(super().__mul__(value))
    def __floordiv__(self,value):return self.__class__(self*self.__class__(value).inv())
    def __pow__(self,value):return self.__class__(super().__pow__(value%(MOD-1), MOD))
    __radd__=__add__
    __rmul__=__mul__
    def __rsub__(self,value):return self.__class__(-super().__sub__(value))
    def __rfloordiv__(self,value):return self.__class__(self.inv()*value)
    def __iadd__(self,value):self=self+value;return self
    def __isub__(self,value):self=self-value;return self
    def __imul__(self,value):self=self*value;return self
    def __ifloordiv__(self,value):self=self //value;return self
    def __ipow__(self,value):self=self**value;return self
    def __neg__(self):return self.__class__(super().__neg__())

N,K,*A=map(int, open(0).read().split())
bit=BinaryIndexedTree(2001)
c=0
for i,a in enumerate(A):
    c+=i-bit.sum(a)
    bit.add(a,1)
d=0
for i,a in enumerate(A):
    d+=N-bit.sum(a)
K=Fp(K)
print(K*c+K*(K-1)//2*d)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
A = list(map(int, input().split()))
counts = [[0, 0] for _ in range(n)]
for i in range(n):
  for j in range(n):
    if A[i] < A[j]:
      if i > j:
        counts[i][0] += 1
      if i < j:
        counts[i][1] += 1

total = 0
for i in range(n):
  total += counts[i][0] * (k * (k + 1) // 2) + counts[i][1] * (k * (k - 1) // 2)
  total %= 1000000007

print(total)

Submission status: Accepted

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

MOD = 1000000007  # type: int


def solve(N: int, K: int, A: "List[int]"):
    al = [0] * N
    bl = [0] * N
    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            elif A[i] > A[j]:
                al[i] += 1
                if i < j:
                    bl[i] += 1

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

    
    print(ans%MOD)
    
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N - 1 - 0 + 1)]  # type: "List[int]"
    solve(N, K, A)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

if __name__=="__main__":
  main()

Submission status: Accepted

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

if __name__=="__main__":
  main()