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:
# -*- coding: utf-8 -*-
n,k = map(int, input().split())
al = list(map(int, input().split()))
MOD = 10**9+7

d = {}
for a in al:
    if a not in d:
        d[a] = 0
    d[a] += 1

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

for i in range(n):
    r = 0
    for key in d:
        if al[i]>key:
            r += d[key]
    res += r*k*(k-1)//2
    res %= MOD

print(res)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
n,k=map(int,input().split())
a=list(map(int,input().split()))
A=sorted(a)
shokou=[]
kousa=[]
m=10**9+7
for i in range(n):
  ct=0
  for j in range(i+1,n):
    if a[i]>a[j]:ct+=1
  shokou.append(ct)
for i in range(n):
  kousa.append(A.index(a[i]))
ans=0
S=0
for i in range(n):
  S=(k*(2*shokou[i]+(k-1)*kousa[i]))//2
  S%=m
  ans+=S
print(ans%m)

Submission status: Accepted

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

# O(N^2)
cnt_self = 0
cnt_left = 0
for i in range(N - 1):
    for j in range(i + 1, N):
        if A[i] > A[j]:
            cnt_self += 1
        if A[i] != A[j]:
            cnt_left += 1

ans = 0
ans = (ans + (K * cnt_self)) % (10 ** 9 + 7)

