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: Wrong Answer

Solution code:
# https://atcoder.jp/contests/jsc2019-qual/tasks/jsc2019_qual_b
# B - Kleene Inversion

import math

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

w = (10 ** 9) + 7
unit_c = 0

# 1個の中だと
for i, a in enumerate(a_list[:-1]):
    unit_c += len([x for x in a_list[i:] if x < a])

appendix = 0
# print(a_list[-1], a_list[0])
if len(a_list) > 1:
    for a in a_list:
        # 自分より小さいやつの数
        appendix += len([x for x in a_list if x < a])

# 2回以上繰り返す場合
# print('unit_c: {}'.format(unit_c))
# print('appendix: {}'.format(appendix))

# total_tento_1 = unit_c * (k-1)
if k-1 == 1:
    work = 1
elif (k-1) % 2 == 0:
    work = (1 + (k-1)) * ((k-1) / 2)
else:
    mid_index = math.floor((k-1) / 2) + 1
    work = (1 + (k-1)) * math.floor((k-1) / 2)
    work += mid_index

t_1 = (unit_c * k) % w
t_21 = appendix % w
t_22 = work % w
t_2 = (t_21 * t_22) % w
ans = int((t_1 + t_2) % w)

# ans = ((unit_c * k) + (appendix * work)) % w
# total_amari = int(total_tento % w)
print(ans)

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/jsc2019-qual/tasks/jsc2019_qual_b
# B - Kleene Inversion

import math

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

w = (10 ** 9) + 7
unit_c = 0

# 1個の中だと
for i, a in enumerate(a_list[:-1]):
    unit_c += len([x for x in a_list[i:] if x < a])

appendix = 0
# print(a_list[-1], a_list[0])
if len(a_list) > 1:
    for a in a_list:
        # 自分より小さいやつの数
        appendix += len([x for x in a_list if x < a])

# 2回以上繰り返す場合
# print('unit_c: {}'.format(unit_c))
# print('appendix: {}'.format(appendix))

# total_tento_1 = unit_c * (k-1)
if k-1 == 1:
    work = 1
elif (k-1) % 2 == 0:
    work = (1 + (k-1)) * ((k-1) / 2)
else:
    mid_index = math.floor((k-1) / 2) + 1
    work = (1 + (k-1)) * math.floor((k-1) / 2)
    work += mid_index

# t_1 = (unit_c * k) % w
# t_21 = appendix % w
# t_22 = work % w
# t_2 = (t_21 * t_22) % w
# total_amari = int((t_1 + t_2) % w)

ans = ((unit_c * k) + (appendix * work)) % w

ans = int(ans)
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
data = input().split(" ")
n = int(data[0])
k = int(data[1]) 
a = list(map(int, input().split(" ")))
print(a)
left = 0
right = 0
for i in range(0, n):
	for j in range(0, i):
		if a[j] < a[i]:
			left += 1
	for j in range(i+1, n):
		if a[j] < a[i]:
			right += 1

