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

Submission status: Runtime Error

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

k = k % mod
mod = 10 ** 9 + 7
# 配列内で自身より小さい数の個数　前後別に求める
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
            else:
                b[i][1] += 1
ans = 0
sigmakp = int(((k * (k+1)) % mod) / 2) % mod
sigmakn = int(((k * (k-1)) % mod) / 2) % mod
for i in range(n):
    mae = (sigmakp * b[i][1]) % mod
    ushiro = (sigmakn * b[i][0]) % mod
    ans = ((mae + ushiro) % mod + ans) % mod 
print(ans)

Submission status: Runtime Error

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

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
       
bit = Bit(n)
rbit = Bit(n)
left = 0
right = 0
for i, (p, rp) in enumerate(zip(a, reversed(a))):
  bit.add(p, 1)
  rbit.add(rp, 1)
  left += i + 1 - bit.sum(p)
  right += i + 1 - rbit.sum(rp)

def ssum(a, d, n):
  return n*(2*a+(n-1)*d)//2

print(
  (
    ssum(left, left, k)
    + ssum(0, right, k)
  )%d
)

Submission status: Runtime Error

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

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
       
bit = Bit(n)
rbit = Bit(n)
left = []
right = []
for i, (p, rp) in enumerate(zip(a, reversed(a))):
  bit.add(p, 1)
  rbit.add(rp, 1)
  left.append(i + 1 - bit.sum(p))
  right.append(i + 1 - rbit.sum(rp))

left = sum(left)
right = sum(right)

def ssum(a, d, n):
  return n*(2*a+(n-1)*d)//2

print(
  (
    ssum(left, left, k)
    + ssum(0, right, k)
  )%d
)

Submission status: Runtime Error

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

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
       
bit = Bit(n)
rbit = Bit(n)
left = []
right = []
for i, (p, rp) in enumerate(zip(a, reversed(a))):
  bit.add(p, 1)
  rbit.add(rp, 1)
  left.append(i + 1 - bit.sum(p))
  right.append(i + 1 - rbit.sum(rp))
right.reverse()

left = sum(left)
right = sum(right)

def ssum(a, d, n):
  return n*(2*a+(n-1)*d)//2

print(
  (
    ssum(left, left, k)
    + ssum(0, right, k)
  )%d
)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
arr = list(map(int, input().split()))
arr = arr * k
count = 0
#print(arr)
for i in range(len(arr)):
    for j in range(i+1, len(arr)):
        if arr[i] > arr[j]:
            count += 1
print(count)

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
A_list = list(map(int, input().split()))
same = 0
diff = 0

for i in range(N):
  for j in range(N):
    if N[i] > N[j]:
      if i < j:
        same += 1
        diff += 1
      elif i>j:
        diff += 1

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

Submission status: Runtime Error

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

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

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

print(count)

Submission status: Runtime Error

Solution code:
# coding: utf-8

import sys
import math
import collections
import itertools
def input(): return sys.stdin.readline().strip()
def gcd(x, y): return y if x % y == 0 else gcd(y, x % y)
def lcm(x, y): return (x * y) // gcd(x, y)
MOD = 10 **9 + 7

# N = int(input())
# S = input()
N, K = map(int, input().split())
# 横
A = [int(x) for x in input().split()]
# 縦
# A = [int(input()) for _ in range(N)]
# 多次元
# L = [[int(x) for x in input().split()] for _ in range(N)]

ans = 0
tmp = 0

for i, a in enumerate(A) :
    for aa in range(i + 1, N) :
        if a > A[aa] :
            ans += 1

for a in A :
    for aa in A :
        if a > aa :
            tmp += 1

