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 math
n,k = map(int,input().split())
a = list(map(int,input().split()))
lim = int((1e+9)+7)
right = [0 for _ in range(n)]
left = [0 for _ in range(n)]
for i in range(n):
    for j in range(n):
        if a[j] < a[i]:
            if i < j:
                right[i] += 1
            else:
                left[i] += 1
ans = 0
def c(g):
    re = g*(g-1)//2
    return re

for i in range(n):
    ans = (ans - (left[i]*k) + ((right[i]+left[i])*c(k+1)))%lim
print(ans)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import Counter,defaultdict
mod=10**9+7
def main():
    n,k=map(int,input().split())
    A=[int(_) for _ in input().split()]
    ac=Counter(A)
    aci=list(ac.items())
    aci.sort(reverse=True)
    nn=len(aci)
    aciv_cum=[0]*nn
    m2=defaultdict(int)
    for i in range(1,nn):
        aciv_cum[i]=aciv_cum[i-1]+aci[i-1][1]
        m2[aci[i][0]]+=aciv_cum[i]
    ans=0
    for i,a in enumerate(A):
        b=m2[a]
        x=0
        for j in range(i):
            if A[j]>a:
                x+=1
        ans+=k*(2*x+(k-1)*b)//2%mod
    print(ans%mod)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
n,  k = list(map(int, input().split()))
al = list(map(int, input().split()))
cnt = [0]*n*2
dif = [0]*n
MOD = 10**9+7

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

for i in range(n):
    dif[i] = cnt[i] - cnt[i+n]
