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: Runtime Error

Solution code:
import math
def counter(A):
    cnt = 0
    for i,ai in enumerate(A):
        cnt += sum(a < ai for a in A[i+1:])
    return cnt
def counter_two(A):
    cnt = 0
    for i,ai in enumerate(A):
        cnt += sum(a < ai for a in A)
    return cnt
  

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

one_a = counter_one(A)
two_a = counter_two(A)

ans = (one_a*K)+((two_a)*(K*(K-1)//2))
print(int(ans%((10**9)+7)))

Submission status: Runtime Error

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

countR=0
countA=0

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

    for j in range(N):
        if a_array[i] > a_array[j]:
            countA += 1

print((countR * K + int(countA * K * (K-1) / 2)))%(10**9+7)

Submission status: Runtime Error

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

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

ans = ans_con + ans_con * K

print(ans)

Submission status: Runtime Error

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
B = A*K
C = 0
for i in range(len(B)-1):
  for j in range(i+1,len(B)):
    if(B[i]>B[j]):
      C+=1
print(C%(10^9+7))

Submission status: Runtime Error

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

result1:int = (one_tento * k) % (7 + 10**9)
result2:int = (two_tento * k * (k - 1) / 2) % (7 + 10**9)
result3:int = (result1 + result2) % (7 + 10**9)
print(int(result3))

Submission status: Runtime Error

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

result1:int = (one_tento * k) % (7 + 10**9)
result2:int = (two_tento * k * (k - 1) / 2) % (7 + 10**9)
result3:int = (result1 + result2)% (7 + 10**9)
print(int(result3))

Submission status: Runtime Error

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

one_tento:int = 0 # Aの転倒数を求める
for i in range(n-1):
    for j in range(i+1,n):
        if array[i] > array[j]:
            one_tento += 1
two_tento:int = 0 # ２つのAの転倒数を求める
for i in range(n):
    for j in range(n):
        if array[i] > array[j]:
            two_tento += 1

result1:int = (one_tento * k) % (7 + 10**9)
result2:int = (two_tento * k * (k - 1) / 2) % (7 + 10**9)
#print('本来のただしい答えは、{}'.format(int(result1 % (7 + 10 ** 9))))
#print('公式に当てはめた答えは{}'.format(int(result2 % (7 + 10 ** 9))))
result3:int = (result1 + result2)% (7 + 10**9)
print(int(result3))

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
a_lis = list(map(int,input().split())) * k
ans = 0
for cnt,i in enumerate(a_lis):
  for j in a_lis[:cnt]:
    if j > i:
      ans += 1
      
print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
N, K = [int(n) for n in input().split()]
A = [int(n) for n in "".join(input().split()) * K]
c = 0
for i in range(len(A)-1):
    for j in range(i+1, len(A)):
        if A[i] > A[j]:
            c += 1
print(c%(10**9+7))

Submission status: Runtime Error

Solution code:
N, K = [int(n) for n in input().split()]
A = [int(n) for n in " ".join(input()) * K]
print(sum([1 if A[i] > A[j] else 0 for i in range(N-1) for j in range(1, N)])%(10**9+7))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1000000)
from math import factorial, ceil, floor
from bisect import bisect_right as bsr
from operator import itemgetter as ig
from collections import defaultdict as dd
from collections import deque, Counter as cnt

# お約束
args = None
INF = float("inf")
MOD = int(1e9 + 7)
def input(*ps):
    if type(ps[0]) is list:
        return [input(*ps[0][:-1]) for _ in range(ps[0][-1])]
    elif len(ps) == 1:
        return ps[0](next(args))
    else:
        return [p(next(args)) for p in ps]
def nlist(n, v):
    if not n: return v.copy()
    return [nlist(n[1:], v) for _ in range(n[0])]

# バイナリインデックス木
class BIT:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
    def sum(self, i):
        s = 0
        while 0 < i:
            s += self.tree[i]
            s %= MOD
            i -= i & -i
        return s
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

# エントリーポイント
def main():
    N, K = input(int, int)
    A = input([int, N])

    MAX = 12
    bit = BIT(MAX)
    # 最終周をカウントする
    sum1 = []
    for i, a in enumerate(A, start=1):
        bit.add(a, 1)
        sum1.append(i - bit.sum(a))
    # 繰り返し周をカウントする
    sum2 = []
    for a in A:
        sum2.append(N - bit.sum(a))
    # (1 + (K - 1))回分を集計する
    ans = 0
    for v1, v2 in zip(sum1, sum2):
        ans += K * v1 + ((K * (K - 1)) // 2) * v2
        ans %= MOD
    print(ans)

if __name__ == '__main__':
    args = iter(sys.stdin.read().split())
    main()

Submission status: Runtime Error

Solution code:
import numpy as np
N, K = map(int,input().split())
A= list((map(int, input().split())))
an = (K*(K+1))//2
a = ((K-1)*K)//2
au =0
al = 0
for i in range(N):
    for j in range(N):
        au += 1 if A[i]<A[j] and i>j else 0
        al += 1 if A[i]<A[j] and i<j else 0
print((au*an+al*a)%(10**9+7))

Submission status: Runtime Error

Solution code:
from collections import Counter

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())
aaa = list(map(int, input().split()))
MOD = 10**9 + 7
bit = Bit(2001)
single = 0
for a in reversed(aaa):
  single += bit.sum(a)
  bit.add(a + 1, 1)
ans = single * k % MOD
coef = k * (k - 1) // 2 % MOD
cnt = Counter(aaa)
before = 0
for a,c in sorted(cnt.items()):
  ans = (ans + c * before * conf) % MOD
  before += c
print(ans)

Submission status: Runtime Error

Solution code:
from collections import Counter

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 & -1
    return s
  
  def add(self, i, x):
    while i <= self.size:
      self.tree[i] += x
      i += i & -i

n,k = map(int, input().split())
aaa = list(map(int, input().split()))
MOD = 10**9 + 7
bit = Bit(2001)
single = 0
for a in reversed(aaa):
  single += bit.sum(a)
  bit.add(a + 1, 1)
ans = single * k % MOD
coef = k * (k - 1) // 2 % MOD
cnt = Counter(aaa)
before = 0
for a,c in sorted(cnt.items()):
  ans = (ans + c * before * conf) % MOD
  before += c
print(ans)

Submission status: Runtime Error

Solution code:
from collections import Counter

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 & -1
    return s
  
  def add(self, i, x):
    while i <= self.size:
      i += i & -i

n,k = map(int, input().split())
aaa = list(map(int, input().split()))
MOD = 10**9 + 7
bit = Bit(2001)
single = 0
for a in reversed(aaa):
  single += bit.sum(a)
  bit.add(a + 1, 1)
ans = single * k % MOD
coef = k * (k - 1) // 2 % MOD
cnt = Counter(aaa)
before = 0
for a,c in sorted(cnt.items()):
  ans = (ans + c * before * conf) % MOD
  before += c
print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools
import numpy as np
 
DIV_NUM = 1000000000 + 7
 
INPUT_NUMS = list(map(int, input().split()))
N=int(INPUT_NUMS[0])
K=int(INPUT_NUMS[1])
 
A = [int(x) for x in input().split()]
AA = np.array(A , dtype='int64')

if N==1:
    print(0)
    exit()

tree = [0] * (N+100)

def BIT_update(x):
    while x <= N:
        tree[x] += 1
        y = x
        z = 1
        while y > 0:
            if y % 2 == 1:
                x += z
                break
            y //= 2
            z *= 2

def BIT_sum(x):
    s = 0
    while x > 0:
        s += tree[x]
        y = x
        z = 1
        while y > 0:
            if y % 2 == 1:
                x -= z
                break
            y //= 2
            z *= 2
    return s
 
answer = N*(N-1)//2
for i in AA:
    answer -= BIT_sum(int(i))
    BIT_update(int(i))

B = sorted(A)
 
q=0
p=B[0]
r=0
for i in range(1,N):
    if B[i]>p:
        p=B[i]
        r=i
    q += r
 
# print(answer,K)
answer = answer % DIV_NUM
answer = int(answer)
answer = (answer * K) % DIV_NUM
q = q % DIV_NUM
answer = answer + q * K * (K-1) // 2
answer = answer % DIV_NUM
print(answer)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools
import numpy as np
 
DIV_NUM = 1000000000 + 7
 
INPUT_NUMS = list(map(int, input().split()))
N=int(INPUT_NUMS[0])
K=int(INPUT_NUMS[1])
 
A = [int(x) for x in input().split()]
AA = np.array(A , dtype='int64')

if N==1:
    print(0)
    exit()
 
tree = [0] * (N+1)

def BIT_update(x):
    while x <= N:
        tree[x] += 1
        y = x
        z = 1
        while y > 0:
            if y % 2 == 1:
                x += z
                break
            y //= 2
            z *= 2

def BIT_sum(x):
    s = 0
    while x > 0:
        s += tree[x]
        y = x
        z = 1
        while y > 0:
            if y % 2 == 1:
                x -= z
                break
            y //= 2
            z *= 2
    return s
 
answer = N*(N-1)//2
for i in AA:
    answer -= BIT_sum(int(i))
    BIT_update(int(i))

B = sorted(A)
 
q=0
p=B[0]
r=0
for i in range(1,N):
    if B[i]>p:
        p=B[i]
        r=i
    q += r
 
# print(answer,K)
answer = answer % DIV_NUM
answer = int(answer)
answer = (answer * K) % DIV_NUM
q = q % DIV_NUM
answer = answer + q * K * (K-1) // 2
answer = answer % DIV_NUM
print(answer)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools
import numpy as np
 
DIV_NUM = 1000000000 + 7
 
INPUT_NUMS = list(map(int, input().split()))
N=int(INPUT_NUMS[0])
K=int(INPUT_NUMS[1])
 
A = [int(x) for x in input().split()]
AA = np.array(A , dtype='int64')

if N==1:
    print(0)
    exit()
 
tree = [0] * (N+1)

def BIT_update(x):
    while x <= N:
        tree[x] += 1
        y = x
        z = 1
        while y:
            if y % 2 == 1:
                x += z
                break
            y /= 2
            z *= 2
def BIT_sum(x):
    s = 0
    while x > 0:
        s += tree[x]
        y = x
        z = 1
        while y:
            if y % 2 == 1:
                x -= z
                break
            y /= 2
            z *= 2
    return s
 
answer = N*(N-1)//2
for i in AA:
    answer -= BIT_sum(int(i))
    BIT_update(int(i))

B = sorted(A)
 
q=0
p=B[0]
r=0
for i in range(1,N):
    if B[i]>p:
        p=B[i]
        r=i
    q += r
 
# print(answer,K)
answer = answer % DIV_NUM
answer = int(answer)
answer = (answer * K) % DIV_NUM
q = q % DIV_NUM
answer = answer + q * K * (K-1) // 2
answer = answer % DIV_NUM
print(answer)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools
import numpy as np
 
DIV_NUM = 1000000000 + 7
 
INPUT_NUMS = list(map(int, input().split()))
N=int(INPUT_NUMS[0])
K=int(INPUT_NUMS[1])
 
A = [int(x) for x in input().split()]
AA = np.array(A , dtype='int64')

if N==1:
    print(0)
    exit()
 
tree = [0] * (N+1)

def BIT_update(x):
    while x <= N:
        tree[x] += 1
        y = x
        z = 1
        while y:
            if y % 2 == 1:
                x += z
                break
            y /= 2
            z *= 2
def BIT_sum(x):
    s = 0
    while x > 0:
        s += tree[x]
        y = x
        z = 1
        while y:
            if y % 2 == 1:
                x -= z
                break
            y /= 2
            z *= 2
    return s
 
answer = N*(N-1)//2
for i in AA:
    answer -= BIT_sum(int(i))
    BIT_update(int(i))

print(type(i),type(N))
print(tree)


B = sorted(A)
 
q=0
p=B[0]
r=0
for i in range(1,N):
    if B[i]>p:
        p=B[i]
        r=i
    q += r
 
# print(answer,K)
answer = answer % DIV_NUM
answer = int(answer)
answer = (answer * K) % DIV_NUM
q = q % DIV_NUM
answer = answer + q * K * (K-1) // 2
answer = answer % DIV_NUM
print(answer)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools
import numpy as np
 
DIV_NUM = 1000000000 + 7
 
INPUT_NUMS = list(map(int, input().split()))
N=int(INPUT_NUMS[0])
K=int(INPUT_NUMS[1])
 
A = [int(x) for x in input().split()]
AA = np.array(A , dtype='int64')
Q=np.array([0], dtype = 'int64')
if N==1:
    print(0)
    exit()
 
tree = [0] * (N+1)
 
# https://atcoder.jp/contests/chokudai_S001/submissions/6789704
def BIT_update(x):
    Q[0]=x
    while Q[0] <= N:
        tree[Q[0]] += 1
        Q[0] += Q[0]&(-Q[0])
def BIT_sum(x):
    s = 0
    Q[0]=x
    while Q[0] > 0:
        s += tree[Q[0]]
        Q[0] -= Q[0]&(-Q[0])
    return s
 
answer = N*(N-1)//2
for x in AA:
    answer -= BIT_sum(int(x))
    BIT_update(int(x))

#print(type(x),type(N))
#print(tree)


B = sorted(A)
 
q=0
p=B[0]
r=0
for i in range(1,N):
    if B[i]>p:
        p=B[i]
        r=i
    q += r
 
# print(answer,K)
answer = answer % DIV_NUM
answer = int(answer)
answer = (answer * K) % DIV_NUM
q = q % DIV_NUM
answer = answer + q * K * (K-1) // 2
answer = answer % DIV_NUM
print(answer)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools
import numpy as np
 
DIV_NUM = 1000000000 + 7
 
INPUT_NUMS = list(map(int, input().split()))
N=int(INPUT_NUMS[0])
K=int(INPUT_NUMS[1])
 
A = [int(x) for x in input().split()]
AA = np.array(A)
if N==1:
    print(0)
    exit()
 
tree = np.array([0] * (N+1) )
 
# https://atcoder.jp/contests/chokudai_S001/submissions/6789704
def BIT_update(x):
    while x <= N:
        tree[x] += 1
        x += x&(-x)
def BIT_sum(x):
    s = 0
    while x > 0:
        s += tree[x]
        x -= x&(-x)
    return s
 
answer = N*(N-1)//2
for x in AA:
    answer -= BIT_sum(int(x))
    BIT_update(int(x))
 
B = sorted(A)
 
q=0
p=B[0]
r=0
for i in range(1,N):
    if B[i]>p:
        p=B[i]
        r=i
    q += r
 
# print(answer,K)
answer = answer % DIV_NUM
answer = int(answer)
answer = (answer * K) % DIV_NUM
q = q % DIV_NUM
answer = answer + q * K * (K-1) // 2
answer = answer % DIV_NUM
print(answer)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools
import numpy as np
 
DIV_NUM = 1000000000 + 7
 
INPUT_NUMS = list(map(int, input().split()))
N=int(INPUT_NUMS[0])
K=int(INPUT_NUMS[1])
 
A = [int(x) for x in input().split()]
AA = np.array(A)
if N==1:
    print(0)
    exit()
 
tree = np.array([0] * (N+1) )
 
# https://atcoder.jp/contests/chokudai_S001/submissions/6789704
def BIT_update(x):
    while x <= N:
        tree[x] += 1
        y = int(x)
        x += y&(-y)
def BIT_sum(x):
    s = 0
    while x:
        s += tree[x]
        y = int(x)
        x -= y&(-y)
    return s
 
answer = N*(N-1)//2
for x in AA:
    answer -= BIT_sum(int(x))
    BIT_update(int(x))
 
B = sorted(A)
 
q=0
p=B[0]
r=0
for i in range(1,N):
    if B[i]>p:
        p=B[i]
        r=i
    q += r
 
# print(answer,K)
answer = answer % DIV_NUM
answer = int(answer)
answer = (answer * K) % DIV_NUM
q = q % DIV_NUM
answer = answer + q * K * (K-1) // 2
answer = answer % DIV_NUM
print(answer)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools
import numpy as np
 
DIV_NUM = 1000000000 + 7
 
INPUT_NUMS = list(map(int, input().split()))
N=int(INPUT_NUMS[0])
K=int(INPUT_NUMS[1])
 
A = [int(x) for x in input().split()]
AA = np.array(A)
if N==1:
    print(0)
    exit()
 
tree = np.array([0] * (N+1) )
 
# https://atcoder.jp/contests/chokudai_S001/submissions/6789704
def BIT_update(tree,x):
    while x <= N:
        tree[x] += 1
        y = int(x)
        x += y&(-y)
def BIT_sum(tree,x):
    s = 0
    while x:
        s += tree[x]
        y = int(x)
        x -= y&(-y)
    return s
 
answer = N*(N-1)//2
for x in AA:
    answer -= BIT_sum(tree,int(x))
    BIT_update(tree,int(x))
 
B = sorted(A)
 
q=0
p=B[0]
r=0
for i in range(1,N):
    if B[i]>p:
        p=B[i]
        r=i
    q += r
 
# print(answer,K)
answer = answer % DIV_NUM
answer = int(answer)
answer = (answer * K) % DIV_NUM
q = q % DIV_NUM
answer = answer + q * K * (K-1) // 2
answer = answer % DIV_NUM
print(answer)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools
import numpy as np
 
DIV_NUM = 1000000000 + 7
 
INPUT_NUMS = list(map(int, input().split()))
N=int(INPUT_NUMS[0])
K=int(INPUT_NUMS[1])
 
A = [int(x) for x in input().split()]
AA = np.array(A)
if N==1:
    print(0)
    exit()
 
tree = np.array([0] * (N+1) )
 
# https://atcoder.jp/contests/chokudai_S001/submissions/6789704
def BIT_update(tree,x):
    while x <= N:
        tree[x] += 1
        x += x&(-x)
def BIT_sum(tree,x):
    s = 0
    while x:
        s += tree[x]
        x -= x&(-x)
    return s
 
answer = N*(N-1)//2
for x in AA:
    answer -= BIT_sum(tree,int(x))
    BIT_update(tree,int(x))
 
B = sorted(A)
 
q=0
p=B[0]
r=0
for i in range(1,N):
    if B[i]>p:
        p=B[i]
        r=i
    q += r
 
# print(answer,K)
answer = answer % DIV_NUM
answer = int(answer)
answer = (answer * K) % DIV_NUM
q = q % DIV_NUM
answer = answer + q * K * (K-1) // 2
answer = answer % DIV_NUM
print(answer)

Submission status: Runtime Error

Solution code:
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    b = a * k
    ans = 0
    maxa = max(a)
    dp = [0] * maxa
    for i in range(k * n):
        ans += dp[b[i] - 1]
        ans % 1000000007
        dp = [(x + 1) % 1000000007 for x in dp[:b[i] - 1]] + dp[b[i] - 1:]
    print(ans % 1000000007)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import Counter


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())
aaa = list(map(int, input().split()))
MOD = 10 ** 9 + 7
bit = Bit(n + 1)
single = 0
for a in reversed(aaa):
    single += bit.sum(a)
    bit.add(a + 1, 1)
