Problem:


Score : 900 points

Problem Statement

Given are a permutation p_1, p_2, \dots, p_N of (1, 2, ..., N) and an integer K. Maroon performs the following operation for i = 1, 2, \dots, N - K + 1 in this order:

Shuffle p_i, p_{i + 1}, \dots, p_{i + K - 1} uniformly randomly.

Find the expected value of the inversion number of the sequence after all the operations are performed, and print it modulo 998244353.

More specifically, from the constraints of this problem, it can be proved that the expected value is always a rational number, which can be represented as an irreducible fraction \frac{P}{Q}, and that the integer R that satisfies R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353 is uniquely determined. Print this R.

Here, the inversion number of a sequence a_1, a_2, \dots, a_N is defined to be the number of ordered pairs (i, j) that satisfy i < j, a_i > a_j.

Constraints

2 \leq N \leq 200,000

2 \leq K \leq N

(p_1, p_2, \dots, p_N) is a permutation of (1, 2, \dots, N).

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K
p_1 p_2 ... p_N

Output

Print the expected value modulo 998244353.

Sample Input 1

3 2
1 2 3

Sample Output 1

1

The final sequence is one of (1, 2, 3), (2, 1, 3), (1, 3, 2), (2, 3, 1), each with probability \frac{1}{4}.
Their inversion numbers are 0, 1, 1, 2 respectively, so the expected value is 1.

Sample Input 2

10 3
1 8 4 9 2 3 7 10 5 6

Sample Output 2

164091855



Sample input:
3 2
1 2 3


Sample output:
1

Submission status: Accepted

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