print((sum(cnt[n:])*k + sum(dif)*(1+k-1)*(k-1)//2) % MOD)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    ans = 0
    mod = 10 ** 9 + 7
    for i in range(N):
        left = 0
        for j in range(i):
            if A[j] < A[i]:
                left += 1
        right = 0
        for j in range(i+1, N):
            if A[j] < A[i]:
                right += 1
        ans += (right * K * (K+1) + left * (K-1) * K) // 2
        ans %= mod
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import collections
N,K = map(int,input().split())
A = list(map(int, input().split()))
Ni_block = 0
Ni_inter = 0
bignum = pow(10,9)+7
for i in range(N):
   for j in range(N):
      if A[i]>A[j]:
         Ni_inter += 1
         if j>i:
            Ni_block+=1
# print(Ni_inter,Ni_block)
# c = collections.Counter(A)
# N_multiple = 1
# # print(c)
# for i in c:
#    # print(i, c[i])
#    N_multiple*=c[i]
   
# print(N_multiple)
# print(len(c))
# Ndiff = len(c)
# Ni = Ni_block*K+(((K*(K-1))//2) % bignum)*(((Ni_inter*(Ni_inter-1))//2) % bignum)
Ni = Ni_block*K+(((K*(K-1))//2) % bignum)*Ni_inter
print(Ni%bignum)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
    def sum(self, i):  # 区間 [1, i]の和
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    def add(self, i, x):  # iにxを加算
        while i <= self.size:
            self.tree[i] += x
            i += i & -i  
    def pos(self, idx):  # idxの値を取得
        return self.sum(idx) - self.sum(idx-1)
    def lower_bound(self, w):  # w以上の値を持つ最小のidxを検索
        if w <= 0:
            return 0
        idx = 0
        k = 1
        while k*2 <= self.size:
            k *= 2
        while k > 0:
            if idx+k <= self.size and self.tree[idx+k] < w:
                w -= self.tree[idx+k]
                idx += k
            k //= 2
        return idx+1

N, K = MAP()
A = LIST()

bit = Bit(max(N, max(A)))
inv = 0
for i, a in enumerate(A):
	inv += i-bit.sum(a)
	bit.add(a, 1)
ans = inv*K%mod

cnt = [0]*(max(A)+1)
for a in A:
	for b in A:
		if a < b:
			cnt[a] += 1

for n in cnt:
	ans += n*((K*(K-1))//2)
	ans %= mod
print(ans)

Submission status: Accepted

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

trip = 0
for i in range(N):
    for j in range(N):
        if A[i] < A[j]:
            num[j] += 1
        if i < j and A[i] > A[j]:
            trip += 1

ans = (trip * K) % mod
for n in num:
    ans += n * K * (K - 1) // 2
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


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

    res = 0
    for i in range(n):

        # A[i]の転倒数を求める
        x = 0
        for j in range(i + 1, n):
            if A[i] > A[j]:
                x += 1

        # A[i]より小さい数を求める
        y = 0
        for j in range(n):
            if A[i] > A[j]:
                y += 1

        res += x * k
        res %= mod
        res += y * (k - 1) * k // 2
        res %= mod

    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
INF = 10 ** 12
import sys
sys.setrecursionlimit(1000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)
import numpy as np

def main():
    n,k = map(int,input().split())
    a = list(map(int,input().split()))
    
    cnt = [0] * 2002
    ret = [0] * n
    for i in range(n):
        for j in range(a[i] + 1):
            cnt[j] += 1

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

if __name__ =='__main__':
    main()

Submission status: Accepted

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

a_out = [sum(bb > aa for bb in a ) for aa in a]
a_in = [sum(a[i] > a[j] for i in range(n) if i<j) for j in range(n)]

print( (sum(a_out)*k*(k-1)//2 + sum(a_in)*k)%mod )

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
a = list(map(int, input().split()))
cnt = 0
mod = 10 ** 9 + 7
for i in range(N):
    #print(cnt)
    for j in range(N):
        if a[i] > a[j]:
            cnt += 1
ans = cnt * ((K - 1) * K) * 500000004 % mod
for i in range(N - 1):
    for j in range(i + 1, N):
        if a[i] > a[j]:
            ans += K % mod
print(ans % mod)

Submission status: Accepted

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
import sys,bisect,string,math,time,functools,random
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[];g=[[] for i in range(n)]
    for i in range(E):
        inp=LI();org_inp.append(inp)
        if index==0:inp[0]-=1;inp[1]-=1
        if len(inp)==2:
            a,b=inp;g[a].append(b)
            if not Directed:g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp;aa=(inp[0],inp[2]);bb=(inp[1],inp[2]);g[a].append(bb)
            if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[1]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)];rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()

class Comb:
    def __init__(self,n,mo=10**9+7):
        self.fac=[0]*(n+1)
        self.inv=[1]*(n+1)
        self.fac[0]=1
        self.fact(n)
        for i in range(1,n+1):
            self.fac[i]=i*self.fac[i-1]%mo
            self.inv[n]*=i
            self.inv[n]%=mo
        self.inv[n]=pow(self.inv[n],mo-2,mo)
        for i in range(1,n):
            self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
        return
    
    def fact(self,n):
        return self.fac[n]
        
    def invf(self,n):
        return self.inv[n]

    def comb(self,x,y):
        if y<0 or y>x:
            return 0
        return self.fac[x]*self.inv[x-y]*self.inv[y]%mo

show_flg=False
show_flg=True

ans=0


n,k=LI()
a=LI()
m=[0]*n
s=0
for i in range(n):
    for j in range(n):
        if a[i]<a[j]:
            m[j]+=1
        if a[i]<a[j] and i>j:
            s+=1
ans=s*k%mo
for i in range(n):
    ans+=m[i]*(k-1)*k//2
    ans%=mo
print(ans)

Submission status: Accepted

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

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

a_l += a_l
count2 = 0
for i in range(n*2):
    for j in range(i+1,n*2):
        if a_l[i] > a_l[j]:
            count2 += 1
count2 -= count1*2

ans = count2*(k-1)*k//2 + count1*k
ans%=mod

print (ans)

Submission status: Accepted

Solution code:
import bisect


if __name__ == '__main__':
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    # 自分より数値が小さい数の個数
    # 1, 3, 2 --> [0, 2, 1]
    B = A.copy()
    B.sort()
    cnt = [0 for _ in range(N)]
    for i, a in enumerate(A):
        idx = bisect.bisect_left(B, a)
        cnt[i] = idx

    ans = 0
    MOD = 1000000007
    for c in cnt:
        ans += c * (K - 1) * K // 2
        ans %= MOD

    # 自分より後ろに存在する自分より小さい数の個数
    # 1, 3, 2 --> [0, 1, 0]
    B = A.copy()
    B = B[::-1]
    cnt = [0 for _ in range(N)]
    array = []
    for i, b in enumerate(B):
        idx = bisect.bisect_left(array, b)
        cnt[i] = idx
        bisect.insort_left(array, b)
    cnt = cnt[::-1]

    for c in cnt:
        ans += c * K
        ans %= MOD

    print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from collections import Counter
def solve():
    mod = 10**9+7
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    B = [A[0]]
    fall_in = 0
    for i in range(1,N):
        fall_in += i - bisect_right(B,A[i])
        insort(B,A[i])
    c = Counter(A)
    double = 0
    for v in c.values():
        double += v*(v-1)//2
    fall_out = N*(N-1)//2 - double
    ans = fall_in * K % mod + fall_out * K*(K-1)//2 % mod
    ans %= mod
    return ans
print(solve())

Submission status: Accepted

Solution code:
N,K = map(int, input().split())
A_list = [int(e) for e in input().split()]

MOD_BY = 7 + 10**9
ans = 0

for i in range(N):
    for j in range(N):
        Bi = A_list[i]
        Bj = A_list[j]
        #print(Bi,Bj,end="")
        if Bi > Bj:
            if K > 1:
                if i < j:
                    ans += (K+1)*K//2
                else:
                    ans += K*(K-1)//2
            else:
                if i > j:
                    ans += 1
                    
        ans %= MOD_BY
        #print(ans)
print(ans)

Submission status: Accepted

Solution code:
# python3.4.2用
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from decimal import *
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
INF = float('inf') #無限大
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(sys.stdin.readline()) #整数読み込み
def ifn(): return float(sys.stdin.readline()) #浮動小数点読み込み
def isn(): return sys.stdin.readline().split() #文字列読み込み
def imn(): return map(int, sys.stdin.readline().split()) #整数map取得
def imnn(): return map(lambda x:int(x)-1, sys.stdin.readline().split()) #整数-1map取得
def fmn(): return map(float, sys.stdin.readline().split()) #浮動小数点map取得
def iln(): return list(map(int, sys.stdin.readline().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, sys.stdin.readline().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD
def lprint(l): print(*l, sep='\n')
def sieves_of_e(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i * 2, n+1, i): is_prime[j] = False
    return is_prime

N, K = imn()
A = iln()

la = len(A)
cnt = 0

# 1個のブロック内の転倒数を求める
cnt1 = 0
for i in range(la):
    for j in range(i+1, la):
        if A[i] > A[j]:
            cnt1 += 1

# ブロック間の転倒数を求める
cnt2 = 0
for i in range(la):
    for j in range(la):
        if A[i] > A[j]:
            cnt2 += 1
ans = cnt1*K
ans += cnt2*(K-1)*K//2
    
print(ans%MOD)

Submission status: Accepted

Solution code:
mod = 10**9 + 7
n, k = map(int, input().split())
a = list(map(int, input().split()))
h = [0 for _ in range(2001)]
ans_1 = []
mi = 2001
for ai in reversed(a):
    h[ai] += 1
    mi = min(mi, ai)
    if mi == ai: continue
    ans_1.append(sum(h[:ai]))
h = [0 for _ in range(2001)]
ans_2 = []
mi = 2001
for ai in a:
    h[ai] += 1
    mi = min(mi, ai)
    if mi == ai: continue
    ans_2.append(sum(h[:ai]))
print(int((sum(ans_1) * (k * (k+1) // 2)) +
          (sum(ans_2) * (k * (k-1) // 2))) % mod)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
MOD = 10**9 + 7

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

ans = 0
ans2 = 0
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        else:
            if i < j and a[i] > a[j]:
                ans += 1
            if i > j and a[i] > a[j]:
                ans2 += 1
            
mal = k*(k+1)//2 % MOD
mal2 = k*(k-1)//2 % MOD
print((ans * mal % MOD + ans2 * mal2 % MOD) % MOD)

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-1):
    count=0
    for j in range(i+1, n):
        if A[i]>A[j]:
            count+=1
    ans = (ans + (count*((k*(k+1))//2)%mod))%mod

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

ans = (down2 * ((k-1) * k // 2)) % d
ans = (ans + down1 * k) % d
print(ans)

Submission status: Accepted

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

after_sum = 0
whole_sum = 0
for i in range(N):
    before = 0
    after = 0
    for j in range(N):
        if A[i] > A[j]:
            if i < j:
                after += 1
            elif j < i:
                before += 1
    # print(before, after)
    whole = before + after
    after_sum = (after_sum + after) % MOD
    whole_sum = (whole_sum + whole) % MOD

a = (K * after_sum) % MOD
b = ((K - 1) * K // 2) % MOD
b = (b * whole_sum) % MOD
print((a + b) % MOD)

Submission status: Accepted

Solution code:
import sys


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(10 ** 9)


def main():
    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
    cnt_1 = 0
    for i in range(N):
        for j in range(N):
            if A[i] > A[j]:
                cnt_1 += 1
    a = cnt * K % MOD
    b = (cnt_1 * K * (K - 1) // 2) % MOD
    answer = (a + b) % MOD
    print(answer)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
mod = 10**9+7
counter1 = [0] * N
counter2 = [0] * N
for i in range(N):
    p, q = 0, 0
    for j in range(i+1, N):
        if A[i] > A[j]:
            counter1[i] += 1
    
    for j in range(N):
        if A[i] > A[j]:
            counter2[i] += 1

ans = 0
for i in range(N):
    c1 = counter1[i]
    c2 = counter2[i]
    ans = (ans + (c1 * K + c2 * K * (K - 1) // 2)) % mod
print(ans)

Submission status: Accepted

Solution code:
import math
n,k = map(int,input().split())
li = list(map(int,input().split()))
li.reverse()
count = 0
#print(li)
for i,l in enumerate(li):
    if i != len(li)-1: 
        a = len(list(filter(lambda x:x > l, li[i+1:])))
        count += a

next_count = 0
#print(li)
for i,l in enumerate(li):
    a = len(list(filter(lambda x:x > l, li)))
    next_count += a
""" 
al = 0
for x in range(1,k+1):
    if x == 1:
        al += count
    else:
        al += count
        al += next_count*(x-1) """
#print(al)
all_count = (k+1)*(k)//2
#print(all_count-k,count,next_count)
al = (all_count-k)*(next_count)+k*count
print(al%(10**9+7))
#print(count,next_count)

Submission status: Accepted

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

Submission status: Accepted

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):
    a=0
    b=0
    for j in range(min(i+1,n-1),n):
        if A[i]>A[j]:
            b+=1
    for j in range(i):
        if A[i]>A[j]:
            a+=1

    ans+=(b*k+(a+b)*k*(k-1)//2)
print(ans%mod)

Submission status: Accepted

Solution code:
def main():
    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]:
                continue
            elif A[i] > A[j]:
                count += K + K*(K-1) // 2
            else:
                k = K - 1
                count += k + k*(k-1) // 2
        count %= MOD

    print(count)
    



main()

Submission status: Accepted

Solution code:
def main():
    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]:
                continue
            elif A[i] > A[j]:
                count += K + K*(K-1) // 2
            else:
                k = K - 1
                count += k + k*(k-1) // 2
            count %= MOD

    print(count)
    



main()

Submission status: Accepted

Solution code:
def main():
    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]:
                continue
            elif A[i] > A[j]:
                count += K + K*(K-1) // 2
            else:
                k = K - 1
                count += k + k*(k-1) // 2

    print(count % MOD)
    



main()

Submission status: Accepted

Solution code:
def main():
    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, N):
            if A[i] == A[j]:
                continue
            elif K == 1 and A[i] > A[j]:
                count += 1
            else:
                if A[i] > A[j]:
                    count += K + K*(K-1) // 2
                else:
                    k = K - 1
                    count += k + k*(k-1) // 2

    print(count % MOD)
    



main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from bisect import bisect_left

n, k = map(int,input().split())
a = list(map(int,input().split()))
assert len(a) == n
sa = sorted(a)
M = 10**9 + 7

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

inv_all = [0] * n
for i in range(n):
    inv_all[i] = bisect_left(sa, a[i])

def solve():
    ans = 0
    for i in range(n):
        ans += (k * inv_before[i]) % M
        ans %= M
        ans += (k * (k-1) // 2 * inv_all[i]) % M
        ans %= M
    return ans

print(solve())

Submission status: Accepted

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

mod = 10**9 + 7

right_numbers = [0]*N
left_numbers = [0]*N
right_ans = [0]*N
left_ans = [0]*N

right_total = K*(K+1)//2
left_total = K*(K-1)//2

for i in range(N):
    for r in range(i+1,N):
        if A[i] > A[r]:
            right_numbers[i] += 1
    for l in range(0,i):
        if A[i] > A[l]:
            left_numbers[i] += 1
    #print(right_numbers[i] * right_total)
    #print(left_numbers[i] * left_total)
    right_ans[i] = right_numbers[i] * right_total
    left_ans[i] = left_numbers[i] * left_total

"""
print(right_numbers)
print(left_numbers)
print(right_ans)
print(left_ans)
print(sum(right_ans))
print(sum(left_ans))
"""
print((sum(right_ans) + sum(left_ans)) % mod)

Submission status: Accepted

Solution code:
from collections import Counter

N, K = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7
c = Counter(A)
c = sorted(c.items(), key=lambda x: x[0])

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

out_num = 0
cnt = 0
for k, v in c:
    cnt += v
    out_num += (N - cnt) * v

ans = in_num * K + out_num * (K * (K - 1) // 2)
print(ans % MOD)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
cnt = [[0,0] for _ in range(N)]
for i,a in enumerate(A):
    for j,b in enumerate(A):
        if a > b:
            if i < j:
                cnt[i][1] += 1
            if i > j:
                cnt[i][0] += 1

ans = 0
mod = 10**9 + 7
for c in cnt:
    ans += c[0]*(K-1)*K//2
    ans += c[1]*K*(K+1)//2
    ans %= mod
print(ans)

Submission status: Accepted

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

# Kを無視して店頭数がいくつなのかを数える
cnt = 0
for i in range(N):
    for j in range(i+1, N):
        if A[i] > A[j]:
            cnt += 1
            cnt %= MOD

cnt2 = 0
A.extend(A)
for i in range(N*2):
    for j in range(i+1, N*2):
        if A[i] > A[j]:
            cnt2 += 1
            cnt2 %= MOD

cnt2 -= cnt * 2

ans = 0
ans += cnt * K % MOD
ans += cnt2 * (K * (K-1) // 2) % MOD
print(ans % MOD)

Submission status: Accepted

Solution code:
#coding:utf-8
import sys,os
from collections import defaultdict, deque
from fractions import gcd
from math import ceil, floor
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7

    N, K = LMIIS()
    A = LMIIS()

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

    print(ans)
    

if __name__ == '__main__':
    main()

Submission status: Accepted

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

# Aに対する転倒数はすぐ求まる
# Aが繰り返されたときに転倒数はどのように増えるのか？
# Aのn_invは少なくとも*Kされる
# 繰り返しの分で増えるものは(K-1)K/2倍される
# 繰り返しの分はどうやって求める？→2倍にしたAに対して n_inv_2A-2n_invすればよい

import sys
read = sys.stdin.readline
ra = range
enu = enumerate
MOD = 10**9 + 7


def read_ints():
    return list(map(int, read().split()))


def ret_n_inv(ls):
    n_inv = 0
    N = len(ls)
    for i in ra(N):
        for j in ra(i + 1, N):
            if ls[i] > ls[j]:
                n_inv += 1
    return n_inv


N, K = read_ints()
A = read_ints()

# 愚直に転倒数を求める
n_A = ret_n_inv(A)
if K == 1:
    print(n_A)
    exit()
n_2A = ret_n_inv(A + A)
mul = (K - 1) * K // 2 % MOD
n_skip = (n_2A - 2 * n_A) * mul % MOD
print((n_A * K + n_skip) % MOD)

Submission status: Accepted

Solution code:
# つよいさんすう
# 最初のAを単独で考えたらいける 等差数列の和の公式はググった
# ex) k = 3, a = [1, 3, 2]
# 1 3 2 1 3 2 1 3 2
# 最初の1 3 2
# 3...[2,1,2,1,2]で5
# 2...[1.1]で2
# 二番目の1 3 2
# 3...[2,1,2]
# 2...[1]
# 三番目の1 3 2
# 3...[2]で1

# 3だけでみると初項1 末項5 公差2で n(2*a1 +(n-1)*2)/2 = 3*(2*1 + (3-1)*2)/2 = 3*6/2 = 9
# n*(a1+an)/2 = 3*(1+5)/2 = 9
# これを一般化すればいけそう

# ex) k = 3, a = [3, 5, 2, 4, 1]とすると
# 3 5 2 4 1 3 5 2 4 1 3 5 2 4 1
# 3の初項は2で公差2 -> 3*(2*2+(3-1)*2)/2 = 12 (6+4+2)
# 5の初項は3で公差4 -> 3*(2*3 + (3-1)*4)/2 = 21 (11+7+3)
# 2の初項は1で公差2 -> 3*(2*1 + (3-1)*2)/2 = 9
# 4の初項は1で公差2 -> 3*(2*1 + (3-1)*3)/2 = 12
# 1の初項は0で公差0 -> 3*(2*0 + (3-1)*0)/2 = 0
# ...みたいな感じ

n, k = map(int, input().split())
a = list(map(int, input().split()))
MOD = 10**9 + 7
first_subarr = [0] * n
rest_arr = [0] * n
for i in range(n):
    for j in range(i, n):
        if a[i] > a[j]:
            first_subarr[i] += 1

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

diffs = [0] * n
for i in range(n):
    diffs[i] = first_subarr[i] + rest_arr[i]

ans = 0
for i in range(n):
    # print("{}について".format(a[i]))
    # print("初項:{} 公差:{}なので".format(first_subarr[i], diffs[i]))
    tmp = k * (2 * first_subarr[i] + (k - 1) * diffs[i]) // 2
    # print("総和は{}".format(tmp))
    ans += tmp
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
*A, = map(int, input().split())
mod = 10**9+7
v1, v2 = 0, 0

for i in range(N):
    p, q = 0, 0
    for j in range(i+1, N):
        if A[i]>A[j]:
            p += 1
    
    for j in range(N):
        if i==j:continue
        if A[i]>A[j]:
            q += 1
    
    v1 += p
    v2 += q

print((v1*K+v2*(K*(K-1)//2))%mod)