print(((int((K*(K-1))//2)%MOD)*tmp+ans*K)%M)

Submission status: Runtime Error

Solution code:
from sys import stdin
from math import factorial
n,k = map(int,stdin.readline().rstrip().split())
li = list(map(int,stdin.readline().rstrip().split()))
nai = 0
ato = 0
point = 0
for i in range(n):
    for s in range(i+1,n):
        if li[i] > li[s]:
            nai += 1
    for v in range(n):
        if li[i] > li[v]:
            ato += 1
def combinations_count(j,r):
    return factorial(j) // (factorial(j - r) * factorial(r))
point += (nai*k)+(ato*combinations_count(k,2))
print(point%(10**9+7))

Submission status: Runtime Error

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

N,K = map(int, input().split())
A = list(map(int, input().split()))
A_ = sorted(A, reverse = True)
ans = 0
ans_ = 0
for i in range(0,N-1):
      for j in range(i+1,N):
          if A[i] > A[j]:
            ans += 1
         if A_[i] > A_[j]:
            ans_ += 1

print(((int((K*(K-1))/2)%M)*ans_+ans*K)%M)

Submission status: Runtime Error

Solution code:
import numpy as np
n, k = map(int, input().split())
a = list(map(int, input().split()))
x, y = 0, 0
for i in range(n):
    for j in range(n):
        if a[i] > a[j]:
            x += 1
        if (i < j) and (a[i] > a[j]):
            y += 1
num_np = np.array(num)
sum_left = sum(num_np[:,0])
sum_right = sum(num_np[:,1])
output = (x * k) % 1000000007 + (y * k * (k - 1) // 2) % 1000000007
print(output % 1000000007)

Submission status: Runtime Error

Solution code:
from sys import stdin
from math import factorial
n,k = map(int,stdin.readline().rstrip().split())
li = list(map(int,stdin.readline().rstrip().split()))
li_to = li*2
nai = 0
ato = 0
for i in range(len(li)):
    for s in range(i+1,len(li)):
        if li[i] > li[s]:
            nai += 1
    for p in range(len(li),len(li_to)):
        if li[i] > li_to[p]:
            ato += 1
def combinations_count(n, r):
    return factorial(n) // (factorial(n - r) * factorial(r))
point = 0
point += (nai*k)+(ato*combinations_count(k,2))
print(point%(10**9+7))

Submission status: Runtime Error

Solution code:
n,k = map(int, input().split())
*a, = map(int, input().split())
ans = 0
wer = 0

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

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

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

Submission status: Runtime Error

Solution code:
_, K = map(int, input())
a = list(map(int, input().split()))
s = [sum([b > c for c in a]) for b in a]
r = [sum([b > c for c in a[i:]]) for i, b in enumerate(a)]
b = (sum(r) + sum(s)*(K-1)/2)*K + sum(r)
print(int(b%(1e9+7)))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)

def tasu(a):
  if a == 1:
    return 1
  else:
    return a + tasu(a-1)
  
N, K = map(int, input().split())
A_list = list(map(int, input().split()))
count = 0

for i in range(N):
  for j in range(N):
    if i == j:
      continue
    elif (i<j) & (A_list[i] > A_list[j]):
      count += tasu(K)
    elif (i>j) & (A_list[i] > A_list[j]):
      count += tasu(K - 1)
print(count%(10**9 + 7))

Submission status: Runtime Error

Solution code:
# factorial of big numbers 
  
# Maximum number of digits in  
# output 
MAX=100000
  
# This function multiplies x 
# with the number represented by res[]. 
# res_size is size of res[] or 
# number of digits in the number 
# represented by res[]. This function 
# uses simple school mathematics 
# for multiplication. 
# This function may value of res_size 
# and returns the new value of res_size 
def multiply(x, res, res_size): 
  
    # Initialize carry 
    carry = 0
  
    # One by one multiply n with 
    # individual digits of res[] 
    for i in range(res_size): 
        prod = res[i] * x + carry 
  
        # Store last digit of 
        # 'prod' in res[] 
        res[i] = prod % 10
  
        # Put rest in carry 
        carry = prod // 10
  
    # Put carry in res and 
    # increase result size 
    while (carry): 
        res[res_size] = carry % 10
        carry = carry // 10
        res_size+=1
  
    return res_size 
  
  
# This function finds 
# power of a number x 
def power(x,n): 
      
    # printing value "1" for power = 0 
    if (n == 0) :  
        print("1") 
        return
      
    res=[0 for i in range(MAX)] 
    res_size = 0
    temp = x 
  
    # Initialize result 
    while (temp != 0): 
        res[res_size] = temp % 10; 
        res_size+=1
        temp = temp // 10
  
  
    # Multiply x n times 
    # (x^n = x*x*x....n times) 
    for i in range(2, n + 1): 
        res_size = multiply(x, res, res_size) 
  
    print(x , "^" , n , " = ",end="") 
    for i in range(res_size - 1, -1, -1): 
        print(res[i], end="") 
  
  
# Driver program 
  


n,k=input().split(" ")
n=int(n)
k=int(k)
s=input()
li=s.split(" ")


ans=1
for i in range(len(li)-1):
    if li[i]!=li[i+1]:
        ans+=1
print(power(ans,k)-1)

Submission status: Runtime Error

Solution code:
import sys

stdin = sys.stdin

sn = lambda : stdin.readline().rstrip()
an = lambda : map(int, stdin.readline().split())
ni = lambda : int(sn())

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

x = 0
y = 0

n, k = an()
a = list(an())

mod = int(1e9)+7
ans = 0

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

ans += x * f(k)
ans += y * f(k - 1)
print(ans % mod)

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
a=[int(i) for i in input().split()]
a.reverse()
dp=[0]*2000
x=0
for i in range(n):
    dp[a[i]]+=1
    x+=sum(dp[:a[i]])
y=0
for i in range(n):
    y+=sum(dp[:a[i]])

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

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict, Counter, deque
from itertools import accumulate, permutations, combinations
from operator import itemgetter
from bisect import bisect_left, bisect_right, bisect
from heapq import heappop, heappush
from fractions import gcd
from math import ceil, floor, sqrt, cos, sin, pi, factorial
from copy import deepcopy

# If you use recursive call, uncomment this code
#sys.setrecursionlimit(10**6)

MOD = 10**9+7

class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )

def main():
    N,K = map(int, input().split())
    aa = list(map(int, input().split()))
    bit = Bit(len(aa))
    ans = ModInt(0)

    # inside aa
    tmp = 0
    for i in range(N):
        for j in range(i,N):
            if i == j:
                continue
            if aa[i]>aa[j]:
                tmp += 1
    ans += tmp * K

    # between two aa
    tmp = 0
    for i in range(N):
        for j in range(N):
            if aa[i]>aa[j]:
                tmp += 1
    ans += tmp * (K*(K-1)//2)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
_, K = map(int, input())
a = list(map(int, input().split()))
s = [sum([b > c for c in a]) for b in a]
l = [sum([l < a[i] for l in a[:i]]) for i in range(1, len(a))]
l.insert(0, 0)
r = [b - c for b, c in zip(s, l)]
a = (sum(r)*(1+K) + sum(l)*(K-1))*K/2
print(int(a%(1e9+7)))

Submission status: Runtime Error

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

N, K = map(int, input().split())
A = list(map(int, input().split()))
B = A * K
count = 0

for i in range(N):
    for j in range(N):
        if i < j and A[i] > A[j]:
            count += 1
count *= K + (K * (K - 1)) // 2

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

Submission status: Runtime Error

Solution code:
n,k = map(int, input().split(' '))
a = list(map(int, input().split(' ')))
A = (10**9)+7
c_in = 0
for i in range(n):
  for j, t in enumerate(a[:i]):
    c_in += int(t > a[i])
  count[a[i]-1] += 1
c_out = 0
for i in range(n):
  for j, t in enumerate(a):
    c_out += int(t > a[i])
N = (k*c_in)%A + ((k*(k-1)//2)*c_out)%A
print(int(N))

Submission status: Runtime Error

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

if k % 2 == 0:
    mul = (1 + k) * (k // 2)
else:
    mul = (1 + k) * (k // 2) + (k // 2 + 1)
if k > 1:
    k -= 1
    if k % 2 == 0:
        mul2 = (1 + k) * (k // 2)
    else:
        mul2 = (1 + k) * (k // 2) + (k // 2 + 1)
print(((cnt * mul) + (cnt2 * mul2)) % 1000000007)

Submission status: Runtime Error

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


diff = []
npA = np.array(A)
lenA = len(A)
for a in A:
    temp = list(np.array([a for i in range(lenA)]) - npA)
    diff.append(temp)

D = np.array(diff)

upD = np.triu(D,k=1)

upC = np.count_nonzero(upD>0)

ans = int(K*(2*upC) - dwC)
print(ans%(1000000007))

Submission status: Runtime Error

Solution code:
#######################################
prime = 10**9+7

def sowa(num):
  return int((1+num)*num/2)
#######################################
n,k = map(int, input().split())
a = list(map(int, input().split()))

tento1 = [sum([1 if a[i]>a[j] else 0 for j in range(i+1,n)]) for i in range(n-1)]
tento2 = [sum([1 if a[i]>a[j] else 0 for j in range(n)]) for i in range(n)]


ret = (sum(tento1) *k %prime) + (sum(tento2) *(sowa(k-1) %prime) %prime)
print(int(ret%prime)))

Submission status: Runtime Error

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


li = []

for i in range(n):
    count=0
    for j in range(n):
        if List[i]>List[j]:
            count += 1
    li.append(count)
#print(str(sum(li))+"li")


count2=0

for i in range(1,n):
    for j in range(i+1,n+1):
        #print(i,j)
        if int(List[i-1]) > int(List[j-1]):
            count2 += 1
    #print(str(count2)+"count2")


for m in range(1,k):
    counted=count2+sum(li)*(m)
counted += count2



ans = counted % 1000000007
print(ans)

Submission status: Runtime Error

Solution code:
INF = 1000000007

n, k = map(int, input().split())
a = list(map(int, input().split()))
ans_i = 0
ans_e = 0

for i in range(len(a)):
    for j in range(len(a)):
        if i == j: continue
        #print(a[i], a[j])
        if a[i] > a[j]:
            if i < j:
                ans_i += 1
            else:
                ans_e += 1
x = ans_i * k
ans = ans_i + ans_e
y = ans * (k * (k-1) )// 2)
print(int((x + y) % INF))

Submission status: Runtime Error

Solution code:
import bisect
MOD = 10**9 + 7
 
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 = [int(item) for item in input().split()]
a = [int(item) for item in input().split()]
bit = Bit(n*2)
ans = 0
 
for i, p in enumerate(a):
    bit.add(p, 1)
    ans += i + 1 - bit.sum(p)
 
a.sort()
big = 0
for item in a:
    big += n - bisect.bisect_right(a, item)
 
times = (k * (k - 1) // 2) % MOD
ans2 = (ans * k) % MOD + (big * times) % MOD
ans2 %= MOD
print(ans2)

Submission status: Runtime Error

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


li = []

for i in range(n):
    count=0
    for j in range(n):
        if List[i]>List[j]:
            count += 1
    li.append(count)
print(str(sum(li))+"li")


count2=0

for i in range(1,n):
    for j in range(i+1,n+1):
        #print(i,j)
        if int(List[i-1]) > int(List[j-1]):
            count2 += 1
    #print(str(count2)+"count2")


for m in range(k-1,0,-1):
    counted=count2+sum(li)*(m)




ans = counted % 1000000007
print(ans)

Submission status: Runtime Error

Solution code:
import bisect
MOD = 10**9 + 7
 
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 = [int(item) for item in input().split()]
a = [int(item) for item in input().split()]
bit = Bit(pow(2,(n.bit_length() + 1)) * 2)
ans = 0
 
for i, p in enumerate(a):
    bit.add(p, 1)
    ans += i + 1 - bit.sum(p)
 
a.sort()
big = 0
for item in a:
    big += n - bisect.bisect_right(a, item)
 
times = (k * (k - 1) // 2) % MOD
ans2 = (ans * k) % MOD + (big * times) % MOD
ans2 %= MOD
print(ans2)

Submission status: Runtime Error

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


li = []

for i in range(n):
    count=0
    for j in range(n):
        if List[i]>List[j]:
            count += 1
    li.append(count)
print(str(sum(li))+"li")


count2=0

for i in range(1,n):
    for j in range(i+1,n+1):
        #print(i,j)
        if int(List[i-1]) > int(List[j-1]):
            count2 += 1
    #print(str(count2)+"count2")


for m in range(k-1,0,-1):
    counted=count2+count2*(m-1)




ans = counted % 1000000007
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)
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,x)
    BIT_update(tree,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:
N, K = map(int, input().split())
a = list(map(int, input().split()))
s = [sum([b > c for c in a]) for b in a]
l = [sum([l < a[i] for l in a[:i]]) for i in range(1, len(a))]
l.insert(0, 0)
r = [[b - c for b, c in zip(s, l)]]
a = sum(r) * (1+K)*K/2 + sum(l) * (K-1)*K/2
print(int(a)%(1e9+7))

Submission status: Runtime Error

Solution code:
n, k = map(long, input().split())
a = list(map(long, input().split()))
mod = 10**9 + 7
ans = 0
fflag = 0
bflag = 0

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

ans = (long((fflag+bflag)*k*(k+1)/2) - fflag*k)%mod
print(ans)

Submission status: Runtime Error

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

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

def count_inversion(sequence):
    return sum(sum(m<n for m in sequence[i+1:]) for i,n in enumerate(sequence))
  
ans = count_inversion(b)

print(ans % (1000000000 + 7))

Submission status: Runtime Error

Solution code:
import numpy as np

def mergeSort(arr, n): 
    # A temp_arr is created to store 
    # sorted array in merge function 
    temp_arr = [0]*n 
    return _mergeSort(arr, temp_arr, 0, n-1) 
  
# This Function will use MergeSort to count inversions 
  
def _mergeSort(arr, temp_arr, left, right): 
  
    # A variable inv_count is used to store 
    # inversion counts in each recursive call 
  
    inv_count = 0
  
    # We will make a recursive call if and only if 
    # we have more than one elements 
  
    if left < right: 
  
        # mid is calculated to divide the array into two subarrays 
        # Floor division is must in case of python 
  
        mid = (left + right)//2
  
        # It will calculate inversion counts in the left subarray 
  
        inv_count = _mergeSort(arr, temp_arr, left, mid) 
  
        # It will calculate inversion counts in right subarray 
  
        inv_count += _mergeSort(arr, temp_arr, mid + 1, right) 
  
        # It will merge two subarrays in a sorted subarray 
  
        inv_count += merge(arr, temp_arr, left, mid, right) 
    return inv_count 
  
# This function will merge two subarrays in a single sorted subarray 
def merge(arr, temp_arr, left, mid, right): 
    i = left     # Starting index of left subarray 
    j = mid + 1 # Starting index of right subarray 
    k = left     # Starting index of to be sorted subarray 
    inv_count = 0
  
    # Conditions are checked to make sure that i and j don't exceed their 
    # subarray limits. 
  
    while i <= mid and j <= right: 
  
        # There will be no inversion if arr[i] <= arr[j] 
  
        if arr[i] <= arr[j]: 
            temp_arr[k] = arr[i] 
            k += 1
            i += 1
        else: 
            # Inversion will occur. 
            temp_arr[k] = arr[j] 
            inv_count += (mid-i + 1) 
            k += 1
            j += 1
  
    # Copy the remaining elements of left subarray into temporary array 
    while i <= mid: 
        temp_arr[k] = arr[i] 
        k += 1
        i += 1
  
    # Copy the remaining elements of right subarray into temporary array 
    while j <= right: 
        temp_arr[k] = arr[j] 
        k += 1
        j += 1
  
    # Copy the sorted subarray into Original array 
    for loop_var in range(left, right + 1): 
        arr[loop_var] = temp_arr[loop_var] 
          
    return inv_count 
  
# Driver Code 
# Given array is 



print("Number of inversions are", result) 
N,K = list(map(int,input().split()))
l = list(map(int,input().split()))
L = np.array(l)
for _ in range(K-1):
    L = np.append(L,l)

arr = L
n = len(L) 
c = mergeSort(arr, n) 


print(c%((10**7)+7))

Submission status: Runtime Error

Solution code:



def bitsum(bit,i):
    s = 0
    while i > 0:
        s += bit[i]
        i -= i&(-i)
    return s
    

def bitadd(bit,i,x):
    while i <= N:
        bit[i] += x
        i += i&(-i)
    return bit
    
#################################
import math
N, K = map(int,input().split())
a = list(map(int,input().split()))


n_ = int(math.log2(N)) + 1
bit = [0] * (2**n_)
bit.append(0)

################################
ass = 0
for j in range(N):
    ass += j-bitsum(bit,a[j])
    bit = bitadd(bit,a[j],1)

Ans = ass*(K*(K+1)/2)+(N*(N-1)/2-ass)*(K*(K-1)/2)

print(int(Ans%(10^9+7)))

Submission status: Runtime Error

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

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

#print(count,countlast)
mod=10**9+7

print((k*(k+1)*rcount+k*(k-1)*lcountlast)/2%mod)

Submission status: Runtime Error

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 = sum(cnt_minA_right) * K % (10**9+7)
ans += (sum(cnt_minA_all) * K % (10**9+7)

print(ans)

Submission status: Runtime Error

Solution code:
def bubble_sort(A):
    cnt = 0
    n = len(A)
    if n>1:
        A1 = A[:n>>1]
        A2 = A[n>>1:]
        cnt += mergecount(A1)
        cnt += mergecount(A2)
        i1=0
        i2=0
        for i in range(n):
            if i2 == len(A2):
                A[i] = A1[i1]
                i1 += 1
            elif i1 == len(A1):
                A[i] = A2[i2]
                i2 += 1
            elif A1[i1] <= A2[i2]:
                A[i] = A1[i1]
                i1 += 1
            else:
                A[i] = A2[i2]
                i2 += 1
                cnt += n//2 - i1
    return cnt

n,k=map(int, input().split())
a = list(map(int, input().split()))
b = list()
for i in range(0,k):
    for j in a:
      b.append(j)
print(bubble_sort(b) % (10**9+7))

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
A=list(map(int,input().split()))
S=[0 for j in range(2000)]
S2=[0 for j in range(2000)]
count=0

for i in range(N):
  S2[A[i]]+=1
  for j in range(A[i]):
    count+=S2[j]*(K-1)*K//2


for i in reversed(range(N)):
  S[A[i]]+=1
  for j in range(A[i]):
    count+=S[j]*K*(K+1)//2
print(count%(1000000007))

Submission status: Runtime Error

Solution code:
NandK = list(map(int,input().split()))
b = int(input())

n = NandK[0]
k = NandK[1]

l = []
while b > 0:
    l.append(b%10)
    b //= 10 # 必須
l.reverse()

l[len(l):len(l)] = l

print(l)

count_list = []
for i in range(len(l)):
    tmp = 0
    for j in range(i,len(l)):
        if l[i] > l[j]:
            tmp += 1
    count_list.append(tmp)

print(count_list)

count_list_N = count_list[3:]
count_list_N_1 = count_list[:3]
ans = 0
for kconunt in range(1, k+1): # k回やる
    for ix, a in enumerate(count_list_N):
        if a != 0:
            ans += a * kconunt
        elif count_list_N_1[ix] != 0:
            ans += count_list_N_1[ix] * kconunt
        else:
            pass
print(ans)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
a = [x for x in input().split()]

def mergecount(A):
    cnt = 0
    n = len(A)
    if n>1:
        A1 = A[:n>>1]
        A2 = A[n>>1:]
        cnt += mergecount(A1)
        cnt += mergecount(A2)
        i1=0
        i2=0
        for i in range(n):
            if i2 == len(A2):
                A[i] = A1[i1]
                i1 += 1
            elif i1 == len(A1):
                A[i] = A2[i2]
                i2 += 1
            elif A1[i1] <= A2[i2]:
                A[i] = A1[i1]
                i1 += 1
            else:
                A[i] = A2[i2]
                i2 += 1
                cnt += n//2 - i1
    return cnt

print((k * (k-1) * mergecount(a) + (k-1) * (k-2) * mergecount(a[::-1])) % 1000000007))

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,x)
    BIT_update(tree,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 = (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:
M, K = map(int, input().split())
list = [int(i) for i in input().split()]
t_list = [] 
count = 0
for i in range(K):
    for j in list :
        t_list.append(j)
t_list.reverse()
for i in range(K * len(list)):
    t_list = list(t_list)
    for j in t_list[i+1:]:
        if t_list[i] < j:
            t_list = set(t_list)
            count += 1
count = count % (10**9 + 7)
print(count)