ans = single * k % MOD
coef = k * (k - 1) // 2
cnt = Counter(aaa)
before = 0
for a, c in sorted(cnt.items()):
    ans = (ans + c * before * coef) % MOD
    before += c
print(ans)

Submission status: Runtime Error

Solution code:
from collections import Counter


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())
aaa = list(map(int, input().split()))
MOD = 10 ** 9 + 7
bit = Bit(n)
single = 0
for a in reversed(aaa):
    single += bit.sum(a - 1)
    bit.add(a, 1)
ans = single * k % MOD
coef = k * (k - 1) // 2
cnt = Counter(aaa)
before = 0
for a, c in sorted(cnt.items()):
    ans = (ans + c * before * coef) % MOD
    before += c
print(ans)

Submission status: Runtime Error

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

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

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

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

bit = Bit(N)

inter = 0
intra = 0
for i in range(len(A)):
    a = A[i]
    bit.add(a, 1)
    s_a = bit.sum(a)
    intra += i + 1 - s_a
    if a == 1:
        continue
    inter += bit.sum(a - 1)

mod = 10**9 + 7

ans = (intra * K * (K + 1) // 2) % mod
ans += inter * (K - 1) * K // 2 % mod
ans %= mod
print(ans)

Submission status: Runtime Error

Solution code:
import collections

N,K = map(int, input().split())
arr = list(map(int, input().split()))
c = collections.Counter(arr)

counts = list(c.values())[::-1]

if len(counts)==1:
  print(0)
else:
  value = 0
  for num in enumerate(arr):
    value += len([1 for x in arr if x<num])
  out_arr = value*K*(K-1)//2
  
  in_arr = 0
  for j,num in enumerate(arr):
    in_arr += len([1 for x in arr[j+1:] if x<num])
  in_arr = in_arr*K
  print((out_arr+in_arr)%1000000007)

Submission status: Runtime Error

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

tentosu_f = 0
tentosu_l = 0

for i in range(len(n)):
    for j in range(i+1, len(n)):
        if A[i] > A[j]:
            tentosu_f += 1

for i in range(n):
    for j range(n):
        if A[i] > A[j]:
            tentosu_l += 1
            
ans = ((tentosu_f * k) + ((k* (k-1)) / 2) * tentosu_l) % (10**9 + 7)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**30)

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

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