rt = ((k + 1) * k // 2) % 1000000007
lt = ((k - 1) * k // 2) % 1000000007
ans = (right * rt + left * lt) % 1000000007
print(ans)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = input().split()
 
MOD = 1000000007
p = 0  #同じブロック内での転倒数
q = 0  #異なる2つのブロック内での転倒数
  
#同じブロック内での転倒数を数え上げ
for i in range(n - 1):
  for j in range(i + 1, n):
    if int(a[i]) > int(a[j]):
      p += 1

#異なるブロック内での転倒数数え上げ      
for i in range(n):
  for j in range(n):
    if int(a[i]) > int(a[j]):
      q += 1
      
ans = ((p * k) % MOD + (q * k * (k - 1) /2) % MOD) % MOD
 
print(int(ans))

Submission status: Wrong Answer

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

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

print(ans)

Submission status: Wrong Answer

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

rn_0 , rn_2 = 0, 0

for i in range(n-1):
  for j in range(i+1, n):
    if l[i] > l[j]:
      rn_0 += 1

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

rn = rn_0 * k*(k+1)/2 + rn_2 * k*(k-1)/2
print(int(rn%(10**9+7)))

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A= list(map(int,input().split()))
a1 = 0
for i in range(len(A)):
  for j in range(len(A)):
    if (int(A[i]) > int(A[j])) and (j>i):
      a1 += 1
    else :
      a1 += 0
ak = K*(K + 1)*(a1)/2
print(int(ak%1000000007))

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
ans = 0
time_ans = 0
A_sort = sorted(A)
before = -1
b = -1
for i in range(N):
        a_sorti = A_sort[i]
        if a_sorti == before:
                time_ans += b
                continue
        b = A_sort.index(a_sorti)
        time_ans += b
        before = a_sorti

for i in range(N):
        for j in range(i + 1,N):
                if A[i] > A[j]:
                        ans += 1
ans1 = int((time_ans * K * (K - 1)) / 2) - K * (time_ans - ans)
print(ans1 % (10 ** 9 + 7))

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
ans = 0
time_ans = 0
A_sort = sorted(A)
before = -1
b = -1
for i in range(N):
        a_sorti = A_sort[i]
        if a_sorti == before:
                time_ans += b
                continue
        b = A_sort.index(a_sorti)
        time_ans += b
        before = a_sorti

for i in range(N):
        for j in range(i + 1,N):
                if A[i] > A[j]:
                        ans += 1
ans1 = int((time_ans * K * (K + 1)) / 2) - K * (time_ans - ans)
print(ans1 % (10 ** 9 + 7))

Submission status: Wrong Answer

Solution code:
N,K = map(int, input().split())
A = list(map(int,input().split()))
 
def souwa(num):
    if num % 2 == 0:
        return int((num+1) * (num/2))
    else:
        return int((num+1) * (num//2)) + ((num//2)+1)
 
ans = 0
for i in range(N):
    buf1 = sum(A[i] > A[j] for j in range(i+1, N))
    buf2 = sum(A[i] > a for a in A)
    ans += (buf1 * K) + (buf2 * (souwa(K-1)))
 
print(ans % (10**9+7))

Submission status: Wrong Answer

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

rn_0 , rn_2 = 0, 0

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

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

rn = rn_0 * k*(k-1)/2 + rn_2 * k*(k+1)/2
print(int(rn%(10**9+7)))

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
ans = 0
time_ans = 0
A_sort = sorted(A)
before = -1
b = -1
for i in range(N):
        a_sorti = A_sort[i]
        if a_sorti == before:
                time_ans += b
                continue
        b = A_sort.index(a_sorti)
        time_ans += b
        before = a_sorti

for i in range(N):
        for j in range(i + 1,N):
                if A[i] > A[j]:
                        ans += 1
ans1 = int((time_ans * K * (K + 1)) // 2) - K * (time_ans - ans)
if K >= 10:
        ans1 += ans
print(ans1 % (10 ** 9 + 7))

Submission status: Wrong Answer

Solution code:
import copy

def j(n):
    if n:print("Yes")
    else:print("No")
    exit(0)
rem = 10 ** 9 + 7

"""
def ct(x,y):
    if (x>y):print("+")
    elif (x<y): print("-")
    else: print("?")
"""

def ip():
    return int(input())
def iprow():
    return [int(i) for i in input().split()]
def ips():
    return (int(i) for i in input().split())
def printrow(a):
    for i in a:
        print(i)
s = 0
n,k =ips()
a = iprow()
for i in a[:-1]:
    for m in a[1:]:
        if i>m:s+=1
adder = 0
rate = s
ans = 0
print(rate)
ans = ((k * (k-1))*rate)//2
print(ans%rem)

Submission status: Wrong Answer

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

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

print(ans)

Submission status: Wrong Answer

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

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

print(int(ans))

Submission status: Wrong Answer

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

a1 = 0
a2 = 0

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

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

a1 = (a1 * K) % MOD

tmp = (K * (K - 1)) / 2
a2 = tmp * a2

ans = (a1 + a2) % MOD

print(int(ans))

Submission status: Wrong Answer

Solution code:
import math, string, itertools, fractions, heapq, collections, re, \
array, bisect, sys, random, time, copy, functools, os, queue, pdb
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)

N, K = LI()
A = LI()

"""
2 1なら
2 1 2 1
点灯数は、左の数のほうが多いもの
2 1
2 1
2 1
の3種類
2回つなげてみたら決まる
2 1 2 1なら
K = 2で3
K=3 で 2 1 2 1 2 1で6
K=4 で2 1 2 1 2 1 2 1で10通り 4+3+2+1=
K=6なら 2 1 2 1 2 1 2 1 2 1 2 1で6+5+4+3+2+1 =

偶奇でわける
modで割る

1 2なら
1 2 1 2で1しかない1
1 2 1 2 1 2なら3で2 + 1
1 2 1 2 1 2 1 2 なら6で3+2+1
"""
if len(set(A)) == 1:
    print(0)
    exit()

"""
各数字ごとに数える
"""
K %= mod
in_count = 0
for i in range(N):
    for j in range(i, N):
        if A[i] > A[j]:
            #  print('i, j', i,j, A[i], A[j])
            in_count += 1
#  print(in_count)
in_count %= mod
in_ans = in_count * K
in_ans %= mod

out_count = 0
for i in range(N):
    for j in range(N):
        if A[i] > A[j]:
            out_count += 1
#  print(out_count)

out_count %= mod
#  out_ans = (out_count * K * (K-1))//2
out_ans = out_count * (((K * (K-1))%mod)/2) % mod
out_ans %= mod
#  print(in_ans, out_ans)
print(int((in_ans + out_ans)%mod))

Submission status: Wrong Answer

Solution code:
import math, string, itertools, fractions, heapq, collections, re, \
array, bisect, sys, random, time, copy, functools, os, queue, pdb
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)

N, K = LI()
A = LI()

"""
2 1なら
2 1 2 1
点灯数は、左の数のほうが多いもの
2 1
2 1
2 1
の3種類
2回つなげてみたら決まる
2 1 2 1なら
K = 2で3
K=3 で 2 1 2 1 2 1で6
K=4 で2 1 2 1 2 1 2 1で10通り 4+3+2+1=
K=6なら 2 1 2 1 2 1 2 1 2 1 2 1で6+5+4+3+2+1 =

偶奇でわける
modで割る

1 2なら
1 2 1 2で1しかない1
1 2 1 2 1 2なら3で2 + 1
1 2 1 2 1 2 1 2 なら6で3+2+1
"""
if len(set(A)) == 1:
    print(0)
    exit()

"""
各数字ごとに数える
"""
K %= mod
in_count = 0
for i in range(N):
    for j in range(i, N):
        if A[i] > A[j]:
            #  print('i, j', i,j, A[i], A[j])
            in_count += 1
#  print(in_count)
in_count %= mod
in_ans = in_count * K
in_ans %= mod

out_count = 0
for i in range(N):
    for j in range(N):
        if A[i] > A[j]:
            out_count += 1
#  print(out_count)

out_count %= mod
#  out_ans = (out_count * K * (K-1))//2
out_ans = out_count * ((K * (K-1))%mod)/2
out_ans %= mod
#  print(in_ans, out_ans)
print(int((in_ans + out_ans)%mod))

Submission status: Wrong Answer

Solution code:
# coding: utf-8

import sys
import math
import collections
import itertools
from decimal import *
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, N) :
        if a > A[aa] :
            ans += 1

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

ans = (ans * K) % MOD
ans += (tmp * (Decimal((K * (K - 1)) % MOD) / Decimal(2))) % MOD
ans %= MOD

print(int(ans))

Submission status: Wrong Answer

Solution code:
import math, string, itertools, fractions, heapq, collections, re, \
array, bisect, sys, random, time, copy, functools, os, queue, pdb
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)

N, K = LI()
A = LI()

"""
2 1なら
2 1 2 1
点灯数は、左の数のほうが多いもの
2 1
2 1
2 1
の3種類
2回つなげてみたら決まる
2 1 2 1なら
K = 2で3
K=3 で 2 1 2 1 2 1で6
K=4 で2 1 2 1 2 1 2 1で10通り 4+3+2+1=
K=6なら 2 1 2 1 2 1 2 1 2 1 2 1で6+5+4+3+2+1 =

偶奇でわける
modで割る

1 2なら
1 2 1 2で1しかない1
1 2 1 2 1 2なら3で2 + 1
1 2 1 2 1 2 1 2 なら6で3+2+1
"""
if len(set(A)) == 1:
    print(0)
    exit()

"""
各数字ごとに数える
"""
K %= mod
in_count = 0
for i in range(N):
    for j in range(i, N):
        if A[i] > A[j]:
            #  print('i, j', i,j, A[i], A[j])
            in_count += 1
#  print(in_count)
in_count %= mod
in_ans = in_count * K
in_ans %= mod

out_count = 0
for i in range(N):
    for j in range(N):
        if A[i] > A[j]:
            out_count += 1
#  print(out_count)

out_count %= mod
#  out_ans = (out_count * K * (K-1))//2
out_ans = out_count * int(((K * (K-1))%mod/2))
out_ans %= mod
#  print(in_ans, out_ans)
print(int((in_ans + out_ans)%mod))

Submission status: Wrong Answer

Solution code:
import math, string, itertools, fractions, heapq, collections, re, \
array, bisect, sys, random, time, copy, functools, os, queue, pdb
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)

