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:
mod = 10 ** 9 + 7
N, K = map(int, input().split())
A = list(map(int, input().split()))
def check(A):
    sum = 0
    for i, a in enumerate(A[:-1]):
        sum += sorted(A[i:]).index(a)
    return sum
 
if K <= 3:
    print(check(A*K))
else:
    sum = [check(A), check(A*2), check(A*3)]
    ans = sum[0] + ((sum[1]-sum[0])*(K-1)%mod) + (((sum[2]-sum[1])-(sum[1]-sum[0])) * int((K-2)*(0.5 + (K-2)*0.5)%mod)%mod)
    print(ans%mod)

Submission status: Wrong Answer

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

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

print(ans)

Submission status: Wrong Answer

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

#import
#import math
#import numpy as np
N, K = map(int, input().split())
A = list(map(int, input().split()))

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

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

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

print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
def check(A):
    sum = 0
    for i, a in enumerate(A[:-1]):
        sum += sorted(A[i:]).index(a)
    return sum

if K <= 3:
    print(check(A*K))
else:
    sum = [check(A), check(A*2), check(A*3)]
    ans = sum[0] + ((sum[1]-sum[0])*(K-1)) + (((sum[2]-sum[1])-(sum[1]-sum[0])) * int((K-2)*(0.5 + (K-2)*0.5)))
    print(ans%(10**9+7))

Submission status: Wrong Answer

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

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

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

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

print(ans)

Submission status: Wrong Answer

Solution code:
N , K = map(int,input().split())
A = list(map(int,input().split()))
mod = 10**9 + 7
Ao = 0
Ad = 0
for i in range(N):
  for j in range(N - i - 1):
    if A[i] > A[i + j + 1]:
      Ao += 1
  if i != 0:
    for j in range(i - 1):
      if A[i] > A[i - j - 1]:
        Ad +=1