MOD = pow(10,9) + 7

p = 0

c = 0
d = 0
for i in range(n):
  for j in range(i+1,n):
    if(a[i] > a[j]):
      c += 1
      d += 1
    elif(a[i] < a[j]):
      d += 1


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

print(ans)

Submission status: Runtime Error

Solution code:

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

MOD = pow(10,9) + 7

p = 0

c = 0
d = 0
for i in range(n):
    for j in range(i+1,n):
      if(a[i] > a[j]):
        c += 1
        d += 1
      elif(a[i] < a[j]):
        d += 1


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

print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import typing

def kleene_inversion(n: int, k: int, a: typing.List[int]) -> int:
    res = 0
    for i, aa in enumerate(a, 1):
        s = sum(aa > aaa for aaa in a[i:])
        res += s * k
        res += s * (k - 1)
    return int(res % (10e9 + 7))




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

Submission status: Runtime Error

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

B = A * K

ans = 0

for i in range(len(B)):
    for j in range(len(B)):
        if B[j] < B[i] and i < j:
            ans += 1
        else:
            ans += 0
print(ans)

Submission status: Runtime Error

Solution code:
from itertools import groupby

R = lambda: map(int, input().split())
n, k = R()
a = list(R())
w = [0] * n

def merge(b, e):
    m = b + (e - b) // 2
    i, j = b, m
    r = 0
    while i < m and j < e:
        if a[i] <= a[j]:
            w[i + j] = a[i]
            i += 1
        else:
            r += m - i
            w[i + j] = a[j]
            j += 1
    a[e - m + i: e] = a[i: m]
    a[b: b + i + j] = w[:i + j]
    return r        
    
