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:
# 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-1):
    tmp = a[i]
    for j in range(i+1, 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)

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-1):
    tmp = a[i]
    for j in range(i+1, 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)//2)%mod
    ans%=mod
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict, deque, Counter
import math
 
# import copy
from bisect import bisect_left, bisect_right
# import heapq
 
# sys.setrecursionlimit(1000000)
 
# input aliases
input = sys.stdin.readline
 
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]
 
INF = 10 ** 20
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)
 
class Segtree_op():
     def __init__(self, n):
         self.size = 1
         while(n >= 1):
             self.size = self.size << 1
             n = n//2
 
         self.arr = [self.unit() for i in range(self.size*2)]
 
     def op(self, lch, rch):
         # update min with holding index
         return lch + rch
 
     def unit(self):
         return 0
 
     def update(self, k, val):
         k += self.size - 1
         self.arr[k] = val
         while(k):
             k = (k - 1) // 2
             self.arr[k] = self.op(self.arr[k*2 + 1], self.arr[k*2 + 2])
 
     def query(self, l, r):
         L = l + self.size
         R = r + self.size
         s = self.unit()
         while L < R:
             if R & 1:
                 R -= 1
                 s = self.op(s, self.arr[R - 1])
 
             if L & 1:
                 s = self.op(s, self.arr[L - 1])
                 L += 1
             L >>= 1
             R >>= 1
         return s
 
 
     def show(self):
         idx = 1
         while(idx <= self.size):
             print(self.arr[idx - 1:idx * 2 - 1])
             idx *= 2
def tento(nums):
    st = Segtree_op(max(nums))
    ret = 0
    for i, num in enumerate(nums):
        st.update(num, st.query(num, num+1)+1)
        # st.show()
        ret += i - st.query(0, num+1) + 1

    return ret