class BIT:
    #1-indexed
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
        self.p = 2**(n.bit_length() - 1)
        self.dep = n.bit_length()
    def get(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
    
    def bl(self, v):
        if v <= 0:
            return -1
        s = 0
        k = self.p
        for _ in range(self.dep):
            if s + k <= self.size and self.tree[s+k] < v:
                s += k
                v -= self.tree[s+k]
            k //= 2
        return s + 1

N, K = map(int, readline().split())
MOD = 998244353
P = list(map(int, readline().split()))

r = (K-1)*pow(K, MOD-2, MOD)

L = [pow(r, max(0, i-K+1), MOD) for i in range(N)]
Linv = [pow(l, MOD-2, MOD) for l in L]
T1 = BIT(N)
T2 = BIT(N)

ans = 0
asum = 0
ti = (MOD+1)//2
for i in range(N):
    ans += i - T2.get(P[i])
    g1 = T1.get(P[i])
    ans = (ans + ti*L[i]*(2*g1-asum))%MOD
    T2.add(P[i], 1)
    T1.add(P[i], Linv[i])
    asum = (asum + Linv[i]) % MOD
print(ans)

Submission status: Accepted

Solution code:
class BIT: #0-indexed
    __slots__ = ["size", "tree","depth","n0"]
    def __init__(self, n):
        self.size = n
        self.tree = [0]*(n+1)
        self.depth = n.bit_length()
        self.n0 = 1<<self.depth

    def get_sum(self, i): #a_0 + ... + a_{i} #閉区間
        s = 0; i += 1
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def range_sum(self,l,r): #a_l + ... + a_r 閉区間
        return self.get_sum(r) - self.get_sum(l-1) 

    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def bisect_left(self,w):
        #和が w 以上になる最小の index
        #w が存在しない場合 self.size を返す
        if w <= 0: return 0
        x,k = 0,self.n0
        for _ in range(self.depth):
            k >>= 1
            if x+k <= self.size and self.tree[x+k] < w:
                w -= self.tree[x+k]
                x += k
        return x


# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

n,k = map(int,readline().split())
*p, = map(int,readline().split())

b = BIT(n)
num = BIT(n)
MOD = 998244353
inv2 = (MOD+1)//2
for i in range(k):
    b.add(p[i]-1,inv2)
    num.add(p[i]-1,1)

ans = k*(k-1)//2%MOD*inv2%MOD

prob = (k-1)*pow(k,MOD-2,MOD)%MOD #(k-1/k)
pinv = pow(prob,MOD-2,MOD)
val = pinv*inv2%MOD #(k-1)/k/2: これを bit に足していく
rate = prob #倍率
for j in range(k,n):
    # p_i < p_j
    pj = p[j]-1
    v = b.get_sum(pj)
    ans += v*rate%MOD
    ans %= MOD

    # p_i > p_j
    w =  b.get_sum(n-1)-v
    ans += (j - num.get_sum(pj)) - w*rate%MOD
    ans %= MOD
    
    b.add(pj,val)
    num.add(pj,1)
    val = val*pinv%MOD
    rate = rate*prob%MOD

print(ans%MOD)

Submission status: Accepted

Solution code:
class BIT: #0-indexed
    __slots__ = ["size", "tree","depth","n0"]
    def __init__(self, n):
        self.size = n
        self.tree = [0]*(n+1)
        self.depth = n.bit_length()
        self.n0 = 1<<self.depth

    def get_sum(self, i): #a_0 + ... + a_{i} #閉区間
        s = 0; i += 1
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def range_sum(self,l,r): #a_l + ... + a_r 閉区間
        return self.get_sum(r) - self.get_sum(l-1) 

    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def bisect_left(self,w):
        #和が w 以上になる最小の index
        #w が存在しない場合 self.size を返す
        if w <= 0: return 0
        x,k = 0,self.n0
        for _ in range(self.depth):
            k >>= 1
            if x+k <= self.size and self.tree[x+k] < w:
                w -= self.tree[x+k]
                x += k
        return x


# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

n,k = map(int,readline().split())
*p, = map(int,readline().split())

b = BIT(n)
num = BIT(n)
MOD = 998244353
inv = (MOD+1)//2
for i in range(k):
    b.add(p[i]-1,1)
    num.add(p[i]-1,1)

ans = k*(k-1)//2%MOD*inv%MOD

tot = k
rate = (k-1)*pow(k,MOD-2,MOD)%MOD
rateinv = pow(rate,MOD-2,MOD)
bunbo = rate
hosei = rateinv
for i in range(k,n):
    pi = p[i]-1
    v = b.get_sum(pi)
    #print(v*inv%MOD*bunbo%MOD,v*inv%MOD*bunbo%MOD*4%MOD,"v")
    ans += v*inv%MOD*bunbo%MOD
    ans %= MOD
    

    x = i - num.get_sum(pi)
    w = x - (tot-v)*inv%MOD*bunbo%MOD
    #print(x,tot,v)
    #print(w,w*4%MOD,"w")
    ans += w
    ans %= MOD
    
    b.add(pi,hosei)
    num.add(pi,1)
    tot += hosei
    hosei = hosei*rateinv%MOD
    bunbo = bunbo*rate%MOD



print(ans%MOD)
#print(ans*8%MOD)

Submission status: Accepted

Solution code:
class SegmentTree():
    def __init__(self, init, unit, f):
        self.unit = unit
        self.f = f
        if type(init) == int:
            self.n = init
            # self.n = 1 << (self.n - 1).bit_length()
            self.X = [unit] * (self.n * 2)
        else:
            self.n = len(init)
            # self.n = 1 << (self.n - 1).bit_length()
            self.X = [unit] * self.n + init + [unit] * (self.n - len(init))
            for i in range(self.n-1, 0, -1):
                self.X[i] = self.f(self.X[i*2], self.X[i*2|1])
    
    def getvalue(self, i):
        i += self.n
        return self.X[i]
        
    def update(self, i, x):
        i += self.n
        self.X[i] = x
        i >>= 1
        while i:
            self.X[i] = self.f(self.X[i*2], self.X[i*2|1])
            i >>= 1
    
    def add(self, i, x):
        i += self.n
        self.X[i] = (self.X[i] + x) % mod
        i >>= 1
        while i:
            self.X[i] = self.f(self.X[i*2], self.X[i*2|1])
            i >>= 1
    
    def getrange(self, l, r):
        l += self.n
        r += self.n
        al = self.unit
        ar = self.unit
        while l < r:
            if l & 1:
                al = self.f(al, self.X[l])
                l += 1
            if r & 1:
                r -= 1
                ar = self.f(self.X[r], ar)
            l >>= 1
            r >>= 1
        return self.f(al, ar)
    
    def debug(self):
        de = []
        a, b = self.n, self.n * 2
        while b:
            de.append(self.X[a:b])
            a, b = a//2, a
        print("--- debug ---")
        for d in de[::-1]:
            print(d)
        print("--- ---")

def r(a):
    for i in range(1, 10001):
        if i and a * i % mod <= 10000:
            return str(a*i%mod) + "/" + str(i)
        if i and -a * i % mod <= 10000:
            return str(-(-a*i%mod)) + "/" + str(i)
    return a

mod = 998244353
N, K = map(int, input().split())
P = [int(a) - 1 for a in input().split()]
f = lambda a, b: (a + b) % mod

p1 = (K - 1) * (K - 2) * pow(4, mod - 2, mod) % mod
p2 = K * (K - 1) * pow(4, mod - 2, mod) % mod
m = (K - 1) * pow(K, mod - 2, mod) % mod
invm = K * pow(K - 1, mod - 2, mod) % mod

st1 = SegmentTree(N, 0, f)
st2 = SegmentTree(N, 0, f)
ans = p2
for i, x in enumerate(P):
    if i >= K:
        ans = (ans + st1.getrange(x, N)) % mod
    st1.add(x, 1)

s = 1
invs = 1
st = SegmentTree(N, 0, f)
for i, x in enumerate(P[:K]):
    st.add(x, 1)
for i in range(K, N):
    s = s * m % mod
    invs = invs * invm % mod
    x = P[i]
    a = st.getrange(x, N) * s % mod
    ans = (ans + p2 - p1 - a) % mod
    st.add(x, invs % mod)

print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 998_244_353

@njit((i8, i8), cache=True)
def mpow(a, n):
    p = 1
    while n:
        if n & 1:
            p = p * a % MOD
        a = a * a % MOD
        n >>= 1
    return p

@njit((i8[:], ), cache=True)
def build(raw_data):
    bit = raw_data.copy()
    for i in range(len(bit)):
        j = i + (i & (-i))
        if j < len(bit):
            bit[j] += bit[i]
            bit[j] %= MOD
    return bit


@njit((i8[:], i8), cache=True)
def get_sum(bit, i):
    s = 0
    while i:
        s += bit[i]
        i -= i & -i
    return s % MOD


@njit((i8[:], i8, i8), cache=True)
def add(bit, i, x):
    while i < len(bit):
        bit[i] += x
        bit[i] %= MOD
        i += i & -i

@njit((i8, i8[:]), cache=True)
def main(K, A):
    N = len(A)
    # 各処理の段階で、n が active になっている確率を求める。
    # 個数の分布も持つ。
    # 更新を sparse にするために、時刻（右端のインデックス） i にアクティブになったところの
    # 生存率には、p^{-i} を入れておく。時刻 t には確率 p^{t-i} なので、和に p^t をかける
    p = (1 - mpow(K, MOD - 2)) % MOD
    p_inv = mpow(p, MOD - 2)
    bit_active = np.zeros(N + 1, np.int64)
    bit_cnt = np.zeros(N + 1, np.int64)
    half = (MOD + 1) // 2
    ans = 0
    # 最初の起動
    ans += K * (K - 1) // 2 % MOD * half % MOD
    ans %= MOD
    for i in range(K):
        x = A[i]
        add(bit_cnt, x, 1)
        add(bit_active, x, mpow(p_inv, K - 1))
    for i in range(K, N):
        x = A[i]
        low_cnt = get_sum(bit_cnt, x)
        high_cnt = i - low_cnt
        pt = mpow(p, i)
        active_sum_low = get_sum(bit_active, x) * pt % MOD
        active_sum_high = K - 1 - active_sum_low
        # 追加処理
        add(bit_cnt, x, 1)
        add(bit_active, x, mpow(p_inv, i))
        # A[i] と A[j] (j<i) の転倒数の期待値を計算
        inv = 0
        inv += active_sum_low * half % MOD
        inv += (high_cnt - active_sum_high)
        inv += active_sum_high * half % MOD
        inv %= MOD
        ans += inv
        ans %= MOD
    return ans

N, K = map(int, readline().split())
A = np.array(read().split(), np.int64)

print(main(K, A))

Submission status: Accepted

Solution code:
class SegmentTree:
    def __init__(self, data, default=0, func=max):
        """initialize the segment tree with data"""
        self._default = default
        self._func = func
        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()

        self.data = [default] * (2 * _size)
        self.data[_size:_size + self._len] = data
        for i in reversed(range(_size)):
            self.data[i] = func(self.data[i + i], self.data[i + i + 1])

    def __delitem__(self, idx):
        self[idx] = self._default

    def __getitem__(self, idx):
        return self.data[idx + self._size]

    def __setitem__(self, idx, value):
        idx += self._size
        self.data[idx] = value
        idx >>= 1
        while idx:
            self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
            idx >>= 1

    def __len__(self):
        return self._len

    def query(self, start, stop):
        """func of data[start, stop)"""
        start += self._size
        stop += self._size

        res_left = res_right = self._default
        while start < stop:
            if start & 1:
                res_left = self._func(res_left, self.data[start])
                start += 1
            if stop & 1:
                stop -= 1
                res_right = self._func(self.data[stop], res_right)
            start >>= 1
            stop >>= 1

        return self._func(res_left, res_right)

    def __repr__(self):
        return "SegmentTree({0})".format(self.data)

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)
 
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

