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: Accepted

Solution code:
import sys
input = sys.stdin.readline

def bubble_sort(A):
    flag = 1  # if non-sorted element exist on side
    counter = 0
    while flag:
        flag = 0
        for i in range(1, len(A))[::-1]:
            if A[i] < A[i - 1]:
                counter += 1
                A[i], A[i - 1] = A[i - 1], A[i]
                flag = 1
    return (A,counter)


def main():
    _,k = [int(i) for i in input().strip().split()]
    l = [int(i) for i in input().strip().split()]
    _sorted, inner = bubble_sort(l)
    _, outer = bubble_sort(_sorted + _sorted)
    
    print((inner * k + (k * (k - 1) // 2) * outer) % (10 ** 9 + 7))
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7

if __name__ == "__main__":
    N, K = [int(x) for x in input().split(" ")]
    A = [int(x) for x in input().split(" ")]

    count_a = 0
    count_b = 0
    A_ = K * (K + 1) // 2
    B = K * (K - 1) // 2
    for i in range(N):
        for j in range(i + 1, N):
            if A[i] > A[j]:
                count_a += 1
            if A[i] < A[j]:
                count_b += 1

    print((A_ * count_a + B * count_b) % MOD)

Submission status: Accepted

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

mod=10**9+7

B=[]
for i in range(N):
    l=0
    r=0
    for j in range(i):
        if A[i]>A[j]:
            l+=1

    for k in range(i,N):
        if A[i]>A[k]:
            r+=1
    B.append([l,r])

ans=0
for i in range(N):
    ans+=B[i][0]*(K-1)*K//2+B[i][1]*K*(K+1)//2
ans%=mod

print(ans)

Submission status: Accepted

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

ans = 0

# A内での転置数
# N*N通り調べてもいいが、以下ではjはiによって絞られることを考慮した
x = 0
for i in range(n - 1):
    for j in range(i + 1, n):
        if a[i] > a[j]:
            x += 1

# y=Aの各要素について、それより小さい要素がA内にいくつ存在するか
# ex. [3,5,1]なら、3>1, 5>3, 5>1の3つ
y = 0
for a1 in a:
    for a2 in a:
        if a1 > a2:
            y += 1

# A内で発生する転倒数 * AはK個存在する
ans += x * k

# ...[3,5,1]...[3,5,1]...と2つのAを選ぶ時を考える
# このとき2つのA間での転倒は3つ、つまりyに等しくなる
# 2つのAの選び方はK_C_2
ans += y * k * (k - 1) // 2

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

Submission status: Accepted

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: Accepted

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: Accepted

Solution code:
from collections import Counter
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()
c = list(Counter(sorted(a)).items())
# a 単体の中での転倒数
count_in_a = 0
for i in range(n):
    for j in range(i + 1, n):
        if a[i] > a[j]:
            count_in_a += 1
# b 全体での転倒数
count_in_b = 0
# ある a の各要素の もうひとつの a の各要素に対する転倒数の数を計算
for elem_1 in a:
    for elem_2 in a:
        if elem_1 > elem_2:
            count_in_b += 1
# b に含まれる k 個の a から 2 つ転倒数を考えるペアを選ぶ(k C 2)
ans = count_in_a * k + count_in_b * (k * (k - 1) // 2)
ans %= MOD
print(ans)

Submission status: Accepted

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((ans_mono*k+ans_di*(k*(k-1)//2))%int(1e+9+7))

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
lst=list(map(int,input().split()))
ans=0
for i in range(n):
    judge=lst[i]
    front=lst[:i]
    back=lst[i+1:]
    former=0
    latter=0
    for j in front:
        if j>judge:
            former+=1
    for j in back:
        if j>judge:
            latter+=1
    ans+=(former*((k+1)*k//2)+latter*((k-1)*k//2))
    ans%=(10**9+7)
print(ans)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7

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

ans = 0

for i, a in enumerate(A):
  before = 0
  after = 0
  for j, b in enumerate(A):
    if a > b:
      if i < j:
        after += 1
      else:
        before += 1
    
  ans += (after * K * (K + 1) // 2) % MOD
  ans += (before * K * (K - 1) // 2) % MOD
  ans %= MOD

print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

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

ans = 0
# 各数列A内での転倒数
for i in range(n):
  for j in range(i+1,n):
    if a[i] > a[j]: ans += 1
ans *= k

# k回の繰り返しによって発生する転倒数
a.sort()
nums = [0]*n
for i in range(1,n):
  if a[i] > a[i-1]: nums[i] = i
  else: nums[i] = nums[i-1]

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

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
l = [0]*n
r = [0]*n
for i in range(n):
  for j in range(n):
    if a[i] > a[j]:
      if j < i:
        l[i] += 1
      if j > i:
        r[i] += 1
#print(l)
#print(r)
ans = 0
MOD = 1000000007
x = (k*(k-1)//2)%MOD
y = (k*(k+1)//2)%MOD
for i in range(n):
  ans = (ans + x*l[i] + y*r[i])%MOD
print(ans)

Submission status: Accepted

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):
    cnt1 = 0
    cnt2 = 0
    for j in range(n):
        if i == j:
            continue
        if a[i] > a[j]:
            if i < j:
                cnt1 += 1
            else:
                cnt2 += 1
    ans += cnt1 * (k * (k + 1) // 2) + cnt2 * ((k - 1) * k // 2)
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, K = mapint()
As = list(mapint())
sortedAs = sorted(As)
mod = 10**9+7

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

from bisect import bisect_right
dub = 0
for a in As:
    bigger = N-bisect_right(sortedAs, a)
    dub += ((K-1)*K//2)*bigger
    dub %= mod
print((cnt*K + dub)%mod)

Submission status: Accepted

Solution code:
p = 10**9+7
N,K = map(int,input().split())
A = list(map(int,input().split()))
cnt_in = 0
for i in range(N-1):
    for j in range(i+1,N):
        if A[i]>A[j]:
            cnt_in += 1
A = A+A
cnt_out=0
for i in range(2*N-1):
    for j in range(i+1,2*N):
        if A[i]>A[j]:
            cnt_out += 1
cnt_out = cnt_out-2*cnt_in
cnt = K*cnt_in
cnt = (cnt+cnt_out*(K*(K-1))//2)%p
print(cnt)

Submission status: Accepted

Solution code:
def resolve():
  mod = 1000000007
  n, k = map(int, input().split())
  a = list(map(int, input().split()))
  x = 0
  # A の転倒数を求める
  for i in range(n):
    for j in range(i+1, n):
      if a[i] > a[j]:
        x += 1
  # A のすべての数字に対して，A内に自分より小さいものが何個あるか
  y = 0
  for i in range(n):
    for j in range(n):
      if a[i] > a[j]:
        y += 1
  ans = (x * k) % mod
  # 1 ~ k の和 * y
  ans += (((k-1) * (k)) // 2) * y % mod
  ans %= mod

  print(ans)
  return

if __name__ == "__main__":
  resolve()

Submission status: Accepted

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

Submission status: Accepted

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

count = [[0, 0] for i in range(N)]
for i in range(N):
    for j in range(i):
        if A[j] < A[i]:
            count[i][0] += 1
    for j in range(i+1, N):
        if A[j] < A[i]:
            count[i][1] += 1
ans = 0
mod = 10**9 + 7

for i in range(N):
    ans += (1+K-1)*(K-1) // 2 * count[i][0]
    ans += (1+K)*K // 2 * count[i][1]
    ans %= mod

print(ans % mod)

Submission status: Accepted

Solution code:
MOD = pow(10,9)+7
N,K = map(int,input().split())
A = list(map(int,input().split()))
L = [[0,0] for _ in range(N)] #leftとright

for i in range(N): #これが基準
  for j in range(N):
    if A[i] > A[j]:
      if i < j:
        L[i][1] += 1
      elif i > j:
        L[i][0] += 1
#print(L)
ans = 0
for i in range(N):
  left = K*(K-1)//2
  right = K*(K+1)//2
  ans = (ans+L[i][0]*left+L[i][1]*right)%MOD
print(ans)

Submission status: Accepted

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

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

ans = (cnt*k + y*k*(k-1)//2)%MOD
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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,2001):
    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: Accepted

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

mod = 1000000007
ans = 0
for i in range(n):
    ans += k * (2*grid[i][1] + (k-1)*grid[i][1]) // 2
    ans %= mod
    ans += (k-1) * (2*grid[i][0] + (k-2)*grid[i][0]) // 2
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
mod=10**9+7
R=[0]*N
L=[0]*N
for i in range(N):
    r,l=0,0
    a=A[i]
    for j in range(N):
        if i<j:
            if a>A[j]:
                r+=1
        else:
            if a>A[j]:
                l+=1
    R[i]=r
    L[i]=l
ans=0
for i in range(N):
    ans+=K*R[i]+(L[i]+R[i])*(K-1)*K//2%mod
    ans%=mod
print(ans)

Submission status: Accepted

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):
    c_0 = 0
    c_1 = 0
    for j in range(n):
        if i == j:
            pass
        elif a[i] > a[j]:
            if i < j:
                c_1 += 1
            else:
                c_0 += 1      
    ans += c_1*k*(k+1)//2 + c_0*k*(k-1)//2
    ans %= mod
print(ans)

Submission status: Accepted

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

count_inner = 0
for i in range(N):
    for j in range(i,N):
        if A[i] > A[j]:
            count_inner += 1
count_outer = 0
for i in range(N):
    for j in range(N):
        if A[i] > A[j]:
            count_outer += 1
def fact(n):
    if n>1:
        return n*fact(n-1)%mod
    else:
        return 1

answer = (count_inner*K + count_outer*K*(K-1)//2)%mod

print(answer)

Submission status: Accepted

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 += 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: Accepted

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

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 += 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: Accepted

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)))//2)%mod
    ans%=mod
print(ans)

Submission status: Accepted

Solution code:
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n,k=MI()
lis=LI()
count=0
sm=[0 for i in range(n)]
sm2=[0 for i in range(n)]
for i in range(n):
    for j in range(n):
        if lis[i]>lis[j]:
            if i<j:
                sm2[i]+=1
            else:
                sm[i]+=1
#print(sm)
ans=0
for i in range(n):
    ans=(ans+sm[i]*((k*(k-1))//2))%mod
    ans=ans+sm2[i]*((k*(k+1))//2)%mod
print(ans%mod)

Submission status: Accepted

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) * v
    # print(ten, oneset)
    print((kk * ten + kk * (kk-1) * oneset // 4)% MOD)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from typing import Optional, Sequence


class BinaryIndexedTree:
    """Binary Indexed Tree (Fenwick Tree): O(logN)

    References:
        http://hos.ac/slides/20140319_bit.pdf
    """

    __slots__ = ["_size", "_tree", "is_zero_origin"]

    def __init__(
        self,
        size: int,
        initial_values: Optional[Sequence[int]] = None,
        is_zero_origin: bool = True,
    ):
        self._size = size
        self._tree = [0] * (size + 1)
        self.is_zero_origin = is_zero_origin

        if initial_values:
            for i, a in enumerate(initial_values):
                self.add(i, a)

    def add(self, index: int, value: int) -> None:
        """Add value to tree[index], O(logN)."""
        if self.is_zero_origin:
            index += 1
        while index <= self._size:
            self._tree[index] += value
            index += index & -index

    def sum(self, index: int) -> int:
        """Return the sum of [1, index] in O(logN)."""
        ret = 0
        while index > 0:
            ret += self._tree[index]
            index -= index & -index
        return ret

    def range_sum(self, left: int, right: int) -> int:
        """Return the range sum of [left, right] in O(logN)."""
        if not self.is_zero_origin:
            left -= 1
        return self.sum(right) - self.sum(left)


def point_add_range_sum():
    # https://judge.yosupo.jp/problem/point_add_range_sum
    N, Q, *X = map(int, open(0).read().split())
    A, queries = X[:N], X[N:]
    tree = BinaryIndexedTree(N, A)
    res = []
    for com, x, y in zip(*[iter(queries)] * 3):
        if com:
            res.append(tree.range_sum(x, y))
        else:
            tree.add(x, y)
    print("\n".join(map(str, res)))


def jsc2019_qual_b():
    # https://atcoder.jp/contests/jsc2019-qual/tasks/jsc2019_qual_b
    N, K, *A = map(int, open(0).read().split())
    tree = BinaryIndexedTree(2000, is_zero_origin=False)
    x = 0
    for i, a in enumerate(A, 1):  # internal inversion
        tree.add(a, 1)
        x += i - tree.sum(a)
    y = -x
    for i, a in enumerate(A, 1):  # external inversion
        tree.add(a, 1)
        y += i + N - tree.sum(a)
    MOD = 10 ** 9 + 7
    print((x * K + y * K * (K - 1) // 2) % MOD)


if __name__ == "__main__":
    # point_add_range_sum()
    jsc2019_qual_b()

Submission status: Accepted

Solution code:
N, K, *A = map(int, open(0).read().split())

cntr = [0]*N
cntl = [0]*N


for i, a in enumerate(A):
    l = r = 0
    for b in A[:i]:
        if a > b:
            l += 1
    for b in A[i+1:]:
        if a > b:
            r += 1
    cntr[i] = r
    cntl[i] = l+r

mod = 10**9 + 7
ans = 0
for r in cntr:
    x = r * K % mod
    ans = (ans + x) % mod

c2 = K*(K-1)//2
for l in cntl:
    x = l*c2%mod
    ans = (ans + x) % mod

print(ans)

Submission status: Accepted

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

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

y = 0
for a1 in a:
    for a2 in a:
        if a1 > a2: y += 1

ans = (cnt * k + y * k * (k-1)//2)%MOD
print(ans)

Submission status: Accepted

Solution code:
p = 10**9+7
N,K = map(int,input().split())
A = list(map(int,input().split()))
inner=0
for i in range(N-1):
    for j in range(i+1,N):
        if A[i]>A[j]:
            inner += 1
B = A+A
outer = 0
for i in range(2*N-1):
    for j in range(i+1,2*N):
        if B[i]>B[j]:
            outer += 1
outer -= 2*inner
cnt = (inner*K)%p
a = ((K*(K-1))//2)%p
cnt = (cnt+outer*a)%p
print(cnt)

Submission status: Accepted

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

inv = 0
for i in range(N-1):
    for j in range(i+1,N):
        if A[i] > A[j]:
            inv += 1
ans = (inv * K) % MOD

from collections import Counter
ctr = Counter(A)
inv2 = 0
s = 0
for _,v in sorted(ctr.items()):
    inv2 += v * s
    s += v
ans += inv2 * K*(K-1)//2
ans %= MOD
print(ans)

Submission status: Accepted

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

ans = 0
mod = 10**9+7

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

Submission status: Accepted

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

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

ans = 0
for i in range(n-1):
    for j in range(i, n):
        if A[i] < A[j]:
            ans += (k-1)*k//2
        elif A[i] > A[j]:
            ans += k*(k+1)//2
        else:
            pass
        ans %= mod
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
mod = 10**9+7

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

#ラスト一個を除く
tentou = [0]*n
for i in range(n):
    for j in range(i+1,n):
        if A[i] > A[j]:
            tentou[i] += 1

back = [0]*n
for i in range(n):
    for j in range(i+1,n):
        if A[-(j+1)] < A[-(i+1)]:
            back[-(i+1)] += 1

#print(A)         
#print(tentou)
#print(back)

wa = k*(k+1)//2

ans = (wa%mod)*sum(tentou)%mod

ans += sum(back)*(k-1)*k//2

print(ans%mod)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
import math
#from itertools import product, accumulate, combinations, product
#import bisect# lower_bound etc
#import numpy as np
#from copy import deepcopy
#from collections import deque
class segtree:
    def __init__(self, n, init_val = 0):
        self.n = n
        self.init_val = init_val
        self.init = 0
        self.k = math.ceil(math.log2(n))
        if type(self.init_val) == int:
            self.bins = [init_val] * (1 << (self.k+1))
        elif len(self.init_val) >0:
            self.bins = [self.init] * (1<<(self.k+1))
            for idx, i in enumerate(range(1<<self.k, 1<<(self.k+1))):
                if len(self.init_val)>idx:
                    self.bins[i] = init_val[idx]
                else:
                    self.bins[i] = 0
        else:
            raise ValueError('init_val is invalid.')
        self.caliculate()

    def compare(self, l, r):
        return l + r

    def caliculate(self):
        k = self.k
        while k:
            for i in range(1<<k, 1<<(k+1)):
                if not i%2:
                    self.bins[i//2] = self.compare(self.bins[i], self.bins[i+1])
                else:continue
            k -= 1

    def update(self, idx, val):
        '''idx : 0-started index'''
        k = (1<<self.k) + idx
        self.bins[k] = val
        while k>1:
            self.bins[k // 2] = self.compare(self.bins[k // 2 * 2], self.bins[k // 2 * 2 + 1])
            k = k//2


    def eval(self, l, r):
        ret = self.init
        l = (1 << self.k) + l
        r = (1 << self.k) + r
        #print(l, r)
        while True:
            #print(l, r)
            if r - l == 1:
                ret = self.compare(ret, self.bins[l])
                ret = self.compare(ret, self.bins[r])
                break
            elif l == r:
                ret = self.compare(ret, self.bins[l])
                break
            else:
                done = False
                if l % 2:
                    ret = self.compare(ret, self.bins[l])
                    l += 1
                    done = True
                if not r % 2:
                    ret = self.compare(ret, self.bins[r])
                    r -= 1
                    done = True
                if not done:
                    l = l // 2
                    r = r // 2
        #print(ret)
        return ret

    def value(self, ind):
        return self.bins[(1<<self.k) + ind]

def run():
    N, K = list(map(int, sysread().split()))
    A = list(map(int, sysread().split()))
    st = segtree(2001, 0)
    T1 = [0] * N
    for i in list(range(N))[::-1]:
        T1[i] = st.eval(0, A[i]-1)
        st.update(A[i], st.value(A[i]) + 1)
        #print(st.bins)
    T2 = []
    for a in A:
        T2.append(st.eval(0, a-1))
    ret = 0
    mod = 10 ** 9 +7
    #print(T1, T2)
    tmp_k2 = K * (K-1) // 2
    tmp_k2 %= mod
    for t1, t2 in zip(T1, T2):
        ret += K * t1 % mod
        tmp = tmp_k2
        tmp %= mod
        tmp *= t2
        tmp %= mod
        ret += tmp
        ret %= mod
    print(ret)

if __name__ == "__main__":
    run()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
n, k, *a = map(int, open(0).read().split())
m = 10**9 + 7
c = [0] * 2001
t1 = [0] * n
for i in range(n):
    c[a[i]] += 1
    t1[i] = sum(c[a[i] + 1:])
t2 = [0] * n
for i in range(n):
    c[a[i]] += 1
    t2[i] = sum(c[a[i] + 1:])
s1 = sum(t1)
s2 = sum(t2)
print((s1 * k % m + k * (k - 1) // 2 * (s2 - s1) % m) % m)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7

n, k = map(int, input().split())
alst = list(map(int, input().split()))
ans = 0
loop1 = k * (k - 1) // 2
loop2 = (k + 1) * k // 2
loop1 %= MOD
loop2 %= MOD

for i, num in enumerate(alst):
    for j, num2 in enumerate(alst):
        if num > num2:
            if i < j:
                ans += loop2
                ans %= MOD
            else:
                ans += loop1
                ans %= MOD
print(ans)