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()))

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

cmb_cnt = 0
for a in A:
   cmb_cnt += len([x for x in A if x < a]) 

kC2 = (K*(K-1))//2
ans = (cnt*K)+(cmb_cnt*kC2)
print(ans%(10**9+7))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)


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


def resolve():

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

    def count_bigger(seq):
        cnt = 0
        for i in seq:
            for j in seq:
                if i < j:
                    cnt += 1
        return cnt

    # Python3 program to count inversions using
    # Binary Indexed Tree

    # Returns sum of arr[0..index]. This function
    # assumes that the array is preprocessed and
    # partial sums of array elements are stored
    # in BITree[].
    def getSum(BITree, index):
        sum = 0  # Initialize result

        # Traverse ancestors of BITree[index]
        while (index > 0):

            # Add current element of BITree to sum
            sum += BITree[index]

            # Move index to parent node in getSum View
            index -= index & (-index)

        return sum

    # Updates a node in Binary Index Tree (BITree)
    # at given index in BITree. The given value
    # 'val' is added to BITree[i] and all of its
    # ancestors in tree.
    def updateBIT(BITree, n, index, val):

        # Traverse all ancestors and add 'val'
        while (index <= n):

            # Add 'val' to current node of BI Tree
            BITree[index] += val

            # Update index to that of parent
            # in update View
            index += index & (-index)

    # Returns count of inversions of size three
    def getInvCount(arr, n):

        invcount = 0  # Initialize result

        # Find maximum element in arrays
        maxElement = max(arr)

        # Create a BIT with size equal to
        # maxElement+1 (Extra one is used
        # so that elements can be directly
        # be used as index)
        BIT = [0] * (maxElement + 1)
        for i in range(1, maxElement + 1):
            BIT[i] = 0
        for i in range(n - 1, -1, -1):

            invcount += getSum(BIT, arr[i] - 1)
            updateBIT(BIT, maxElement, arr[i], 1)
        return invcount

    # Driver code
    A = list(map(int, input().split()))
    tot1 = getInvCount(A, n)

    tot2 = count_bigger(A)
    mod = 10**9+7
    print((tot1*k + tot2*(k*(k-1)//2)) % mod)

resolve()

Submission status: Accepted

Solution code:
n,k = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
mod = 10**9 + 7

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from sys import stdin
from collections import defaultdict, deque, Counter
import sys
from bisect import bisect_left
import heapq
import math

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

#n = int(stdin.readline().rstrip())
#l = list(map(int, stdin.readline().rstrip().split()))
n,k = map(int, stdin.readline().rstrip().split())
#S = [list(stdin.buffer.readline().decode().rstrip()) for _ in range(h)]
A = list(map(int, stdin.readline().rstrip().split()))



ans = 0
for i in range(n):
    right = 0
    left = 0
    for j in range(i):
        if A[i] > A[j]:
            left += 1
    for j in range(i+1, n):
        if A[i] > A[j]:
            right += 1
    ans += int(right*k*(k+1)//2 + left*k*(k-1)//2)

print(ans % MOD)

Submission status: Accepted

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

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

inside = [0] * n
outside = [0] * n

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

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

ans = 0
ans += sum(inside) * k
ans %= mod
ans += sum(outside) * k * (k - 1) // 2
ans %= mod
print(ans)

Submission status: Accepted

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

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

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

t = (t * k) % (10**9 + 7)

L = sorted(L)
s = 0
for i in range(n):
    for j in range(i + 1, n):
        if L[i] < L[j]:
            s += 1
k = k - 1
sum = (k * (k + 1)//2)% (10**9 + 7)
s = (s * sum) % (10**9 + 7)
print((t + s) % (10**9 + 7))

Submission status: Accepted

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


af = [0]*n
al = [0]*n

for i in range(n):
    b = a[i+1:]
    af[i] = len(b[b < a[i]])
    al[i] = len(a[a < a[i]])
s = 0

for i in range(n):
    s += al[i] * (k**2 - k*(k+1)//2) + af[i] * k
    s %= 1000000007
print(s)

Submission status: Accepted

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

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

ans = (nor * K * (K + 1) // 2 + rev * 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()))

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

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

Submission status: Accepted

Solution code:
import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))
## dp ##
def DD2(d1,d2,init=0): return [[init]*d2 for _ in range(d1)]
def DD3(d1,d2,d3,init=0): return [DD2(d2,d3,init) for _ in range(d1)]
## math ##
def to_bin(x: int) -> str: return format(x, 'b') # rev => int(res, 2)
def to_oct(x: int) -> str: return format(x, 'o') # rev => int(res, 8)
def to_hex(x: int) -> str: return format(x, 'x') # rev => int(res, 16)
MOD=10**9+7
def divc(x,y) -> int: return -(-x//y)
def divf(x,y) -> int: return x//y
def gcd(x,y):
    while y: x,y = y,x%y
    return x
def lcm(x,y): return x*y//gcd(x,y)
def enumerate_divs(n):
    """Return a tuple list of divisor of n"""
    return [(i,n//i) for i in range(1,int(n**0.5)+1) if n%i==0]
def get_primes(MAX_NUM=10**3):
    """Return a list of prime numbers n or less"""
    is_prime = [True]*(MAX_NUM+1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(MAX_NUM**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i*2, MAX_NUM+1, i):
            is_prime[j] = False
    return [i for i in range(MAX_NUM+1) if is_prime[i]]
## libs ##
from itertools import accumulate as acc, combinations as combi, product, combinations_with_replacement as combi_dup
from collections import deque, Counter
from heapq import heapify, heappop, heappush
from bisect import bisect_left
#======================================================#

def main():
    n, k = MII()
    aa = MII()
    cnt = 0
    for i in range(n):
        a = aa[i]
        for j in range(i,n):
            if a > aa[j]:
                cnt += 1
    cnt_s = 0
    aa.sort(reverse=True)
    for i in range(n):
        a = aa[i]
        for j in range(i,n):
            if a > aa[j]:
                cnt_s += 1
    print((cnt*k+cnt_s*(k*(k-1))//2)%MOD)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

A=[int(N) for N in A]

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

a = (K*(K-1)//2)%(10**9+7)
b = foll*K%(10**9+7)
u= (prev+foll)*a+b
print(u%(10**9+7))

Submission status: Accepted

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

p = 10**9 + 7

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

print((all * K * (K-1)//2 + K * aft) % p)

Submission status: Accepted

Solution code:
def main():
    n,k = map(int,input().split())
    a = list(map(int,input().split()))
    MOD = 10 ** 9 + 7
    sm1 = [0] * n
    sm2 = [0] * n
    for i in range(n):
        now = a[i]
        for j in range(i+1,n):
            if now > a[j]:
                sm1[i] += 1
    for i in range(n):
        now = a[i]
        for j in range(i):
            if now > a[j]:
                sm2[i] += 1
    a1 = sum(sm1) % MOD
    d = (sum(sm2) + a1) % MOD

    ans = k * (2*a1 + (k-1)*d)
    ans %= MOD
    inv_2 = power_func(2,MOD-2,MOD)
    ans = ans *inv_2
    print(ans%MOD)

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    import bisect
    
    N,K=MI()
    A=LI()
    

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

        
    print(rev0)
        
               
    

main()

Submission status: Accepted

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

ans = 0
MOD = 10**9+7
for i in range(N):
    l = 0
    r = 0
    for j in range(N):
        if i<j:
            if A[i]>A[j]:
                r += 1
            else:
                pass
        elif i>j:
            if A[i]>A[j]:
                l += 1
            else:
                pass
    ans += l*max(0,(K-1)*(K)//2)
    ans %= MOD
    ans += r*(K+1)*K//2
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
N, K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
total = 0
B = [0]*N
for n in range(N):
  count = 0
  for m in range(N):
    if A[m]<A[n]:
      count += 1
  B[n] = count
for n in range(N):
  for m in range(n,N):
    if A[m]<A[n]:
      total+=1
total *= K
K = K*(K-1)//2
for b in B:
  total += b*K
  total %= 1000000007
print(total)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
lis = list(map(int, input().split()))
c1, c2 = 0, 0
for i in range(n):
        for j in range(n):
                if lis[i] > lis[j]:
                        c2 += 1
                        if j > i:
                                c1 += 1
ans = c1*k + c2*k*(k-1)//2
print(ans % 1000000007)

Submission status: Accepted

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


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

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

mod = 10**9 + 7

ans = z * (K) + y * (K) * (K-1)//2
print(ans % mod)

Submission status: Accepted

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


def read():
    N, K = map(int, input().strip().split())
    A = list(map(int, input().strip().split()))
    return N, K, A


class ModInt(int):
    
    MOD = 10**9+7

    def __new__(cls, x, *args, **kwargs):
        return super().__new__(cls, x % ModInt.MOD)

    def __add__(self, other):
        return ModInt(super().__add__(other) % ModInt.MOD)

    def __radd__(self, other):
        return ModInt(super().__radd__(other) % ModInt.MOD)

    def __mul__(self, other):
        return ModInt(super().__mul__(other) % ModInt.MOD)

    def __rmul__(self, other):
        return ModInt(super().__rmul__(other) % ModInt.MOD)

    def __pow__(self, other, *args):
        return ModInt(super().__pow__(other, ModInt.MOD))

    def __rpow__(self, other, *args):
        raise NotImplementedError()

    def __truediv__(self, other):
        return ModInt(super().__mul__(pow(other, ModInt.MOD-2, ModInt.MOD)))

    def __floordiv__(self, other):
        return self.__truediv__(other)

    def __rtruediv__(self, other):
        return ModInt(self.__pow__(ModInt.MOD-2).__mul__(other))

    def __rfloordiv__(self, other):
        return self.__rtruediv__(other)


def solve(N, K, A):
    ModInt.MOD = 10**9+7
    N = len(A)
    k = ModInt(K)
    t0 = k * (k+1) // 2  # 三角数
    t1 = (k-1) * k // 2

    c0 = 0
    c1 = 0
    for i in range(N):
        for j in range(i+1, N):
            if A[i] > A[j]:
                c0 += 1
            elif A[i] < A[j]:
                c1 += 1
    return c0 * t0 + c1 * t1


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Accepted

Solution code:

SOSU = (10**9 + 7)

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

#print(A)

cntall = 0
cntusiro = 0

for indexi, i in enumerate(A):
    for indexj, j in enumerate(A):
        if i > j :
            cntall += 1
            if indexi < indexj:
                cntusiro += 1
        #print("roop:",i,j,indexi,indexj,cntall,cntusiro)

anst = (k*(k -1))*cntall//2 + k * cntusiro 


ans = anst % SOSU

#print ( cntall, cntusiro)
#print(anst)
print(int(ans) )

Submission status: Accepted

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt, ceil
from functools import lru_cache, reduce
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定
def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True


# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret


# ここから書き始める
n, k = map(int, input().split())
a = list(map(int, input().split()))
inner = 0
for i in range(n - 1):
    cnt = 0
    for j in range(i + 1, n):
        if a[i] > a[j]:
            cnt += 1
    inner += cnt
inner *= k
outer = 0
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        if a[i] > a[j]:
            outer += 1
outer *= k * (k - 1) // 2
ans = (inner + outer) % MOD
print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
mod=10**9+7
a=list(map(int,input().split()))
tcount=0
hidaricount=[]
allcount=[]

for i in range(n):
    count=0
    for j in range(n):
        #print(a[i],a[j],"all")
        if a[i]<a[j]:
            count+=1
    allcount.append(count)


for i in range(n):
    count=0
    for j in range(i+1,n):
        #print(a[i],a[j])
        if a[i]<a[j]:
            count+=1
    hidaricount.append(count)  
#print(allcount)
#print(hidaricount)  
#print(sum(allcount),sum(hidaricount))
alls=sum(allcount)
hidari=alls-sum(hidaricount)
#print(alls,hidari)
print((hidari*k + alls*k*(k-1)//2 )%mod)

Submission status: Accepted

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

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

ans = 0
if K % 2 == 0:
    k = ((K//2)*(K+1)) % MOD
else:
    k = (K*((K+1)//2)) % MOD
for i in range(N):
    ans = (ans + (((k * p[i]) % MOD - (K*q[i]) % MOD) % MOD)) % MOD
print(ans)

Submission status: Accepted

Solution code:
import sys
rs = lambda: sys.stdin.readline().strip()
ri = lambda: int(rs())
rs_ = lambda: [_ for _ in rs().split()]
ri_ = lambda: [int(_) for _ in rs().split()]

MOD = 10 ** 9 + 7

N, K = ri_()
A = ri_()
ans = 0
for i in range(N):
    for j in range(N):
        if A[i] > A[j]:
            if i < j:
                ans += (K * (K + 1) // 2) % MOD
            elif i > j:
                ans += (K * (K - 1) // 2) % MOD
print(ans % MOD)

Submission status: Accepted

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

Submission status: Accepted

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

memo = [0] * (max_a + 1)
num = 0
for a in A:
    memo[a] += 1
    num += sum(memo[a+1:])

num_larger = 0
for a in A:
    num_larger += sum(memo[a+1:])

ans = ((num*K % MOD) + ((K*(K-1)//2)*num_larger) % MOD) % MOD
print(ans)

Submission status: Accepted

Solution code:
class SegmentTree:
    def __init__(self, a):
        self.padding = 0
        self.n = len(a)
        self.N = 2 ** (self.n-1).bit_length()
        self.seg_data = [self.padding]*(self.N-1) + a + [self.padding]*(self.N-self.n)
        for i in range(2*self.N-2, 0, -2):
            self.seg_data[(i-1)//2] = self.seg_data[i] + self.seg_data[i-1]
    
    def __len__(self):
        return self.n
    
    def update(self, i, x):
        idx = self.N - 1 + i
        self.seg_data[idx] += x
        while idx:
            idx = (idx-1) // 2
            self.seg_data[idx] = self.seg_data[2*idx+1] + self.seg_data[2*idx+2]
    
    def query(self, i, j):
        # [i, j)
        if i == j:
            return self.seg_data[self.N - 1 + i]
        else:
            idx1 = self.N - 1 + i
            idx2 = self.N - 2 + j # 閉区間にする
            result = self.padding
            while idx1 < idx2 + 1:
                if idx1&1 == 0: # idx1が偶数
                    result = result + self.seg_data[idx1]
                if idx2&1 == 1: # idx2が奇数
                    result = result + self.seg_data[idx2]
                    idx2 -= 1
                
                idx1 //= 2
                idx2 = (idx2 - 1)//2
            return result
    
    @property
    def data(self):
        return self.seg_data[self.N-1:self.N-1+self.n]


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

st = SegmentTree([0]*(max_a + 1))

num = 0
for a in A:
    st.update(a, 1)
    if a == max_a:
        continue
    num += st.query(a+1, max_a+1)

num_larger = 0
for a in A:
    if a == max_a:
        continue
    num_larger += st.query(a+1, max_a+1)

ans = ((num*K % MOD) + ((K*(K-1)//2)*num_larger) % MOD) % MOD
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

mod=10**9+7

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

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

Submission status: Accepted

Solution code:
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

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

    # add x to i
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

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

def inv(X):
    B = Bit(2000+1)
    inv = 0
    for i in range(len(X)):
        inv += i - B.sum(X[i])
        B.add(X[i], 1)
    return inv

A_inv = inv(A) % MOD
A2_inv = inv(A*2) % MOD

print((K*A_inv + ((K*(K-1))//2) * (A2_inv - 2*A_inv)) % MOD)

Submission status: Accepted

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

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

ans=(k*part)%MOD+(all*(k*(k-1))//2)%MOD
print(ans%MOD)

Submission status: Accepted

Solution code:
from collections import defaultdict
n,k=map(int,input().split())
a=list(map(int,input().split()))
mod=pow(10,9)+7
a0=0
d=defaultdict(lambda:0)
for i in range(n):
    a0+=len([s for s in a[:i] if s>a[i]])
    d[a[i]]+=1
keys=sorted(d.keys())
matagi=0
ni=n
for ky in keys:
    c=d[ky]
    ni-=c
    matagi+=ni*c
ans=(k*a0)%mod
ans+=(matagi*(k*(k-1))//2)%mod
print(ans%mod)

Submission status: Accepted

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

nums = [int(i) for i in input().split()]

mod = 10 ** 9 + 7

ans = 0
for i in range(n):
    c = 0
    for j in range(i + 1, n):
        if nums[i] > nums[j]:
            c += 1
    ans += (c * k) % mod

dp = [0] * n
for i in range(n):
    for j in range(n):
        if nums[i] > nums[j]:
            dp[i] += 1
for i in range(n):
    ans += ((k - 1) * k // 2 * dp[i]) % mod
print(ans % mod)

Submission status: Accepted

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

gen=10**9+7

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

kaburi = 0
sorta=sorted(a)
scnt=0
for i in range(n-1):
  if sorta[i]==sorta[i+1]:
    scnt+=1
  if sorta[i]!=sorta[i+1]:
    kaburi+=scnt*(scnt+1)//2
    scnt=0
kaburi+=scnt*(scnt+1)//2

print((k*count+(n*(n-1)//2-kaburi)*k*(k-1)//2)%gen)

Submission status: Accepted

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

for i in range(N):
    for j in range(i + 1, 2 * N):
        if j == N:
            c = b
        if A[i] > A[j] and j < N:
            b += 1
        elif A[i] > A[j] and j >= N:
            c += 1
    
    if b == c - b:
        ans += b * K * (K + 1) // 2
    else:
        ans += b * K + (c - b) * K * (K - 1) // 2
    
    b = 0
    c = 0

print(ans % mod)

Submission status: Accepted

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

for i in range(N):
    for j in range(i + 1, 2 * N):
        if j == N:
            c = b
        if A[i] > A[j] and j < N:
            b += 1
        elif A[i] > A[j] and j >= N:
            c += 1
    if b == c - b:
        ans += b * K * (K + 1) // 2
    else:
        ans += b * K + (c - b) * K * (K - 1) // 2
    b = 0
    c = 0

print(ans % mod)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
mod=1000000007
l1=0
l2=0
for i in range(n):
  for j in range(n):
    
    if i!=j:
      
      if a[i]>a[j]:
        l1+=1
        
        if i<j:
          l2+=1

k=k%mod
print((l2*k+l1*k*(k-1)//2)%mod)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H):
    '''
    H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right

# https://atcoder.jp/contests/jsc2019-qual/tasks/jsc2019_qual_b
# 転倒数はどのように増えるのか？
# もとの配列の転倒数と結合したときに増える転倒数に分解する
# もとの配列の転倒数はただ単純にK回掛ければいい
# 結合したときに増える転倒数はK*(K-1)//2をかける

N, K = read_ints()
A = read_ints()

n_origin = 0  # Aの転倒数
for a, b in combinations(A, r=2):
    if a > b:
        n_origin += 1

n_append = 0  # A+Aを結合したときに転倒数がいくつ増えるか
# これは愚直に各要素にたいして、以下の数がいくつあるか数え上げてもいいが、
# 結合したときの転倒数-2*n_originでも求められそう
for a, b in combinations(A + A, r=2):
    if a > b:
        n_append += 1
n_append -= n_origin * 2
print((n_origin * K + n_append * (K - 1) * K // 2) % MOD)

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

n, k = na()
a = na()

ans = 0
for i in range(n):
    bl = 0
    al = 0
    for j in range(i):
        if a[j] < a[i]:
            bl += 1
    for j in range(i + 1, n):
        if a[j] < a[i]:
            al += 1
    
    ans += al * (k * (k + 1) // 2) + bl * (k * (k - 1) // 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

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