N, K = LI()
A = LI()

"""
2 1なら
2 1 2 1
点灯数は、左の数のほうが多いもの
2 1
2 1
2 1
の3種類
2回つなげてみたら決まる
2 1 2 1なら
K = 2で3
K=3 で 2 1 2 1 2 1で6
K=4 で2 1 2 1 2 1 2 1で10通り 4+3+2+1=
K=6なら 2 1 2 1 2 1 2 1 2 1 2 1で6+5+4+3+2+1 =

偶奇でわける
modで割る

1 2なら
1 2 1 2で1しかない1
1 2 1 2 1 2なら3で2 + 1
1 2 1 2 1 2 1 2 なら6で3+2+1
"""
if len(set(A)) == 1:
    print(0)
    exit()

"""
各数字ごとに数える
"""
K %= mod
in_count = 0
for i in range(N):
    for j in range(i, N):
        if A[i] > A[j]:
            #  print('i, j', i,j, A[i], A[j])
            in_count += 1
#  print(in_count)
in_count %= mod
in_ans = in_count * K
in_ans %= mod

out_count = 0
for i in range(N):
    for j in range(N):
        if A[i] > A[j]:
            out_count += 1
#  print(out_count)

out_count %= mod
#  out_ans = (out_count * K * (K-1))//2
out_ans = out_count * int(((K * (K-1))/2))
out_ans %= mod
#  print(in_ans, out_ans)
print(int((in_ans + out_ans)%mod))

