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: Time Limit Exceeded

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 = map(int, input().split())
ppp = list(map(int, input().split()))
pppa = []
for i in range(k):
    pppa += ppp
ppp = pppa
k = 1
bit = Bit(3000)
ans_ = 0

for i, p in enumerate(ppp):
    bit.add(p, 1)
    ans_ += i + 1 - bit.sum_(p)

mod = 10 ** 9 + 7
ans = (ans_ * k) % mod
ppp = sorted(ppp)

ppp_ = set(ppp)
dic1 = {}
dic2 = {}
for i in ppp_:
    dic1[i] = 0
    dic2[i] = 0

for i in ppp:
    dic1[i] += 1
    dic2[i] += 1

k_ = ((k-1) * k / 2) % mod
k_ = int(k_)
for i in ppp_:
    dic1[i] = 0
    ans += k_ * dic2[i] * sum(dic1.values())
    ans %= mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

if __name__ == '__main__':
    N,K = map(int, input().split())
    A = list(input().split())
    #B = A[:]

    #for i in range(K-1):
        #A.extend(B)

    count = 0
    for i,a in enumerate(A):
        for target in A[i+1:]:
            if int(a) > int(target):
                count += 1

    count_ = 0
    for i,a in enumerate(A):
        for target in A:
            if int(a) > int(target):
                count_ += 1

    C = 0
    for i in range(K):
        C += count + count_*(K-i-1)

    print(C%1000000007)

Submission status: Time Limit Exceeded

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

cnt_all = 0
cnt_right = 0
cnt_minA_all = []
cnt_minA_right = []


for i in range(N):
    for j in range(N):
        if A[i] > A[j]:
            cnt_all += 1
            if i < j:
                cnt_right += 1
    else:
        cnt_minA_all.append(cnt_all)
        cnt_all = 0
        cnt_minA_right.append(cnt_right)
        cnt_right = 0

ans = 0
for i in reversed(range(1, K+1)):
    ans += (sum(cnt_minA_all) * (K-i) % (10**9+7) + sum(cnt_minA_right)) % (10**9+7)

print(ans)

Submission status: Time Limit Exceeded

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

b = []

for i in range(nk[1]):
    b += a

def bubble_sort(A):
    cnt = 0
    for j in range(len(A)):
        for l in range(len(A)-1, j, -1):
            if A[l] < A[l-1]:
                A[l], A[l-1] = A[l-1], A[l]

                cnt += 1
    return int(cnt)

ans = bubble_sort(b)
ans = ans % 1000000007
print(ans)

Submission status: Time Limit Exceeded

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

for _ in range(K-1):
    A.extend(A)
    


print(bubble_sort(A))

Submission status: Time Limit Exceeded

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

N = A[0]
K = A[1]
count = 0

list = []

for i in range(K):
  list.extend(B)

for j in range(N*K):
  for k in range(j,N*K):
    if list[j] > list[k]:
      count+=1
    
  
count = count%(10**9 + 7)
print(count)

Submission status: Time Limit Exceeded

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

b = []

for i in range(nk[1]):
    b += a

def bubble_sort(A):
    cnt = 0
    for j in range(len(A)):
        for l in range(len(A)-1, j, -1):
            if A[l] < A[l-1]:
                A[l], A[l-1] = A[l-1], A[l]

                cnt += 1
    return int(cnt)

ans = bubble_sort(b) % 1000000007
print(ans)

Submission status: Time Limit Exceeded

Solution code:

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

A=list(map(int,input().split()))
B=[]
for i in range(2):
    for j in range(N):
        B.append(A[j])
b=len(B)
count=0
for i in range(b):
    for j in range(b-i):
        if B[i]>B[i+j]:
            count+=1
#print(count)

a=len(A)
counter=0
for i in range(a):
    for j in range(a-i):
        if B[i]>B[i+j]:
            counter+=1
#print(count)
#print(counter)
#print(count-2*counter)