n, k = map(int, input().split())
p = list(map(lambda x: int(x) - 1, input().split()))

out = 0
mod = 998244353

mult_r = (k-1) * modinv(k, mod)
mult_inv = modinv(mult_r, mod)
mult = 1
inv = 1

seg = SegmentTree([0] * n, func = lambda x,y: x+y)
seg2 = SegmentTree([0] * n, func = lambda x,y: x+y)

for i in range(n):

    if i >= k:
        mult *= mult_r
        mult %= mod

        inv *= mult_inv
        inv %= mod

    expected_above = (seg.query(p[i], n) * mult) % mod
    expected_below = (seg.query(0,p[i]) * mult) % mod

    tot_above = seg2.query(p[i], n)
    #tot_below = seg2.query(0, p[i])

    out += tot_above - modinv(2, mod) * (expected_above)
    out += modinv(2, mod) * (expected_below)
    out %= mod

    seg[p[i]] = inv
    seg2[p[i]] = 1
print(out)
#print((modinv(2, mod) * dout) % mod)

Submission status: Accepted

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

mod=998244353

class BIT:
	def __init__(self,n):
		self.n=n
		self.buf=[0]*n
	
	def add(self,i,v):
		buf=self.buf
		while i<n:
			buf[i]+=v
			if buf[i]>=mod:
				buf[i]-=mod
			i+=(i+1)&(-i-1)
	
	def get(self,i):
		buf=self.buf
		res=0
		while i>=0:
			res+=buf[i]
			if res>=mod:
				res-=mod
			i-=(i+1)&(-i-1)
		return res
	
	def rng(self,b,e):
		res=self.get(e-1)-self.get(b)
		if res<0:
			res+=mod
		return res

n,k=map(int,readline().split())
p=list(map(int,readline().split()))
for i in range(n):
	p[i]-=1

ans=0

bit=BIT(n)
for i in range(n):
	ans+=i-bit.get(p[i])
	bit.add(p[i],1)

z=pow(2,mod-2,mod);
w=1
winv=1
rem=(k-1)*pow(k,mod-2,mod)%mod
reminv=pow(rem,mod-2,mod)

bit=BIT(n)
for i in range(n):
	lw=bit.get(p[i])
	up=bit.rng(p[i],n)
	dif=(lw-up+mod)%mod
	ans=(ans+dif*w*z)%mod
	bit.add(p[i],winv)
	if i>=k-1:
		w=w*rem%mod
		winv=winv*reminv%mod

print(ans)