Submission status: Wrong Answer

Solution code:
import math, string, itertools, fractions, heapq, collections, re, \
array, bisect, sys, random, time, copy, functools, os, queue, pdb
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)

N, K = LI()
A = LI()

"""
2 1なら
2 1 2 1
点灯数は、左の数のほうが多いもの
2 1
2 1
2 1
の3種類
2回つなげてみたら決まる
2 1 2 1なら
K = 2で3
K=3 で 2 1 2 1 2 1で6
K=4 で2 1 2 1 2 1 2 1で10通り 4+3+2+1=
K=6なら 2 1 2 1 2 1 2 1 2 1 2 1で6+5+4+3+2+1 =

偶奇でわける
modで割る

1 2なら
1 2 1 2で1しかない1
1 2 1 2 1 2なら3で2 + 1
1 2 1 2 1 2 1 2 なら6で3+2+1
"""
if len(set(A)) == 1:
    print(0)
    exit()

"""
各数字ごとに数える
"""
K %= mod
in_count = 0
for i in range(N):
    for j in range(i, N):
        if A[i] > A[j]:
            #  print('i, j', i,j, A[i], A[j])
            in_count += 1
#  print(in_count)
in_count %= mod
in_ans = in_count * K
in_ans %= mod

out_count = 0
for i in range(N):
    for j in range(N):
        if A[i] > A[j]:
            out_count += 1