def main():
    n, kk = getList()
    nums = getList()
    ten = tento(nums)
    oneset = 0
    for k, v in Counter(nums).items():
        oneset += n - v
    # print(ten, oneset)
    print((kk * ten + kk * (kk-1) * oneset // 4)% MOD)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

ans = 0
mod = 10**9+7
for i in range(n):
    tento = 0
    t = a[i]
    for j in range(i+1, n):
        if t > a[j]:
            tento += 1
    ans += k*tento % mod
    ans += (k-1)*k*(t-1)//2 % mod
print(ans%mod)

Submission status: Wrong Answer

Solution code:
from collections import Counter

N, K = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7
A_sort = sorted(list(set(A)))
counter = Counter(A)
ans = 0
for i in range(len(A_sort)):
    if i == 0:
        continue
    else:
        ans += (i * (K * (K-1) // 2) * counter[A_sort[i]])  % MOD
        index = A.index(A_sort[i])
        cnt = 0
        p = 0
        for j in range(index, N):
            if A_sort[i] > A[j]:
                cnt += 1 * p
            elif A_sort[i] == A[j]:
                p += 1
        ans = (ans + (cnt * K)) % 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
A_sort = sorted(list(set(A)))
ans = 0
for i in range(len(A_sort)):
    if i == 0:
        continue
    else:
        ans += i * (K * (K-1) // 2) % MOD
        index = A.index(A_sort[i])
        cnt = 0
        for j in range(index, N):
            if A_sort[i] > A[j]:
                cnt += 1
        ans = (ans + (cnt * K)) % MOD
print(ans)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
A = list(map(int, input().split()))
mod = pow(10,9)+7
ans = 0
for i in range(n):
    ans += sum([bool(A[i]>A[j]) for j in range(i+1,n)])
print((ans*k+k*(k-1)//2*len(set(A))*(len(set(A))-1)//2)%mod)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
M = 10**9+7
from collections import defaultdict

d = defaultdict(int)

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

            if i < j:
                lcl_cnt += 1

print(((K*(lcl_cnt + K*lcl_cnt))//2)%M)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
#https://scrapbox.io/pocala-kyopro/B_-_Kleene_Inversion
MOD = 1000000007
N,K = map(int,input().split())
A = list(map(int, input().split()))
ans = 0
for i in range(N):
    migi = 0
    zentai = 0
    for j in range(i,N):
        if A[i] > A[j]:
            migi += 1
    for j in range(N):
        if A[i] > A[j]:
            zentai += 1
            
    ans += migi * K % MOD
    ans %= MOD
    ans += int((K-1)*K % MOD * zentai % MOD/2)
    ans %= MOD
print(ans)

Submission status: Wrong Answer

Solution code:
#https://scrapbox.io/pocala-kyopro/B_-_Kleene_Inversion
MOD = 1000000007
N,K = map(int,input().split())
A = list(map(int, input().split()))
ans = 0
for i in range(len(A)):
    migi = 0
    zentai = 0
    for j in range(i,len(A)):
        if A[i] > A[j]:
            migi += 1
    for j in range(len(A)):
        if A[i] > A[j]:
            zentai += 1
            
    ans += migi * K % MOD
    ans %= MOD
    ans += int((K-1)*K/2) % MOD * zentai % MOD
    ans %= MOD
print(ans)

Submission status: Wrong Answer

Solution code:

import itertools

def solve(A,K):
    """
    >>> solve([1,2,3])
    Yes
    """
    x = 0
    y = 0
    table = [0] * 2100

    for i in range(len(A)):
        for j in range(len(A)-1,i,-1):
            if A[j] < A[j-1]:
                A[j],A[j-1] = A[j-1],A[j]
                y += 1

    for i in range(len(A)):
        table[A[i]] += 1
        
    
    table[len(A)+1] = len(A)
    for i in range(len(A),0,-1):
        x += table[i] - table[i-1]
        x %= 1000000007

    ans = 0
    ans += int((K*(K-1)*x)/2)
    ans %= 1000000007
    ans += y * K
    ans %= 1000000007

    print(ans)

def main():
    N,K = map(int,input().split())
    A = list(map(int, input().split()))
    solve(A,K)


def _test():
    import doctest
    doctest.testmod()


if __name__ == "__main__":
    import sys
    argv = sys.argv
    if len(sys.argv) == 1:
        # no option
        main()
    elif sys.argv[1] == "-t":
        _test()
    else:
        input = open(sys.argv[1]).buffer.readline

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
A=[int(i) for i in input().split()]
MOD = 10**9 + 7

def tent(a):
    t = len(a)
    res = 0
    for i in range(t-1):
        for j in range(i+1,t):
            if(a[i]>a[j]):
                res+=1
    return res
t1 = tent(A)
t2 = tent(A+A)-2*t1
ans = (t1*k%MOD + t2*(k*(k-1)%MOD)//2)%MOD
print(ans)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = [int(x) for x in input().split()]
b = [sorted(a).index(a[i]) for i in range(n)]
p = [b[i] * (k*(k+1)//2)for i in range(n)]
q = [0] * n
for i in range(n):
    num = 0
    for j in range(i,n):
        if a[j] > a[i]:
            num += 1
    q[i] = num

print(sum(p)-sum(q)*k)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

n,k = map(int,input().split())
a = list(map(int,input().split()))
mod = 10**9 + 7
d = defaultdict(int)

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

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

x = ((t)*(k)*(k-1)/2)%mod
y = (inner*k)%mod
print(int((x+y)%mod))

Submission status: Wrong Answer

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

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

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

x = ((t)*(k)*(k-1)/2)%mod
y = (c*k)%mod
print(int((x+y)%mod))

Submission status: Wrong Answer

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

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

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

ans = (t)*(k)*(k-1)/2
print(int((ans+c*k)%mod))

Submission status: Wrong Answer

Solution code:
N,K = map(int, input().split())
A = list(map(int,input().split()))
t = 0
for i in range(N-1):
  for j in range(N-i-1):
    if A[i] > A[j+i+1]:
      t += 1
u = 0
for i in range(N):
  for j in range(N):
    if A[i]>A[j]:
      u += 1
T = t%(10**9+7)
U = u%(10**9+7)
Z=K*(K-1)/2%(10**9+7)
Y=T*K%(10**9+7)
X=U*Z%(10**9+7)
ans = int((Y+X)%(10**9+7))
   
print(ans)

Submission status: Wrong Answer

Solution code:
N,K = map(int, input().split())
A = list(map(int,input().split()))
t = 0
for i in range(N):
  for j in range(N-i-1):
    if A[i] > A[j+i+1]:
      t += 1
u = 0
for i in range(N):
  for j in range(N):
    if A[i]>A[j]:
      u += 1
T = t%(10**9+7)
U = u%(10**9+7)
Z=K*(K-1)/2%(10**9+7)
Y=T*K%(10**9+7)
X=U*Z%(10**9+7)
ans = int((Y+X)%(10**9+7))
   
print(ans)

Submission status: Wrong Answer

Solution code:
N,K = map(int, input().split())
A = list(map(int,input().split()))
t = 0
for i in range(N):
  for j in range(N-i-1):
    if A[i] > A[j+i+1]:
      t += 1
T = t%(10**9+7)
u = 0
for i in range(N):
  for j in range(N):
    if A[i]>A[j]:
      u += 1
U = u%(10**9+7)
Z=K*(K-1)/2%(10**9+7)
ans = int((T*K+U*Z)%(10**9+7))
   
print(ans)

Submission status: Wrong Answer

Solution code:
N,K = map(int, input().split())
A = list(map(int,input().split()))
t = 0
for i in range(N):
  for j in range(N-i-1):
    if A[i] > A[j+i+1]:
      t += 1
T = t
u = 0
for i in range(N):
  for j in range(N):
    if A[i]>A[j]:
      u += 1
U = u
ans = int((T*K+U*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()))

A_cnt = [0] * (max(A)+1)
ans = 0
tmp = 0

def pow_k(x, n):
    """
    O(log n)
    """
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2

    return K * x

for i in reversed(range(N)):
    A_cnt[A[i]] += 1
    tmp += sum(A_cnt[:A[i]])

for i in A:
    ans += pow_k(sum(A_cnt[:i]), (K-1))

print((ans+tmp*K)%(10**9+7))

Submission status: Wrong Answer

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

A_cnt = [0] * (max(A)+1)
ans = 0
tmp = 0

def pow_k(x, n):
    """
    O(log n)
    """
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2

    return K * x

for i in reversed(range(N)):
    A_cnt[A[i]] += 1
    tmp += sum(A_cnt[:A[i]])

for i in A:
    ans += pow_k(sum(A_cnt[:i]), (K-1))

print(ans+tmp*K)

Submission status: Wrong Answer

Solution code:
from decimal import Decimal

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

def tosa(a,n,d):
    s = Decimal(n / 2) * (2*a+(n-1)*d)
    return int(s)

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

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

d = N*(N-1)//2
print(tosa(ans,K,d)%mod)

Submission status: Wrong Answer

Solution code:
from decimal import Decimal

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

def tosa(a,n):
    s = Decimal(n / 2) * (2*a+(n-1)*a)
    return int(s)

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

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

print(tosa(ans,K)%mod)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率

def input(): return sys.stdin.readline()[:-1]
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 10**9+7
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    #N = int(input())
    N, K = map(int, input().split())
    A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    count=0
    la=len(A)
    for i in range(0,la-1):
        for j in range(i+1,la):
            ai,aj=A[i],A[j]
            if ai>aj:
                count+=1
    
    aset=set(A)
    asrt=sorted(list(aset))
    d=dict()

    for i,a in enumerate(asrt):
        d[a]=i
    ans=(count*K)%mod
    
    for a in A:
        order=d[a]
        ans=(ans+((K*(K-1)//2)%mod*order)%mod)%mod
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率

def input(): return sys.stdin.readline()[:-1]
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    #N = int(input())
    N, K = map(int, input().split())
    A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    count=0
    for i,ai in enumerate(A[:-1]):
        for j, aj in enumerate(A[i+1:]):
            if ai>aj:
                count+=1
    
    aset=set(A)
    asrt=sorted(list(aset))
    d=dict()

    for i,a in enumerate(asrt):
        d[a]=i
    ans=count*K%mod
    
    for a in A:
        order=d[a]
        ans=(ans+(K*(K-1)//2%mod*order)%mod)%mod
    print(ans)



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
MOD = int(1e9+7)
N,K = map(int,input().split())
A = list(map(int,input().split()))
inv = pow(2,MOD-2,MOD)
ans = 0
for i in range(N):
    cnt = 0
    for j in range(N):
        if A[i] > A[j]:
            cnt += 1
    val = (cnt * (K+1) * K * inv) % MOD
    cnt = 0
    for j in range(i):
        if A[i] > A[j]:
            cnt += 1
    val -= cnt
    val %= MOD
    ans += val
    ans %= MOD
print(ans)

Submission status: Wrong Answer

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

# 数列の自分より後方で自分より小さい数
c1 = sum([1 if a[i]>j else 0 for i in range(n) for j in a[i+1:]])

# 数列内で自分より小さい数
from collections import Counter
ca = Counter(a)

c2 = 0
for n1 in ca.keys():
    for n2,cnt2 in ca.items():
        if n2<n1:
            c2+=cnt2

MOD=10**9+7
k %= MOD
ans = (c1*k)%MOD + (c2*k*(k-1)//2)%MOD
ans %= MOD
print(ans)

Submission status: Wrong Answer

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

# 数列の自分より後方で自分より小さい数
c1 = sum([1 if a[i]>j else 0 for i in range(n) for j in a[i+1:]])

# 数列内で自分より小さい数
from collections import Counter
ca = Counter(a)

c2 = 0
for n1 in ca.keys():
    for n2,cnt2 in ca.items():
        if n2<n1:
            c2+=cnt2
MOD=10**9+7
ans = (c1*k)%MOD + (c2*k*(k-1)//2)%MOD
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
d=dict()
for i in a:
    if i in d:
        d[i]+=1
    else:
        d[i]=1
l=sorted(d.items())
#print(l)
r=(k*(k+1)//2)%mod
p=0
for i,j in l[:-1]:
    p+=p+(j*r)%mod
p+=mod
e=0
for i in range(n):
    for j in range(i):
        e+=a[i]>a[j]
#print(e)
print((p-((e*k)%mod))%mod)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun May 31 11:25:07 2020

@author: NEC-PCuser
"""

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

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

tentosu = 0

MOD = 1000000007

for i in range(0, N):
    a = 0
    d = 0
    """
    for j in range(0, N):
        if (i == j):
            continue
        if (i < j and A[i] > A[j]):
            a += 1
        if (A[i] > A[j]):
            d += 1
    """
    for j in range(0, N):
        if (A[i] > A[j]):
            d += 1
    for j in range(i, N):
        if (A[i] > A[j]):
            a += 1
    
    
    tentosu += a * K % MOD;
    tentosu %= MOD;
    tentosu += (K - 1) * K / 2 % MOD * d % MOD;
    tentosu %= MOD;
    
print(int(tentosu))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun May 31 11:25:07 2020

@author: NEC-PCuser
"""

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

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

tentosu = 0

MOD = 1000000007

for i in range(0, N):
    a = 0
    d = 0
    for j in range(0, N):
        if (i == j):
            continue
        if (i < j and A[i] > A[j]):
            a += 1
        if (A[i] > A[j]):
            d += 1
    tentosu += a * K % MOD;
    tentosu %= MOD;
    tentosu += (K - 1) * K / 2 % MOD * d % MOD;
    tentosu %= MOD;
    
print(int(tentosu))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun May 31 11:25:07 2020

@author: NEC-PCuser
"""

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

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

tentosu = 0

MOD = 1000000007

for i in range(0, N):
    a = 0
    d = 0
    for j in range(0, N):
        if (i == j):
            continue
        if (i < j and A[i] > A[j]):
            a += 1
        if (A[i] > A[j]):
            d += 1
    tentosu += ((a*K % MOD) + (K-1)*K/ 2 % MOD * d % MOD) % MOD
    
print(int(tentosu) % MOD)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun May 31 11:25:07 2020

@author: NEC-PCuser
"""

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

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

tentosu = 0


for i in range(0, N):
    a = 0
    d = 0
    for j in range(0, N):
        if (i == j):
            continue
        if (i < j and A[i] > A[j]):
            a += 1
        if (A[i] > A[j]):
            d += 1
    tentosu += a*K + (d*K) * (K-1) / 2
    
print(int(tentosu) % 1000000007)

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):
    tmp = 0
    for j in range(i):
        if A[i] < A[j]:
            tmp += 1
    if tmp:
        t = ((tmp * K % mod) + tmp) % mod
        c = K // 2
        if K == 1:
            ans = (ans + tmp) % mod
        elif K % 2 == 0:
            ans = (ans + (t * c % mod)) % mod
        else:
            ans = (ans + ((t * c + (c + 1)) % mod)) % mod

print(ans)

Submission status: Wrong Answer

Solution code:
def answer(arr, k):
    _mod = (10**9+7)
    left = 0
    right = 0
    for i in range(len(arr)):
        for j in range(i, len(arr)):
            if arr[i] > arr[j]:
                left += 1
            if arr[i] < arr[j]:
                right += 1
    left = (left * (k*(k+1))/2)
    right = (right * (k*(k-1))/2)
    return int((left+right)%_mod)

n, k = map(int, input().split())
arr = list(map(int, input().split()))
print(answer(arr, k))

Submission status: Wrong Answer

Solution code:
def answer(arr, k):
    _mod = (10**9+7)
    left = 0
    right = 0
    for i in range(len(arr)):
        for j in range(i, len(arr)):
            if arr[i] > arr[j]:
                left += 1
            if arr[i] < arr[j]:
                right += 1
    left = (left * (k*(k+1))/2)%_mod
    right = (right * (k*(k+1))/2)%_mod
    return int((left+right)%_mod)

n, k = map(int, input().split())
arr = list(map(int, input().split()))
print(answer(arr, k))

Submission status: Wrong Answer

Solution code:
def f(d,i):
    if i in d:
        d[i]+=1
    else:
        d[i]=1
    return d
mod=10**9+7
n,k=map(int,input().split())
a=list(map(int,input().split()))
#a=[i for i in range(2000)]
p=0
d=dict()
for i in range(n):
    b=a[i]
    d=f(d,b)
    for j in range(i):
        if a[i]>a[j]:
            p-=1
l=sorted(d.items())[:-1]
print(p)
r=0
for i in range(len(l)):
    g,h=l[i]
    r+=h
    p+=sum(range(r*k))%mod
print(p)

Submission status: Wrong Answer

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

mod = 10**9 + 7
result = 0
count = [0] * 2001

# リスト内での繰り返し
for a in A:
    count[a-1] += 1
    result += K * sum(count[a:])
    result %= mod

kn = 0
# 前のループに存在する自分より大きい数
count = [i for i in count if i != 0]
total = sum(count) % mod
for i in count[::-1]:
    total -= i
    kn += total
    kn %= mod

result += kn * K*(K-1)//2
result %= 10**9 + 7

print(result)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

# グループ間
coef = 0
for i in range(n):
    coef += np.where(a < a[i])[0].shape[0]

# グループ間 - 調整数
diff = 0
for i in range(1, n):
    diff += np.where(a[:i - 1] < a[i])[0].shape[0]

mod = 10**9 + 7

ans = (coef * (1 + k) * k // 2 - diff) % mod

print(ans)

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):
    migi = 0
    a = A[i]
    for j in range(i+1,n):
        if a > A[j]:
            migi += 1
    ans += migi * k
    ans %= mod
# 全体で、その数よりも小さいもの(ループするので)
for i in range(n):
    zen = 0
    a = A[i]
    for j in range(n):
        if a > A[j]:
            zen += 1
    # 等差数列のやつ 初項は0, 項数はk,末項はzen * (k-1)
    ans += ((zen*(k-1))%mod) * k //2
    ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
INF = 10 ** 9 + 7

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

# 単体のA内で発生するケース
inv = 0
for i in range(N-1):
    for j in range(i+1, N):
        if A[i] > A[j]:
            inv += 1
inv = inv * K

# 異なるA間で発生するケース
ini = 0
for k in range(N):
    for l in range(N):
        if A[k] > A[l]:
            ini += 1
ini = ini * K * (K-1) / 2
ans = int(inv+ini) % INF
print(ans)