ans = int(Ao*K*(K+1)//2)
ans %= mod
ans += int(Ad*K*(K-1)//2)
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
Ao = 0
Ad = 0
for i in range(N):
  for j in range(N - i - 1):
    if A[i] > A[i + j + 1]:
      Ao += 1
  if i != 0:
    for j in range(i - 1):
      if A[i] > A[i - j - 1]:
        Ad +=1
ans = Ao*K*(K+1)//2 + Ad*K*(K-1)//2
ans %= mod
print(int(ans))

Submission status: Wrong Answer

Solution code:
N , K = map(int,input().split())
A = list(map(int,input().split()))
mod = 1000000007
Ao = 0
Ad = 0
for i in range(N):
  for j in range(N - i - 1):
    if A[i] > A[i + j + 1]:
      Ao += 1
  if i != 0:
    for j in range(i - 1):
      if A[i] > A[i - j - 1]:
        Ad +=1
ans = Ao*K*(K+1)/2 + Ad*K*(K-1)/2
ans %= mod
print(int(ans))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
b = [[0,0] for _i in range(2001)]
for i in range(n):
    b[a[i]][0] += 1
    b[a[i]][1] += sum(j<a[i] for j in a[i:])
cnt, r = 0, 0
mod = 10**9+7
for i in sorted(set(a)):
    x = cnt*(k*(k+1)//2)%mod + ((b[i][1] - cnt)*k)%mod
    r = (r+x)%mod
    cnt += b[i][0]
print(r)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
b = [[0,0] for _i in range(2001)]
for i in range(n):
    b[a[i]][0] += 1
    b[a[i]][1] += sum(j<a[i] for j in a[i:])
cnt, r = 0, 0
mod = 10**9+7
for i in sorted(set(a)):
    x = b[i][0]*(cnt*(k*(k+1)//2)%mod)%mod + ((b[i][1] - cnt)*k)%mod
    r = (r+x)%mod
    cnt += b[i][0]
print(r)

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n, k = map(int,input().split())
A = list(map(int,input().split()))
B = [1]*n
N = len(set(A))

for i in range(n):
    chk = 0
    for j in range(n):
        if A[i] < A[j]:
            chk += 1
    B[i] += chk

ans = 0
for i in range(n):
    chk = 0
    for j in range(i-1,-1,-1):
        if B[i] > B[j]:
            chk += 1
    ans += chk * k
ans += k * (k - 1)*N*(N - 1)//4
print(ans % (10**9 + 7))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
mod=10**9+7

n,k = map(int,input().split())
l = list(map(int,input().split()))
l2 = l+l

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

y=0
for i in range(2*n-1):
    for j in range(i+1,2*n):
        if l2[i] > l2[j]:
            y+=1
y-=(x*k)

for i in range(k-1):
    y = (y*(1+i))%mod

print((y + (x*k)%mod)%mod)

Submission status: Wrong Answer

Solution code:
import sys, math
from functools import lru_cache
from collections import defaultdict
sys.setrecursionlimit(500000)
MOD = 10**9+7

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

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

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]

def main():
    N, K = mi()
    A = list(mi())
    c = 0
    d = 0

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

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

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

if k%2 == 0:
    print((k+1)*(k//2)*cnt%(10**9+7))
else:
    print((((k//2)*(k+1)+((k+1)//2))*cnt)%(10**9+7))

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = int(1e9 + 7)
cnt_a = [0] * 2005
for i in a:
    cnt_a[i] += 1
less = 0
m = 0
for i in range(2005):
    if cnt_a[i] == 0:
        continue
    m += less
    less += cnt_a[i]
ans = 0
for i in range(n):
    cnt = 0
    for j in range(i):
        if a[j] > a[i]:
            cnt += 1
    ans += cnt * k % mod
ans += m * k * (k - 1) // 2 % mod
print(ans % mod)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = int(1e9 + 7)
cnt_a = [0] * 2005
for i in a:
    cnt_a[i] += 1
less = 0
m = 0
for i in cnt_a:
    if i == 0:
        continue
    m += less
    less += i
ans = 0
for i in range(n):
    cnt = 0
    for j in range(i):
        if a[j] > a[i]:
            cnt += 1
    ans += cnt * k % mod
ans += m * k * (k - 1) // 2 % mod
print(ans % mod)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
count = 0
b, c = [], []

for i in range(n):
    count1, count2 = 0, 0
    for j in range(n):
        if a[i] > a[j] and i < j:
            count1 += 1
        elif a[i] > a[j] and i > j:
            count2 += 1
    b.append(count1)
    c.append(count2)

if k == 1:
    print(sum(b))
else:
    print(int(sum(b)*k*(k+1)/2+sum(c)*(k-1)*k/2)%(10**9+7))

Submission status: Wrong Answer

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

# K_seq_sum = int(K  * (K+1) / 2) - K
K_seq_sum = int(K  * (K+1) / 2)
# print(K_seq_sum)
# その中での転倒数と
# 自分より低い数を持っておく
inv_num_in_original_list = []
inv_num_all_list = []
diff_lst = []
res = 0
for n1, a1 in enumerate(A_list):
    cnt1 = 0
    cnt2 = 0
    for n2, a2 in enumerate(A_list):
        if a1 > a2:
            cnt2 += 1
            if n1 < n2:
                cnt1 += 1
    inv_num_in_original_list.append(cnt1)
    inv_num_all_list.append(cnt2)
    diff = cnt2 - cnt1
    diff_lst.append(cnt2 - cnt1)
    # a1から見たときの数を出す
    # (自分のリストの中での転倒の数 * K回) + (自分より左のリストとの転倒数)
    # res_tmp = cnt1 * K + cnt2 * K_seq_sum
    # res += res_tmp 
    res_tmp = cnt2 * K_seq_sum - diff * K
    res += res_tmp 
    res = int(res % (1e9 + 7))
# print(inv_num_in_original_list)
# print(inv_num_all_list)
# print(diff_lst)
print(res)

Submission status: Wrong Answer

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

ans = 0

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

Submission status: Wrong Answer

Solution code:
# A内で完結するものと、連結したときに変わるものがある
#
# 3 4 2 1 2 -> 3+3+1+0+0 = 7
# 3 4 2 1 2 | 3 4 2 1 2 -> (3*2)+(1*1+3*2)+(1*2)+0+(1*1) + 7 = 16 + 7
# 3 4 2 1 2 | 3 4 2 1 2 | 3 4 2 1 2 -> (3*3)+(2*1+3*3)+(1*3)+0+(2*1) + 16+7 = 25+16+7
# この公差9は Aについて、i<jなるjでAi>Ajになるものがk個、Ai<Ajになるものがk-1個あることから、それぞれの数を合わせたもの
# ということで、それぞれ等差数列の和が使えそう
n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = 10**9 + 7

# 順方向
base = 0
for i in range(n):
    for j in range(i, n):
        if a[i] > a[j]:
            base += 1
# 逆方向
additional = 0
for i in range(n):
    for j in range(i):
        if a[i] > a[j]:
            additional += 1
# 公差を使った等差数列の和
# ans = k * (2 * base + (k - 1) * (base + additional) % mod) // 2 % mod
# なぜか上記だとWAになるので（意味不明）末項を使ったもので求めてみる
x = base + (base + additional) * (k - 1)
ans = k * ((base + x) % mod) // 2 % mod
print(ans % mod)

Submission status: Wrong Answer

Solution code:
# A内で完結するものと、連結したときに変わるものがある
#
# 3 4 2 1 2 -> 3+3+1+0+0 = 7
# 3 4 2 1 2 | 3 4 2 1 2 -> (3*2)+(1*1+3*2)+(1*2)+0+(1*1) + 7 = 16 + 7
# 3 4 2 1 2 | 3 4 2 1 2 | 3 4 2 1 2 -> (3*3)+(2*1+3*3)+(1*3)+0+(2*1) + 16+7 = 25+16+7
# この公差9は Aについて、i<jなるjでAi>Ajになるものがk個、Ai<Ajになるものがk-1個あることから、それぞれの数を合わせたもの
# ということで、それぞれ等差数列の和が使えそう
n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = 10**9 + 7

# 順方向
base = 0
for i in range(n):
    for j in range(i, n):
        if a[i] > a[j]:
            base += 1
# 逆方向
additional = 0
for i in range(n):
    for j in range(i):
        if a[i] > a[j]:
            additional += 1
# 公差を使った等差数列の和
# ans = k * (2 * base + (k - 1) * (base + additional) % mod) // 2 % mod
# なぜか上記だとWAになるので（意味不明）末項を使ったもので求めてみる
x = base + (base + additional) * (k - 1)
ans = k * ((base + x) % mod) // 2 % mod
print(ans)

Submission status: Wrong Answer

Solution code:
# A内で完結するものと、連結したときに変わるものがある
#
# 3 4 2 1 2 -> 3+3+1+0+0 = 7
# 3 4 2 1 2 | 3 4 2 1 2 -> (3*2)+(1*1+3*2)+(1*2)+0+(1*1) + 7 = 16 + 7
# 3 4 2 1 2 | 3 4 2 1 2 | 3 4 2 1 2 -> (3*3)+(2*1+3*3)+(1*3)+0+(2*1) + 16+7 = 25+16+7
# この公差9は Aについて、i<jなるjでAi>Ajになるものがk個、Ai<Ajになるものがk-1個あることから、それぞれの数を合わせたもの
# ということで、それぞれ等差数列の和が使えそう
n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = 10**9 + 7

# 順方向
base = 0
for i in range(n):
    for j in range(i, n):
        if a[i] > a[j]:
            base += 1
# 逆方向
additional = 0
for i in range(n):
    for j in range(i):
        if a[i] > a[j]:
            additional += 1
# 公差を使った等差数列の和
ans = k * (2 * base + (k - 1) * (base + additional) % mod) // 2 % mod
print(ans)

Submission status: Wrong Answer

Solution code:
# A内で完結するものと、連結したときに変わるものがある
#
# 3 4 2 1 2 -> 3+3+1+0+0 = 7
# 3 4 2 1 2 | 3 4 2 1 2 -> (3*2)+(1*1+3*2)+(1*2)+0+(1*1) + 7 = 16 + 7
# 3 4 2 1 2 | 3 4 2 1 2 | 3 4 2 1 2 -> (3*3)+(2*1+3*3)+(1*3)+0+(2*1) + 16+7 = 25+16+7
# Aについて、i<jなるjでAi>Ajになるものがk個、Ai<Ajになるものがk-1個ある
# k=3で考えると
# 順方向: (m*3)+(m*3)+(m*1)+(0)+(0), m=1~3 = 7+14+21=42
# 逆方向：(0)+(m*1)+(0)+(0)+(m*1), m=1~2 = 2+4=6 （逆方向はk-1個）
# 合わせて48となりこれは上記で試してたのと等しい
# ということで、それぞれ等差数列の和が使えそう
n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = 10**9 + 7

# 順方向
base = 0
for i in range(n):
    for j in range(i, n):
        if a[i] > a[j]:
            base += 1
# 逆方向
additional = 0
for i in range(n):
    for j in range(i):
        if a[i] > a[j]:
            additional += 1
print(base, additional)
ans = (k * (k + 1) // 2 % mod * base +
       (k - 1) * k // 2 % mod * additional) % mod
print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A_LIST = list(map(int, input().split()))
MOD = 10 ** 9 + 7
t = 0
tr = 0
ans = 0
for i in range(N):
    for j in range(i + 1, N):
        if A_LIST[i] > A_LIST[j]:
            t += 1
    for j in range(N):
        if A_LIST[i] > A_LIST[j]:
            tr += 1
ans += t * K % MOD
ans += tr * (K - 1) * K % MOD
print(ans % MOD)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A_LIST = list(map(int, input().split()))
INF = 10 ** 9 + 7
t = 0
for i in range(N - 1):
    for j in range(i + 1, N):
        if A_LIST[i] > A_LIST[j]:
            t += 1
ans = (t * K) % INF
A_SET_LIST = sorted(set(A_LIST))
t = sum(range(len(A_SET_LIST)))
ans += t * (K - 1) * K // 2 % INF
print(ans % INF)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A_LIST = list(map(int, input().split()))
INF = 10 ** 9 + 7
t = 0
for i in range(N - 1):
    for j in range(i + 1, N):
        if A_LIST[i] > A_LIST[j]:
            t += 1
A_SET_LIST = sorted(set(A_LIST))
tr = sum(range(len(A_SET_LIST)))
total = (t * K % INF) + (tr * (K - 1) * K // 2 % INF)
print(total % INF)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A_LIST = list(map(int, input().split()))
INF = 10 ** 9 + 7
t = 0
for i in range(N - 1):
    for j in range(i + 1, N):
        if A_LIST[i] > A_LIST[j]:
            t += 1
A_SET_LIST = sorted(set(A_LIST))
tr = sum(range(len(A_SET_LIST)))
total = t * K + tr * (K - 1) * K // 2
print(total % INF)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
import itertools


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

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

    M = 10**9 + 7
    # オーバーフロー対策で掛け算毎に剰余をとる
    a = cntA * K % M
    b = int((K - 1) * K / 2) % M * cntB % M
    print((a + b) % M)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import itertools


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

    ### BIT ###
    # bit = [0] * (N + 1)

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

    # def add(i, x):
    #     while i <= N:
    #         bit[i] += x
    #         i += i & -i
    #         print(i, bit)

    # ans = 0
    # for i in range(N):
    #     ans += i - sum(A[i])
    #     add(A[i], 1)
    # print(ans)

    cnt = 0
    while A != sorted(A):
        for i in range(N - 1):
            if A[i] > A[i + 1]:
                A[i], A[i + 1] = A[i + 1], A[i]
                cnt += 1
            # print(cnt, A)

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

    M = 10**9 + 7
    # オーバーフロー対策で掛け算毎に剰余をとる
    a = cnt * K % M
    b = int((K - 1) * K / 2) % M * d % M
    print((a + b) % M)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

mod = 10**9+7

n,k = nm()
a=nl()
b=[]
for i in range(k):
  b.extend(a)

ans=0

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

Submission status: Wrong Answer

Solution code:
from operator import mul
from functools import reduce

def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


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

#Aの内部での転倒数を計算
tot1=0
for i in range(len(A)):
    tot1+=len([j for j in A[i+1:] if j<A[i]])%(10**9+7)

#Aの外部での転倒数を計算
n=len(set(A))
tot2=int(0.5*(n-1)*n%(10**9+7))
ans=K*tot1+combinations_count(K, 2)*tot2
print(ans)

Submission status: Wrong Answer

Solution code:
from operator import mul
from functools import reduce

def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


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

#Aの内部での転倒数を計算
tot1=0
for i in range(len(A)):
    tot1+=len([j for j in A[i+1:] if j<A[i]])

#Aの外部での転倒数を計算
n=len(set(A))
tot2=int(0.5*(n-1)*n)
ans=K*tot1+combinations_count(K, 2)*tot2
print(ans%(10**9+7))

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
mod = 1000000007
ans = 0
list = [[0,0] for i in range(N)]
I = 0
J = 0
for i in range(N):
  for j in range(i):
    if A[j] < A[i]:
      list[i][0] += 1
      I += 1
      J += 1
  for k in range(i+1,N):
    if A[k] < A[i]:
      list[i][1] += 1
      J += 1
#print(list)
for i in range(N):
  ans += K*list[i][1] + K*(K-1)*(list[i][0]+list[i][1])/2                     
print(int(ans%mod))

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
mod = 1000000007
ans = 0
list = [[0,0] for i in range(N)]
I = 0
J = 0
for i in range(N):
  for j in range(i):
    if A[j] < A[i]:
      list[i][0] += 1
      I += 1
      J += 1
  for k in range(i+1,N):
    if A[k] < A[i]:
      list[i][1] += 1
      J += 1
#print(list)
for i in range(N):
  ans += K*list[i][1] + K*(K-1)*(list[i][0]+list[i][1])/2                     
print(ans%mod)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
mod = 1000000007
ans = 0
list = [[0,0] for i in range(N)]
I = 0
J = 0
for i in range(N):
  for j in range(i):
    if A[j] < A[i]:
      list[i][0] += 1
      I += 1
      J += 1
  for k in range(i+1,N):
    if A[k] < A[i]:
      list[i][1] += 1
      J += 1
print(list)
for i in range(N):
  ans += int(K*list[i][1] + K*(K-1)*(list[i][0]+list[i][1])//2)                      
print(ans%mod)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
mod = 10**9+7
ans = 0
list = [[0,0] for i in range(N)]

for i in range(N):
  for j in range(i):
    if A[j] < A[i]:
      list[i][0] += 1
  for k in range(i+1,N):
    if A[k] < A[i]:
      list[i][1] += 1
#print(list)
for i in range(N):
  ans += int(K*list[i][1] + K*(K-1)*(sum(list[i]))/2)
  ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
import math
import sys


def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def S(): return input()
def LS(): return input().split()


INF = float('inf')
MOD = 10 ** 9 + 7


n, k = LI()
a = LI()
base = 0
for i in range(n):
    cnt = 0
    for j in range(i + 1, n):
        if a[i] > a[j]:
            base += 1
            cnt += 1
    # print(a[i], cnt)

# print(base)
k_sum = k * (k + 1) // 2
# print(k_sum)
ans = (base * k_sum) % MOD
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
import math
import sys


def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def S(): return input()
def LS(): return input().split()


INF = float('inf')
MOD = 10 ** 9 + 7


def calc_cumsum(l):
    cumsum = [0]
    for i in l:
        cumsum.append(cumsum[-1] + i)
    return cumsum


n, k = LI()
a = LI()
a.sort()
a = a[::-1]
c = list(Counter(a).items())
counts = [cnt for _, cnt in c]
cumsum_count = calc_cumsum(counts)[::-1][1:-1]
# print(cumsum_count)
# print(c)
base = 0
for i, (num, cnt) in enumerate(c):
    if i == len(c) - 1:
        break
    # print(num, cnt)
    base += cumsum_count[i] * cnt
# print(base)
fact = math.factorial(k)
fact %= MOD
ans = base * fact
print(ans)

Submission status: Wrong Answer

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

ans_mono=0
ans_di=0
for i in range(n):
    for j in range(i+1,n):
        if a[i]>a[j]:ans_mono+=1
for i in range(n):
    for j in range(n):
        if a[i]>a[j]:ans_di+=1
print(int((ans_mono*k+ans_di*(k*(k-1)//2))%(1e+9+7)))

Submission status: Wrong Answer

Solution code:
MOD = 10 ** 9 + 7

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

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

Submission status: Wrong Answer

Solution code:
import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n,k=mp()
a=lmp()
cnt=0
for i in range(n-1):
    for j in range(i+1,n):
        if a[i]>a[j]:
            cnt+=1
m=len(set(a))
print((cnt*k+(m-1)*m*k*(k-1)//4)%(10**9+7))

Submission status: Wrong Answer

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

memo = [0]*N
tmp = [0]*(2002)
sm = [0]*(2002)

for i in range(N):
  for j in range(As[i]+1,2000):
    memo[i] += tmp[j]
  tmp[As[i]] += 1
  
for i in range(2000, 0, -1):
  sm[i] += sm[i+1] + tmp[i]
  
rlt = 0

for i in range(N):
  rlt += (K*(K-1)*sm[As[i]+1]//2 + K*memo[i]) % P
  rlt %= P
  
print(rlt)

Submission status: Wrong Answer

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

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

cnt2 = 0
c = 0
i = 0
c_n = a[0]
while True:
    cnt = 0
    while a[i + cnt] == c_n:
        cnt +=1
        if i + cnt == n:
            break
    cnt2 += cnt*c
    c += cnt
    i += cnt
    if i == n:
        break
    c_n = a[i]

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

Submission status: Wrong Answer

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

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

a.sort()           
cnt2 = 0
c = 0
i = 0
c_n = a[0]
while True:
    cnt = 0
    while a[i + cnt] == c_n:
        cnt +=1
        if i + cnt == n:
            break
    cnt2 += cnt*c
    c += 1
    i += cnt
    if i == n:
        break
    c_n = a[i]

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

Submission status: Wrong Answer

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

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

a.sort(reverse = True)           
cnt2 = 0
c = 0
i = 0
c_n = a[0]
while True:
    cnt = 0
    while a[i + cnt] == c_n:
        cnt +=1
        if i + cnt == n:
            break
    cnt2 += cnt*c
    c += 1
    i += cnt
    if i == n:
        break
    c_n = a[i]

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

Submission status: Wrong Answer

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import fractions
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

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

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

    return arr


# a^n
def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod


# n*(n-1)*...*(l+1)*l
def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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


inf = 10 ** 18
mod = 10 ** 9 + 7

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