#  print(out_count)

out_count %= mod
#  out_ans = (out_count * K * (K-1))//2
out_ans = out_count *( (K * (K-1))/2)
out_ans %= mod
#  print(in_ans, out_ans)
print(int((in_ans + out_ans)%mod))

Submission status: Wrong Answer

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

num_a = 0
num_b = 0

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

for i in range(n-1):
    for j in range(n, 2*n):
        if b[j] < b[i]:
            num_b += 1

total = (k * num_a + int(((k*(k-1))/2)*num_b)) % 1000000007

if k == 1:
    print(num_a)
else:
    print(total)

Submission status: Wrong Answer

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

box_2=box*2
count_2=0
for i in range(0,n):
    for j in box_2[n:]:
        if box_2[i]>j:
            count_2 +=1

point=int(0.5*(k*(k-1)))
print((count_2*point+count*k)%(10**9+7))

Submission status: Wrong Answer

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: Wrong Answer

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, N) :
        if a > A[aa] :
            ans += 1

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

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

print(int(ans))

Submission status: Wrong Answer

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
output = (x * k) % 1000000007 + (y * k * (k - 1) // 2) % 1000000007
print(output % 1000000007)

Submission status: Wrong Answer

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

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

i=0
tentou=0
while i<n-1:
  j=i+1
  while j<n:
    if r[i]>r[j]:tentou+=1
    j=j+1
  i=i+1

tentou2=0
i=0
while i<n:
  j=0
  while j<n:
    if r[j]>r[i]:tentou2+=1
    j=j+1
  i=i+1

#print(tentou,tentou2)

temp1=(tentou*k)
temp2=(tentou2*k*(k-1)/2)
#print(k,temp1,temp2)

print(int((temp1+temp2)%(1000000007)))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

b = len(set(a))
y = b*(b-1)//2
           
ans = x*k + y*k*(k-1)//2
print(ans%(10**9+7))

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = input().split()
 
MOD = 1000000007
p = 0  #同じブロック内での転倒数
q = 0  #異なる2つのブロック内での転倒数

#同じブロック内での転倒数を数え上げ
for i in range(n - 1):
  for j in range(i + 1, n):
    if a[i] > a[j]:
      p += 1

#異なるブロック内での転倒数数え上げ      
for i in range(n):
  for j in range(n):
    if a[i] > a[j]:
      q += 1
      
ans = ((p * k) % MOD + (q * k * (k - 1) /2) % MOD) % MOD

print(int(ans))

Submission status: Wrong Answer

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

count = 0
for i in range(n):
    for j in range(n-i-1):
        jj = j+1+i
        if la[i] > la[jj]:
            count += 1

count2 = 0
laa = sorted(la)
for i in range(n):
    for j in range(n-i-1):
        jj = j+1+i
      
        if laa[i] < laa[jj]:
            count2 += 1

a = count * k
b = count2 * ((1/2)*(k-1)*k)
result = int(a%mod)+int(b%mod)

print(result%mod)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
def main():
    n, k = (int(i) for i in input().split())
    a = [int(i) for i in input().split()]
    MOD = 10**9 + 7
    ans = 0
    alpha = 0
    cur_min = a[-1]
    cur_l = [a[-1]]
    from bisect import bisect,insort
    for i in range(2,n+1):
        if a[n-i] <= cur_min:
            cur_min = a[n-i]
            cur_l.insert(0,a[n-i])
        else:
            in_idx = bisect(cur_l,a[n-i])
            cur_l.insert(in_idx,a[n-i])
            alpha += in_idx
    ans = ans + (alpha * k)%MOD

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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

count = 0
for i in range(n):
    for j in range(n-i-1):
        jj = j+1+i
        if la[i] > la[jj]:
            count += 1

count2 = 0
laa = sorted(la)
for i in range(n):
    for j in range(n-i-1):
        jj = j+1+i
      
        if laa[i] < laa[jj]:
            count2 += 1

a = (count%mod) * (k%mod)
b = (count2%mod) * (((1/2)*(k-1)*k)%mod)
result = int(a)+int(b)

print(result%mod)

Submission status: Wrong Answer

Solution code:
MOD = 1e+9 + 7
N, K = map(int, input().split())
Alist = list(map(int, input().split()))

cnt = 0
ans = 0
KK = ((K * (K-1)) // 2) % MOD
for i in range(N):
    for j in range(N):
        if i != j:
            if Alist[i] > Alist[j]:
                cnt += 1
ans = (cnt * KK)

Alist = Alist[::-1]
tmp = 0
for i in range(1, len(Alist)):
    for j in range(i):
        if Alist[i] > Alist[j]:
            tmp += 1

ans += (tmp * K)
ans = ans % MOD

print(int(ans))

Submission status: Wrong Answer

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)

count2=0

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

counted = k*count2 + sum(li)*k*(k-1)/2

ans = counted % (10**9+7)
print(int(ans))

Submission status: Wrong Answer

Solution code:
import numpy as np
N, K   = map(int, input().split())
A=np.array(list(map(int, input().split())))
right=[]
left=[]
for i in range(N):
    right.append(np.count_nonzero(A[i:] < A[i]))
    left.append(np.count_nonzero(A[:i] < A[i]))
ans=sum(right)*(K*(1+K)/2)+sum(left)*((K-1)*K/2)
print(ans%(10**9+7))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import numpy as np
N, K   = map(int, input().split())
A=np.array(list(map(int, input().split())))
right=[]
left=[]
for i in range(N):
    right.append(np.count_nonzero(A[i:] < A[i]))
    left.append(np.count_nonzero(A[:i] < A[i]))
ans=sum(right)*int(K*(1+K)/2)+sum(left)*int((K-1)*K/2)
print(ans%(10**9+7))

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
from functools import lru_cache

def main():
    count = 0

    n,k = map(int, input().split(' '))
    a = [i for i in map(int, input().split(' '))]

    for i in range(len(a)):
        for j in range(len(a)):
            # print('--- ---', i,j)
            if i == j:
                continue
            if a[i] > a[j]:
                
                if i < j:
                    plus = int(k*(k+1)/2)
                    count += plus

                elif i > j:
                    plus = int(k*(k-1)/2)
                    count += plus

    count2 = 0
    for i in range(n):
        for j in range(i+1,n):
            if a[i] > a[j]:
                count2 += k
    
    aa = a.extend(a)

    for i in range(n):
        for j in range(n+1,2*n):
            if a[i] > a[j]:
                count2 += int(k*(k-1)/2)
        
        count2 = count2 % (10**9 + 7)
    # print(count%(10**9+7))
    print(count2)


            
                
    
    



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
MOD = 1e+9 + 7
N, K = map(int, input().split())
Alist = list(map(int, input().split()))

cnt = 0
ans = 0
KK = ((K * (K-1)) // 2) % MOD
for i in range(N):
    cnt = 0
    for j in range(N):
        if i != j:
            if Alist[i] > Alist[j]:
                cnt += 1
    ans += (cnt * KK) % MOD

Alist = Alist[::-1]
for i in range(1, len(Alist)):
    tmp = 0
    for j in range(i):
        if Alist[i] > Alist[j]:
            tmp += 1
    ans += (tmp * K) % MOD
ans = ans % MOD

print(int(ans))

Submission status: Wrong Answer

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

d0 = [0]*N
d1 = [0]*N
for i in range(N):
    d0[i] = sum(map(lambda x: x<A[i], A[i+1:N]))
    d1[i] = sum(map(lambda x: x<A[i], A))

ans = sum(d0)*(K)+sum(d1)*(K-1)*K/2
print(int(ans%MOD))