coeff = (K * (K - 1) // 2) % (10 ** 9 + 7)
ans = (ans + (coeff * cnt_left)) % (10 ** 9 + 7)

print(ans)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
inside = 0
for i in range(n):
  for j in range(i+1,n):
    if a[i] > a[j]:
      inside += 1
inside *= k
mod = 10**9+7
a.sort()
b = [0]
for i in range(1,n):
  if a[i-1] == a[i]:
    b.append(b[-1])
  else:
    b.append(i)
outside = sum(b)
kk = k * (k-1) // 2
kk %= mod
outside *= kk
outside %= mod
ans = (inside + outside) % 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

# 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

ans = 0
pre = []
from bisect import *
for i in range(N):
    a = a_list[i]
    for j in range(i + 1, N):
        b = a_list[j]
        if a > b:
            ans += (K + 1) * K // 2
            ans %= mod
    idx = bisect_left(pre, a)
    ans += idx * ((K-1)*K//2)
    ans %= mod
    insort_left(pre, a)
print(ans)

Submission status: Accepted

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

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

total = count1 * k + count2 * k * (k - 1) // 2
print(total % (10 ** 9 + 7))

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
l=[0]*n
r=[0]*n
MOD=10**9+7
for i in range(n):
    for j in range(n):
        if a[i]<a[j] and i<j:
            r[i]+=1
            continue
        if i>j and a[i]<a[j]:
            l[i]+=1
            continue
s=sum(l)
count=0
count+=k*(k+1)//2*s%MOD
s2=sum(r)
count+=k*(k-1)//2*s2%MOD
print(count%MOD)

Submission status: Accepted

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


class BinaryIndexedTree:
    # http://hos.ac/slides/20140319_bit.pdf
    def __init__(self, size):
        """
        :param int size:
        """
        self._bit = [0] * size
        self._size = size

    def add(self, i, w):
        """
        i 番目に w を加える
        :param int i:
        :param int w:
        :return:
        """
        x = i + 1
        while x <= self._size:
            self._bit[x - 1] += w
            x += x & -x

    def sum(self, i):
        """
        0 番目から i 番目までの合計
        :param int i:
        :return:
        """
        ret = 0
        x = i + 1
        while x > 0:
            ret += self._bit[x - 1]
            x -= x & -x
        return ret

    def __len__(self):
        return self._size


def count_inversions(li, max=None):
    if not max:
        max = __builtins__.max(li)
    bit = BinaryIndexedTree(size=max + 1)
    ret = 0
    for i in range(len(li)):
        ret += i - bit.sum(li[i])
        bit.add(li[i], 1)
    return ret


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

bit = BinaryIndexedTree(size=2001)
invs = []
for i, a in enumerate(A):
    invs.append(i - bit.sum(a))
    bit.add(a, 1)
ans = 0
for i, a in enumerate(A):
    rem = N - bit.sum(a)
    ans += K * (2 * invs[i] + (K - 1) * rem) // 2
    ans %= MOD
print(ans)

Submission status: Accepted

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

cnt = [0] * 2001
for i in range(n):
    cnt[a[i]] += 1

ruiseki = [0] * (2000 + 1 + 1)
for i in range(2000 + 1):
    ruiseki[i+1] = ruiseki[i] + cnt[i]

ans = 0
for i in range(n):
    num = a[i]
    ans += (ruiseki[num] * (k - 1) * k) // 2
    ans %= MOD
    for j in range(i, n):
        if a[i] > a[j]:
            ans += k
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
mod = 10**9+7
N,K=map(int,input().split())
A = [int(i) for i in input().split()]

tento = []
ookii = []#自分より大きい数のあつまり
for i,a in enumerate(A):
  te=0
  oo=0
  for j,b in enumerate(A):
    if j==i:continue
    if b>a:
      oo+=1
      if j<i:
        te+=1
  tento.append(te)
  ookii.append(oo)
Tent = sum(tento)%mod
Lar = sum(ookii)%mod
L = Lar *K*(K-1)//2
R = Tent*K

print((L+R)%mod)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = [int(a) for a in input().split()]
mod = 7 + 10 ** 9
Atype = set(A)

mult = K * (K - 1)// 2
mult %= mod

count = dict()
for a in A:
    if a in count: count[a] += 1
    else: count[a] = 1

inside = 0
used = dict()
used[A[N-1]] = 1
for i in reversed(range(N-1)):
    for k in used:
        if A[i] > k: inside += used[k]
    if A[i] in used: used[A[i]] += 1
    else: used[A[i]] = 1
inside *= K
inside %= mod

after = 0
for a in A:
    for k in count:
        if a > k: after += count[k]
after *= mult
after %= mod

print((inside + after) % mod)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
A = list(map(int,input().split()))
p = []
B = sorted(A)
for i in range(n):
    cnt = 0
    for j in range(i+1, n):
        if A[i] > A[j]:
            cnt += 1
    p.append(cnt)

ans = 0
mod = 10**9 + 7
for i,a in enumerate(A):
    ans = (ans + (k-1) * k * B.index(a) // 2 + p[i]*k) % mod
print(ans)

Submission status: Accepted

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

ans = 0

MOD = 10**9+7
for i, a in enumerate(A):
    bef = 0
    aft = 0
    for j, b in enumerate(A):
        if a > b:
            if i > j:
                aft += 1
            else:
                bef += 1
    ans += bef*(K*(K+1))//2
    ans += aft*(K*(K-1))//2
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
import sys, math, itertools, bisect, copy, re

from collections import Counter, deque, defaultdict
from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
from functools import reduce
from math import ceil, floor, log10, log2, factorial
from pprint import pprint

# 10倍速いらしい
input = sys.stdin.readline

INF = float('inf')
MOD = 10 ** 9 + 7
EPS = 10 ** -7
sys.setrecursionlimit(1000000)

# N = int(input())
# N,M = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]
# DP = [[0] * 100 for _ in range(100)]
# DP = defaultdict(lambda: float('inf'))

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

T1 = [0] * N
T2 = [0] * N

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

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

ans = sum(T1) * K
ans %= MOD
ans += sum(T2) * K * (K - 1) // 2
ans %= MOD

print(ans)
# print(T1)
# print(T2)

Submission status: Accepted

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

Submission status: Accepted

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

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

# print(cnt_a)
print(ans%MOD)

Submission status: Accepted

Solution code:

class BIT:
            
    def __init__(self, L):
        self.N = len(L)
        self.bit = [0]*self.N
        for i,l in enumerate(L):
            self.add(i,l)

    def add(self, a, w):
        x = a + 1
        for i in range(1000):
            self.bit[x-1] += w
            x += x & -x
            if x > self.N:
                break

    def sum(self, a):
        x = a+1
        ret = 0
        for i in range(1000):
            ret += self.bit[x-1]
            x -= x & -x
            if x <= 0:
                break        
        return ret



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

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

S_tag = [0]*2001

for i in range(N):
        S_tag[A[i]]+=1

bit=BIT([0]*2001)

bit.add(A[0],1)
count = 0

for i in range(1,N):
        count+=bit.sum(2000)-bit.sum(A[i])
        bit.add(A[i],1)

mod = 10**9 + 7

ans = 0
for i in range(1,2001):
        ans += bit.sum(i-1)*S_tag[i]

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

ans += K*count
ans %= mod

print(ans)

Submission status: Accepted

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

from collections import defaultdict
from itertools import combinations

d = defaultdict(int)

k = 0
K %= mod

for i,j in combinations(range(N),2):
    if A[i] > A[j]:
        k+=1
        d[A[j]]+=1
    elif A[j] > A[i]:
        d[A[i]]+=1

ans = (k * K) % mod

for k in d.keys():
    ans += d[k]*(K*(K-1)//2) % mod
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
inpl = lambda: list(map(int,input().split()))
MOD = 10**9 + 7
N, K = inpl()
A = inpl()
correct = 0
inverse = 0
for i in range(N):
    for j in range(i+1,N):
        if A[i] < A[j]:
            correct += 1
        elif A[i] > A[j]:
            inverse += 1

W1 = K*(K-1)//2 % MOD
W2 = K*(K+1)//2 % MOD
ans = (correct*W1+inverse*W2) % MOD
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
mod = 1000000007


def inverse(a):
    return pow(a, mod - 2, mod)


def usearch(x, a):
    lft = 0
    rgt = len(a) + 1
    while rgt - lft > 1:
        mid = (rgt + lft) // 2
        if a[mid] <= x:
            lft = mid
        else:
            rgt = mid
    return lft


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

def main():
    n, k=map(int, input().split())
    a = list(map(int, input().split()))
    ans = bubble_sort(a) * k % mod
    div2 = inverse(2)
    # a.sort()
    lft = 0
    rgt = 0
    while lft < n:
        while rgt < n and a[lft] == a[rgt]:
            rgt += 1
        ans = (ans + (rgt - lft) * (n - rgt) % mod * k % mod * (k-1) * div2 % mod) % mod
        lft =rgt

    print(ans)
main()

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


B0=[]

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

    B0.append(ANS)

count=[0]*(max(A)+1)

for a in A:
    count[a]+=1

from itertools import accumulate
S=list(accumulate(count))

ANS=0

for i in range(N):
    t=S[A[i]-1]
    ANS=(ANS+B0[i]*K+t*K*(K-1)//2)%mod

print(ANS)

Submission status: Accepted

Solution code:
N, K = map(int,input().split())
A = list(map(int,input().split()))
tentou = [0 for i in range(N)] #tentou[i]はA[i]>A[j]なるjの数(i < j)
compl = [0 for i in range(N)] #compl[i]はA[i] > A[j]なるjの数(i != j つまりi < jとは限らない)
for i in range(N):
    for j in range(N):
        if A[i] > A[j]:
            compl[i] += 1
            if i < j:
                tentou[i] += 1
print(str((sum(tentou)*K + sum(compl)*K*(K-1)//2) % (10**9+7)))

Submission status: Accepted

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

KR=((K*(1+K))//2)%MOD
KL=(((K-1)*K)//2)%MOD

ans=0
for i in range(N):
    ans = (ans + (KR*R[i])%MOD)%MOD
    ans = (ans + (KL*L[i])%MOD)%MOD
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools


def main():
    nun, k = map(int, input().split())
    data = list(map(int, input().split()))

    aaa = [0 for i in range(nun)]
    for i in range(nun):
        for j in range(nun):
            if i == j:
                continue
            if data[i] > data[j]:
                aaa[i] += 1

    mod = 10 ** 9 + 7
    ans = 0
    # print(aaa)
    for i in range(nun):
        shokou = 0
        for j in range(i + 1, nun):
            if data[i] > data[j]:
                # ans += 1
                shokou += 1
        # print(shokou)
        ans += (shokou + shokou + (k - 1) * aaa[i]) * k // 2
        # print(ans)
        ans %= mod

    print(ans)





if __name__ == '__main__':
    main()

Submission status: Accepted

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

base = 0
mod = 10**9 + 7
mul = (k*(k+1))//2
mul2 = (k*(k-1))//2

for i in range(n):
    for j in range(i):
        if arr[i] < arr[j]:
            base += 1
    # print(base)

pot = 0
for i in range(n):
    for j in range(i+1,n):
        if arr[i] < arr[j]:
            pot += 1


# print(pot)
# print(base)

print((base*mul+pot*mul2)%mod)

Submission status: Accepted

Solution code:
def main():
    N, K = map(int, input().split())
    A = [int(a) for a in input().split()]
    div = pow(10, 9) + 7

    pairs1 = []
    pairs2 = []
    for i in range(N):
        ref = A[i]
        count1 = 0
        count2 = 0
        for j in range(N):
            if j < i and A[j] < ref:
                count2 += 1
            elif j > i and A[j] < ref:
                count1 += 1
        count2 += count1
        pairs1.append(count1)
        pairs2.append(count2)

    # print(A)
    # print(pairs1)
    # print(pairs2)
    ans = 0
    for i in range(N):
        ans += pairs1[i]*K % div
        ans += pairs2[i]*K*(K-1)//2 % div
    return ans % div

if __name__ == '__main__':

    print(main())

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
aa = list(map(int, input().split()))
mod = int(10**9+7)
total = 0
for i in range(n):
    for j in range(i+1, n):
        a = aa[i]
        b = aa[j]

        if a < b:
            total += k * (k-1) // 2
            total %= mod
        if a > b:
            total += k * (k+1) // 2
            total %= mod

print(total)

Submission status: Accepted

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

ans = 0

for i, a in enumerate(A):
    big_mae = 0
    big_ushiro = 0
    for j in range(i):
        if A[j] < a:
            big_mae += 1
    for j in range(i + 1, N):
        if A[j] < a:
            big_ushiro += 1
    
    # print((big_mae, big_ushiro, big_ushiro*K + (big_mae + big_ushiro)*K*(K-1)//2))

    ans += big_ushiro*K + (big_mae + big_ushiro)*K*(K-1)//2
    ans %= 1000000007

print(ans)

Submission status: Accepted

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

mod = int(1E9+7)

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

D = []
for i in range(N):
    a = A[i]
    q = 0
    for j in range(N):
        if A[j] < a:
            q += 1
    D.append(q)

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

Submission status: Accepted

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

k = k%1000000007

tent  = [0 for i in range(n)]
ind = [0 for i in range(n)]

for i in range(n):
        al = 0
        bl = 0
        for j in range(n):
                if i < j and a[i] > a[j]:
                        al += 1
                if a[i] > a[j]:
                        bl += 1

        tent[i] = al
        ind[i] = bl

#print(tent)
#print(ind)

ans = 0

for i in range(n):
        ans += tent[i]*k
        ans +=(k*(k-1)//2)*ind[i]
        #print("今の"+str(ans))
        ans = ans%1000000007
print(ans%1000000007)

Submission status: Accepted

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

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

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

if K == 1:
    print(c)
elif K == 2:
    print(c * 2 + cp)
else:
    print((c * K + (K * (K - 1) // 2) * cp) % (10 ** 9 + 7))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
A=[int(i) for i in input().split()]
import bisect
mod=10**9+7
AA=[]
ans1=0
for i in range(n):
  ans1+=i-bisect.bisect_right(AA,A[i])
  AA.append(A[i])
  AA.sort()
ans2=0
for i in range(n-1):
  ans2+=n-bisect.bisect_right(AA,AA[i])

ans=(ans1*k)%mod
ans=(ans+ans2*k*(k-1)//2)%mod
print(ans)

Submission status: Accepted

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

X = [0]*N
Y = [0]*N

for i in range(N):
    for j in range(i+1, N):
        if A[i] > A[j]:
            X[i] += 1
        elif A[i] < A[j]:
            Y[j] += 1

mod = 10**9+7
ans = 0
for i in range(N):
    ans += K*(K+1)*X[i]//2%mod
    ans += (K-1)*K*Y[i]//2%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()))
cnt = [0 for i in range(2001)]
for a in A:
	cnt[a] += 1
total = [0]
for i in range(2000):
	total.append(total[i] + cnt[i+1])

base = 0
loop = 0
keisu = K*(K-1)//2 % MOD
for i in range(N):
	a = A[i]
	for j in range(i+1, N):
		if a > A[j]:
			base += 1
	loop = (loop + total[a-1] * keisu) % MOD

print((base*K + loop) % MOD)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n, k = li()
a = list(li())
MOD = 10**9 + 7

ans = 0
for i, ai in enumerate(a):
    for j, aj in enumerate(a):
        if ai > aj:
            if j < i:
                ans += ((k-1)*k // 2)
            else:
                ans += ((k+1)*k // 2)

            ans %= MOD


print(ans % MOD)

Submission status: Accepted

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

mod = 10**9 + 7
nums = [[0, 0] for _ in range(n)]

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

kbig = ((k+1) * k) // 2
ksmall = (k * (k-1)) // 2

result = 0
for i in range(n):
    result = (result + nums[i][0] * ksmall + nums[i][1] * kbig) % mod

print(result)

Submission status: Accepted

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

R = {}
L = []
for i in A:
  if i not in R:
    R[i] = 1
    L.append(i)
  else:
    R[i] += 1

L.sort(reverse = True)

k = 0
t = R[L[0]]
for i in range(1, len(L)):
  k = (k + t * R[L[i]]) % MOD
  t += R[L[i]]

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

k = 0
for i in range(N):
  for j in range(i):
    if A[i] < A[j]:
      k += 1
ans = (ans + k * K) % MOD

print(ans)

Submission status: Accepted

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

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

A_sorted = sorted(A)
smaller = [0] * N
for i in range(1, N):
    if A_sorted[i - 1] < A_sorted[i]:
        smaller[i] = i
    else:
        smaller[i] = smaller[i-1]
sum_smaller = sum(smaller)

ans = (((tentou * K) % mod) + ((sum_smaller * (((K * (K - 1)) // 2) % mod)) % mod)) % mod
print(ans)

Submission status: Accepted

Solution code:

import sys
def input():
	return sys.stdin.readline().strip()

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

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

total = 0
for i in range(N):
	total += K * bigger_after[i]
	total += K * (K - 1) * bigger[i] //2
	total = total % 1000000007
print(total)

Submission status: Accepted

Solution code:
I=lambda:input()
L=lambda:list(map(int,I().split()))
n,k=L()
a=L()
m=10**9+7
kk=(k*(k+1)//2)%m
k=(k*(k-1)//2)%m
from bisect import bisect_left
x=0
for i in range(n):
  if i!=0:
    l=a[:i]
    l.sort()
    b=bisect_left(l,a[i])
    x+=(b*k)%m
  if i!=n-1:
    l=a[i+1:]
    l.sort()
    b=bisect_left(l,a[i])
    x+=(b*kk)%m
  x%=m
print(x)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,k=map(int,input().split())
INF=10**9+7
a_list=list(map(int,input().split()))
count=0
ans=0
for i in range(n):
    for j in range(i+1,n):
        if a_list[i]>a_list[j]:
            count+=1
ans=(count*k)%INF
m=max(a_list)
D=[0]*m
for i in a_list:
    D[i-1]+=1
count=0
Sum=D[m-1]
for i in range(m-2,-1,-1):
    count=(count+Sum*D[i])%INF
    Sum=(Sum+D[i])%INF
count=(count*k*(k-1)//2)%INF
ans=(ans+count)%INF
print(ans)

Submission status: Accepted

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


def tentousu(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


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


print((tentousu(a_) * k + chiisai(a_) * k * (k - 1) // 2) % (10 ** 9 + 7))

Submission status: Accepted

Solution code:
import sys
import heapq
from operator import itemgetter
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7

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

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

    ans = (((front * K * (K + 1) // 2) % MOD) + ((back * (K - 1) * K // 2) % MOD)) % MOD
    print(ans)


sol()

Submission status: Accepted

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

d1 = defaultdict(lambda:0)
d2 = defaultdict(lambda:0)

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

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

print(ans)

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
n,k=map(int,input().split())
a=list(map(int,input().split()))
b=[0]*n
c=[0]*n
mod=10**9+7
for i in range(n):
    for j in range(i+1,n):
        if a[i]>a[j]:
            b[i]+=1
    for j in range(i):
        if a[i]>a[j]:
            c[i]+=1
ans=sum(b)
anst=sum(c)
# print(b)
print((ans*k*(k+1)//2+anst*(k-1)*k//2)%mod)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
Q = 10**9 + 7

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

    for i in range(N):
        a = A[i]
        al = 0
        after = 0
        for i in range(i):
            if A[i] < a:
                al += 1
        for i in range(i+1, N):
            if A[i] < a:
                al += 1
                after += 1
        ans += K*(K-1)//2*al%Q + after*K%Q
        ans %= Q
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

y=[0 for _ in range(n)]
for i in range(1,n):
	for j in range(i):
		if a[j]<a[i]:
			y[i]+=1


print((sum(x)*k*(k+1)//2+sum(y)*k*(k-1)//2)%(10**9+7))

Submission status: Accepted

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

count_bf = [0] * n
count_af = [0] * n

for i in range(n):
    for j in range(n):
        if j < i:
            if lst[i] > lst[j]:
                count_bf[i] += 1
        if j > i:
            if lst[i] > lst[j]:
                count_af[i] += 1
                
res = 0
for i in count_af:
    res += ((k * (k+1) // 2) * i) % (10**9 + 7)
for i in count_bf:
    res += ((k * (k-1) // 2) * i) % (10**9 + 7)
print(res % (10**9 + 7))

Submission status: Accepted

Solution code:
#B問題
N,K = map(int,input().split())
A = list(map(int,input().split()))
count = 0
for i,a in enumerate(A):
    for j,b in enumerate(A):
        if a > b:
            if i < j:
                count+=(K*(K+1))//2
            else:
                count+=(K*(K-1))//2
                
print(count%1000000007)

Submission status: Accepted

Solution code:
import collections

MOD = 10**9+7


def solve(n, k, a):
    total = 0

    cnt = [0] * 2001
    for v in a:
        cnt[v] += 1
    for i in range(n - 1):
        for j in range(i + 1, n):
            if a[i] > a[j]:
                total += 1
    total *= k
    l_sum = [0] * 2001
    r_sum = [0] * 2001
    for i in range(1, 2001):
        l_sum[i] = l_sum[i-1] + cnt[i-1]
    for i in range(1999, 0, -1):
        r_sum[i] = r_sum[i + 1] + cnt[i + 1]
    z = k*(k-1)//2
    for i in range(1, 2001):
        total += z*(l_sum[i]) * cnt[i]

    return total % MOD


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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def makelist(n, m):
    return [[0 for _ in range(m)] for _ in range(n)]


MOD = int(1e9) + 7

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

init = 0
total = 0
for i in range(N):
    for j in range(i+1, N):
        if A[i] > A[j]:
            init += 1
        if A[i] != A[j]:
            total += 1
            
ans = init * K
ans %= MOD

hoge = (K * (K - 1)) // 2
hoge %= MOD
ans += total * hoge
ans %= MOD

print(ans)