def mergesort(b, e):
    if e - b < 2:
        return 0
    mid = b + (e - b) // 2
    return mergesort(b, mid) + mergesort(mid, e) + merge(b, e)


r = k * mergesort(0, n)
print(a)
c = n * (n - 1) // 2
for _, g in groupby(a):
    x = sum(1 for _ in g)
    c -= x * (x - 1) // 2
print((r + c * k * (k - 1) // 2) % (10**9 + 7))

Submission status: Runtime Error

Solution code:
from itertools import groupby

R = lambda: map(int, input().split())
n, k = R()
a = list(R())
w = [0] * n

def merge(b, e):
    m = b + (e - b) // 2
    i, j = b, mid
    r = 0
    while i < m and j < e:
        if a[i] <= a[j]:
            w[i + j] = a[i]
            i += 1
        else:
            r += m - i
            w[i + j] = a[j]
            j += 1
    a[e - m + i: e] = a[i: m]
    a[b: b + i + j] = w[:i + j]
    return r        
    
def mergesort(b, e):
    if e - b < 2:
        return 0
    mid = b + (e - b) // 2
    return mergesort(b, mid) + mergesort(mid, e) + merge(b, e)


r = k * mergesort(0, n)
print(a)
c = n * (n - 1) // 2
for _, g in groupby(a):
    x = sum(1 for _ in g)
    c -= x * (x - 1) // 2
print((r + c * k * (k - 1) // 2) % (10**9 + 7))

Submission status: Runtime Error

Solution code:
import sys
from math import factorial, ceil, floor
from bisect import bisect_right as bsr
from operator import itemgetter as ig
from collections import defaultdict as dd
from collections import deque

# お約束
args = None
INF = float("inf")
MOD = int(1e9 + 7)
def input(*ps):
    if type(ps[0]) is list:
        return [input(*ps[0][:-1]) for _ in range(ps[0][-1])]
    elif len(ps) == 1:
        return ps[0](next(args))
    else:
        return [p(next(args)) for p in ps]

# バイナリインデックス木(BIT)
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
    def sum(self, i):
        s = 0
        while 0 < i:
            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

# エントリーポイント
def main():
    N, K = input(int, int)
    A = input([int, N])

    ppp = A * K
    bit = Bit(2010)
    ans = 0
    
    for i, p in enumerate(ppp):
        bit.add(p, 1)
        ans += i + 1 - bit.sum(p)
        ans %= MOD
    print(ans)

if __name__ == '__main__':
    args = iter(sys.stdin.read().split())
    main()

Submission status: Runtime Error

Solution code:
import sys
from math import factorial, ceil, floor
from bisect import bisect_right as bsr
from operator import itemgetter as ig
from collections import defaultdict as dd
from collections import deque

# お約束
args = None
INF = float("inf")
MOD = int(1e9 + 7)
def input(*ps):
    if type(ps[0]) is list:
        return [input(*ps[0][:-1]) for _ in range(ps[0][-1])]
    elif len(ps) == 1:
        return ps[0](next(args))
    else:
        return [p(next(args)) for p in ps]

# バイナリインデックス木(BIT)
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
      def sum(self, i):
        s = 0
        while 0 < i:
            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

# エントリーポイント
def main():
    N, K = input(int, int)
    A = input([int, N])

    ppp = A
    bit = Bit(2010)
    ans = 0
    
    for k in range(1, K + 1):
        for i, p in enumerate(ppp):
            bit.add(p, 1)
            ans += (K * i + 1) - bit.sum(p)
            ans %= MOD
    print(ans)

if __name__ == '__main__':
    args = iter(sys.stdin.read().split())
    main()

Submission status: Runtime Error

Solution code:
import sys
from math import factorial, ceil, floor
from bisect import bisect_right as bsr
from operator import itemgetter as ig
from collections import defaultdict as dd
from collections import deque

# お約束
args = None
INF = float("inf")
MOD = int(1e9 + 7)
def input(*ps):
    if type(ps[0]) is list:
        return [input(*ps[0][:-1]) for _ in range(ps[0][-1])]
    elif len(ps) == 1:
        return ps[0](next(args))
    else:
        return [p(next(args)) for p in ps]

# バイナリインデックス木(BIT)
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
      def sum(self, i):
        s = 0
        while 0 < i:
            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

# エントリーポイント
def main():
    N, K = input(int, int)
    A = input([int, N])

    ppp = A
    bit = Bit(10)
    ans = 0
    
    for k in range(1, K + 1):
        for i, p in enumerate(ppp):
            bit.add(p, 1)
            ans += (K * i + 1) - bit.sum(p)
            ans %= MOD
    print(ans)

if __name__ == '__main__':
    args = iter(sys.stdin.read().split())
    main()

Submission status: Runtime Error

Solution code:
a,b=input().split()
c=input().split()
c=c*int(b)
# print(c)
d=0
for i in range(len(c)):
    for j in range(i+1,len(c)):
        if(int(c[i])>int(c[j])):
            d=(d+1)%((10**9)+7)
print(d)

Submission status: Runtime Error

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

mod = 10 ** 9 + 7
k = k % mod
# 配列内で自身より小さい数の個数　前後別に求める
b = [[0, 0] for _ in range(n)]
for i in range(n):
    for j in range(n):
        if a[i] > a[j]:
            if i > j:
                b[i][0] += 1
            elif i < j:
                b[i][1] += 1
    b[i][0] = b[i][0] % mod
    b[i][1] = b[i][1] % mod
ans = 0
# kまでの和　後ろの数用
sigmakp = (((k * (k+1)) % mod) / 2) % mod
#sigmakp = int(sigmakp)
# k-1までの和　前の数用
sigmakn = (((k * (k-1)) % mod) / 2) % mod
#sigmakn = int(sigmakn)

for i in range(n):
    mae = (sigmakp * b[i][1]) % mod
    ushiro = (sigmakn * b[i][0]) % mod
    ans = ((mae + ushiro) % mod + ans) % mod 
print(int(ans)