ans=(counter*K+((count-2*counter)*(K-1)*K)//2)%(1000000007)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.reverse()
ans = 0
for i in range(n):
    tmp = 0
    Tmp = 0
    tmplist = [a[i]]
    index = i
    for _ in range(n-1):
        index += 1
        index %= n
        tmplist.append(a[index])
    for j in range(1,n):
        if tmplist[j] > a[i]:
            tmp += 1
    for j in range(i,n):
        if a[j] > a[i]:
            Tmp += 1
    ans += Tmp*k + tmp * (k-1)*k//2
    #print(tmplist,Tmp,tmp)
ans = ans % (10**9 + 7 )
print(ans)

Submission status: Time Limit Exceeded

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


M = 10 ** 9 + 7


def naive_inv_num(xs):
    n = len(xs)
    res = 0
    for i in range(n - 1):
        for j in range(i + 1, n):
            if xs[i] > xs[j]:
                res += 1
    return res


def rep_inv_num(k, xs, mod=M):
    c1 = naive_inv_num(xs)
    c2 = naive_inv_num(xs * 2)
    c3 = naive_inv_num(xs * 3)
    d1 = c2 - c1
    f = c3 - 2 * c2 + c1
    res = c1
    res += (k - 1) * d1
    res %= mod
    res += f * (k - 1) * k // 2
    res %= mod
    res -= f * (k - 1)
    res %= mod
    return res


def main():
    _, k = (int(z) for z in input().split())
    xs = [int(x) for x in input().split()]
    res = rep_inv_num(k, xs)
    print(res)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N,K = [int(i) for i in input().split(" ")]
B_list = A_list = [int(i) for i in input().split(" ")]
s = 0
for k in range(K-1):
    B_list += A_list
for i in range(len(B_list)):
    a0 = B_list[i]
    for a in B_list[i+1:]:
        if a0 > a:
            s+=1
print(s)

Submission status: Time Limit Exceeded

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

s = 0
for i in range(k):
    s += i

res = 0
for i in range(n):
    for j in range(n):
        if j == i:
            continue
        if a_list[i] > a_list[j]:
            if i < j:
                res += s + k
            else:
                res += s

res %= mod
print(int(res))

Submission status: Accepted

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

ans=0
for i in range(n):
    cnt1=0
    cntall=0
    for j in range(n):
        if a[i]>a[j]:
            cntall+=1
            if i<j:
                cnt1+=1

    ans =(ans + cnt1*k + cntall*k*(k-1)//2) % MOD

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def input_int():
    return(int(input()))

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

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

def run():

    n, k = input_int_map()

    nums = input_int_list()


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

    in_list_count_sum = in_list_count * k

    other_list_count = 0

    for num in nums:
        for num2 in nums:
            if num > num2:
                other_list_count += 1


    other_list_count_sum = other_list_count * k * (k - 1) // 2

    result = (in_list_count_sum + other_list_count_sum) % (10 ** 9 + 7)
    print(result)

run()

# RRLRL
# 0 2 1 1 1

# 1 1 2 2 0

Submission status: Accepted

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

#import
#import math
#import numpy as np
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

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

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

print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10**9+7
L = [0 for _ in range(N)]
R = [0 for _ in range(N)]

for i in range(N):
  num = A[i]
  for j in range(i):
    if num > A[j]:
      L[i] += 1
  for k in range(i, N):
    if num > A[k]:
      R[i] += 1

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

Submission status: Accepted

Solution code:

MOD = 10 ** 9 + 7

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

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

totalMin = [0] * N
afterMin = [0] * N

def addAll(n):
  return (n * (n + 1) // 2) % MOD


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

total = 0
for i in range(N):
  total = (total + afterMin[i] * K) % MOD
  total = (total + totalMin[i] * addAll(K - 1)) % MOD

print(total)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
p = 0 #tumble count in a: finally *k
q = 0 #tumble count between a: finally *kC2
for i in range(n-1):
  for j in range(i+1,n):
    if a[i] > a[j]:
      p += 1
for i in range(n):
  for j in range(n):
    if a[i] > a[j]:
      q += 1
p *= k
q *= k*(k-1)//2
print((p+q)%(10**9+7))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
a_ls = list(map(int, input().split()))
i_great = [0] * N
i_greatleft = [0] * N 

for i in range(N):
    for j in range(N):
        if a_ls[i] > a_ls[j]:
            i_great[i] += 1
            if i < j:
                i_greatleft[i] += 1
#print(i_great)
#print(i_greatleft)

ans = 0
mod = 10**9+7
K %= mod
times = ((K*(K-1))//2)%mod

for i in range(N):
    #print('------')
    #print(i)
    ans += (K*i_greatleft[i])%mod
    #print(K*i_greatleft[i])
    ans += (times*i_great[i])%mod
    #print(times*i_great[i])
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
import math


def compute_reverse(n: list):
    result = 0
    for i in range(len(n)):
        for j in range(i+1, len(n)):
            if n[i] > n[j]:
                result += 1
    return result


N, K = map(int, input().split())
A = list(map(int, input().split()))
case1 = compute_reverse(A) *  ((K * (K + 1)) // 2)
case3 = compute_reverse(A[::-1]) * ((K * (K - 1)) // 2)
ans = (case1 + case3) % MOD
print(ans)

Submission status: Accepted

Solution code:
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():
    n, k = LI()
    a = LI()
    ans = 0
    num = 10**9 + 7

    for i in range(n):
        x = a[i]
        before = 0
        after = 0

        for j in range(i):
            if a[j] < x:
                before += 1

        for j in range(i+1, n):
            if a[j] < x:
                after += 1


        ans += (after*(k+1)+before*(k-1))*k // 2
        ans %= num

    ans = print(ans)
main()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
#a内部ての転倒数
c_1=0
for i in range(n):
    for j in range(i+1,n):
        if a[i]>a[j]:
            c_1+=1
ans1=c_1*k
#print(ans1)
#aとaの間の転倒数
c_2=0
for i in range(n):
    for j in range(n):
        if a[i]>a[j]:
            c_2+=1
ans2=c_2*(k*(k-1)//2)
print((ans1+ans2)%(7+10**9))

Submission status: Accepted

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

mod = 10**9+7
ans = 0
for i in range(n):
    x,y = 0,0
    for j in range(i):
        if a_L[i] > a_L[j]:
            x += 1
    for j in range(n):
        if a_L[i] > a_L[j]:
            y+=1
    ans += y*((1+k)*k//2) - x*k
    ans = ans%mod

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
A = list(map(int, input().split()))
ans1 = 0
ans2 = 0
mod = 10 ** 9 + 7
for i, a in enumerate(A):
    for j, b in enumerate(A):
        if a > b:
            if i < j:
                ans1 += 1
                ans2 += 1
            else:
                ans2 += 1

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

Submission status: Accepted

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

k1 = ((k-1)*k//2)
k2= ((k)*(k+1)//2)

normal = 0
reverse = 0
for i in range(n):
    normal += sum(1 for a in A[i+1:] if a > A[i])
    reverse += sum(1 for a in A[i+1:] if a < A[i])

print((normal * k1 + reverse * k2)%(10**9 + 7))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
from sys import exit
from collections import deque
from bisect import bisect_left, bisect_right, insort_left, insort_right #func(リスト,値)
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import sin, cos, tan, asin, acos, atan, degrees, radians

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def perm(n,mod=None):
    ans = 1
    for i in range(1,n+1):
        ans *= i
        if mod!=None:
            ans %= mod
    return ans
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x,d=1):
        self.setdefault(x,0)
        self[x] += d
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]

class SegmentTree():
    
    # 目的関数！！
    def func(self,x,y):
        return x+y
    
    # インデックスは0-start
    # 初期化（配列と初期値）
    def __init__(self, array, initial_value=0):
        
        self.n = len(array)
        self.init_val = initial_value
        self.num = 2**(self.n-1).bit_length()
        self.seg = [self.init_val]*2*self.num
        
        for i in range(self.n):
            self.seg[i+self.num-1] = array[i]
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.func(self.seg[2*i+1],self.seg[2*i+2]) 
    
    # k番目の要素をxに変更
    def update(self,k,x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.func(self.seg[2*k+1],self.seg[2*k+2])
    
    # k番目の要素にxを追加
    def add(self,k,x):
        k_tmp = k+self.num-1
        x_tmp = self.seg[k_tmp]+x
        self.update(k,x_tmp)
    
    # [p,q]に対するクエリを処理
    def query(self,p,q):
        q += 1
        if q<=p:
            return self.init_val
        p += self.num-1
        q += self.num-2
        res = self.init_val
        while q-p>1:
            if p&1 == 0:
                res = self.func(res,self.seg[p])
            if q&1 == 1:
                res = self.func(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.func(res,self.seg[p])
        else:
            res = self.func(self.func(res,self.seg[p]),self.seg[q])
        return res
    
    # もとの配列を出力
    def result(self):
        return self.seg[self.num-1:self.n+self.num-1]
N,K = mint()
A = lint()
T = [0]*2001
for a in A:
    T[a] += 1
t = SegmentTree(T)
s = SegmentTree([0]*2001)
ans = 0
for a in A:
    t.add(a,-1)
    ans += t.query(0,a-1)*K*(K+1)//2
    ans %= MOD
    ans += s.query(0,a-1)*K*(K-1)//2
    ans %= MOD
    s.add(a,1)
print(ans)

Submission status: Accepted

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

for i in range(n):
    cnt_left = 0
    cnt_right = 0
    for j in range(n):
        if a[i] > a[j]:
            if i < j:
                cnt_right += 1
            elif i > j:
                cnt_left += 1
    right += cnt_right % (10 ** 9 + 7)
    left += cnt_left % (10 ** 9 + 7)
    cnt_right = 0
    cnt_left = 0

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import re
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
import functools
def v(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
cnt = 0
ans = 0
inf = float("inf")
al = "abcdefghijklmnopqrstuvwxyz"
AL = al.upper()

n,k = I()
a = l()
p = list(set(a))

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

print(ans%mod)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
m=10**9+7
s=sum
print(s((((s(a[i]>j for j in a[i:])*(k*(k+1)//2)%m)+(s(a[i]>j for j in a[:i+1])*(k*(k-1)//2)%m))%m) for i in range(n))%m)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

mod = 10**9 + 7
x = (k*(k+1)//2)%mod
y = (k*(k-1)//2)%mod

r = 0
for i in range(n):
    right = sum(a[i] > j for j in a[i:])
    left = sum(a[i] > j for j in a[:i+1])
    r = (r+((right*x) + (left*y))%mod)%mod
print(r)

Submission status: Accepted

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

m = []
for i in range(N-1):
  cnt = sum([1 for j in range(i,N) if S[i] > S[j]])
  m.append(cnt)

f = sum(m) # within one copies

m = []
for i in range(N):
  cnt = sum([1 for j in range(0,N) if S[i] > S[j]])
  m.append(cnt)

g = sum(m) # between two copies
  
#print(m)
import decimal as d
f = d.Decimal(f)
g = d.Decimal(g)
ans = (f*K + g*K*(K-1)/2) % divisor
print(ans)

Submission status: Accepted

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

    B0 = ans = 0

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

    ans += (B0 * K)

    for i in range(len(A)):
        count = 0
        for j in range(len(A)):
            if A[i] > A[j]:
                count += 1
        
        ans += (count * (K - 1) * K // 2)

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

if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

def nC2(n):
  return n*(n-1)//2

inv=0
for i in range(N-1):
  for j in range(i+1,N):
    if A[j]<A[i]: inv += 1
      
inv2=0
B = sorted(A,reverse=True)
for i in range(N-1):
  for j in range(i+1,N):
    if B[j]<B[i]: inv2 += 1

print((inv*K+inv2*nC2(K))%mod)

Submission status: Accepted

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

mod = 10**9 + 7

ans = 0
right = 0
zenbu = 0

for i in range(n-1):
    for j in range(i,n):
        if lis[i] > lis[j]:
            right += 1
for i in range(n):
    for j in range(n):
        if lis[i] > lis[j]:
            zenbu += 1
    
t = (k-1)*k
ans += right*k
ans +=(t//2)*zenbu
ans %= mod

print(ans)

Submission status: Accepted

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

left=[0]*N
right=[0]*N
for i in range(N):
    if 0<i:
        for l in range(0,i):
            if A[l]<A[i]:
                left[i]+=1
    if i<N-1:
        for r in range(i+1,N):
            if A[r]<A[i]:
                right[i]+=1
        
ans=0
mod=10**9+7
for i in range(N):
    ans=(ans+(K*right[i]%mod+K*(K-1)//2*(left[i]+right[i])%mod)%mod)%mod

print(ans)

Submission status: Accepted

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

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

print(int(sum(a2)*(k*(k-1)//2) + sum(a)*k) % (10**9+7))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect
import copy
import math
sys.setrecursionlimit(10**6)

# lis_of_lis = [[] for _ in range(N)]


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


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


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


def C(line): return [sys.stdin.readline() for _ in range(line)]


MOD = pow(10, 9)+7
N, K = zz()
A = zz()

# Aの中にある転倒数を求める
# Aの中にある転倒数 * K 個転倒数がある
# Aの各要素について、転倒数を求めておけば、それをK倍すればよい

num_tentou = [0] * N
num_tentou_within = [0] * N

for i in range(N):
    base = A[i]
    for j in range(N):
        if (base > A[j]):
            num_tentou[i] += 1
    for j in range(i + 1, N):
        if (base > A[j]):
            num_tentou_within[i] += 1
num = sum(num_tentou)
within_num = sum(num_tentou_within)
ans = -K*(K-1)*num//2 + K*(K-1)*num + within_num*K
print(ans % MOD)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
ls = list(map(int,input().split()))
di = [0]*2001
sm = 0
ans = 0
cnt = 0
mod = 10**9+7
f = sorted(list(set(ls)))
for i in f:
    di[i] = sm
    sm += ls.count(i)
for j in range(n):
    for l in range(j+1,n):
        if ls[j] > ls[l]:
            cnt += 1
    ans += (cnt*k+di[ls[j]]*k*(k-1)//2)
    if ans >= 10**9+7:
        ans %= mod
    cnt = 0
print(ans)

Submission status: Accepted

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

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

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

x = sum(c)
y = x + sum(d)
ans = (K * x + (K * (K - 1) // 2) * y) % (10**9 + 7)

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
ca,cb=0,0
mod=10**9+7
for i,x in enumerate(a):
  for j,y in enumerate(a):
    if x>y:
      if i<j:ca+=1
      else:cb+=1
print((ca*k*(k+1)//2%mod+cb*k*(k-1)//2%mod)%mod)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
A=list(map(int,input().split()))
mod=10**9+7
cnt=0
for i in range(n-1):
    for j in range(i+1,n):
        if A[i]>A[j]:
            cnt+=1
Aij=A+A
l=len(Aij)
cntij=0
for i in range(l-1):
    for j in range(i+1,l):
        if Aij[i]>Aij[j]:
            cntij+=1
cntij-=2*cnt
Tii=cnt*k
Tij=cntij*(k*(k-1)//2)
print((Tii+Tij)%mod)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
before = [0] * N
after = [0] * N
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        if i < j:
            if A[i] > A[j]:
                after[i] += 1
        elif i > j:
            if A[i] > A[j]:
                before[i] += 1
sum_after = (sum(after) * (K * (K + 1)) // 2) % ((10 ** 9) + 7)
K -= 1
sum_before = (sum(before) * (K * (K + 1)) // 2) % ((10 ** 9) + 7)
ans = sum_after + sum_before
ans %= ((10 ** 9) + 7)
#print(after, before)
#print(sum_after, sum_before)
print(ans)

Submission status: Accepted

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

cnt = 0
for i in range(n):
    cnt1 = 0
    cnt2 = 0

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

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

    cnt += cnt1*k + (k-1)*k//2*cnt2

print(cnt % 1000000007)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
mod=pow(10,9)+7
answer=0
for n in range(N-1):
    number=A[n]
    for n_ in range(n,N-1):
        if A[n_+1]<number:
            answer+=1
sort_A=sorted(A,reverse=True)
answer2=0
for n in range(N-1):
    number=sort_A[n]
    for n_ in range(n,N-1):
        if sort_A[n_+1]<number:
            answer2+=1
print((answer*K+answer2*(K-1)*K//2)%mod)

Submission status: Accepted

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

class BIT:
    def __init__(self, n):
        self.size = n
        self.tree = [0]*(n+1)
 
    def sum(self, i):
        # [0, i) の要素の総和を返す
        s = 0
        while i>0:
            s += self.tree[i]
            i -= i & -i
        return s
    # 0 index を 1 index に変更  転倒数を求めるなら1を足していく
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

bit = BIT(2001)
count = [0]*(2001)
t = []
for i in range(n):
    x = a[i]
    count[x] += 1
    t.append(i-bit.sum(x))
    bit.add(x,1)

for i in range(1,2001):
    count[i] += count[i-1]

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