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

Solution (Python):
import sys
readline = sys.stdin.readline

class BIT:
    
    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)

Solution (Python):
class BIT: 
    __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): 
        s = 0; i += 1
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def range_sum(self,l,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):
        
        
        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




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 
pinv = pow(prob,MOD-2,MOD)
val = pinv*inv2%MOD 
rate = prob 
for j in range(k,n):
    
    pj = p[j]-1
    v = b.get_sum(pj)
    ans += v*rate%MOD
    ans %= MOD

    
    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)

Solution (Python):
class BIT: 
    __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): 
        s = 0; i += 1
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def range_sum(self,l,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):
        
        
        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




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)
    
    ans += v*inv%MOD*bunbo%MOD
    ans %= MOD
    

    x = i - num.get_sum(pi)
    w = x - (tot-v)*inv%MOD*bunbo%MOD
    
    
    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)

Solution (Python):
class SegmentTree():
    def __init__(self, init, unit, f):
        self.unit = unit
        self.f = f
        if type(init) == int:
            self.n = init
            
            self.X = [unit] * (self.n * 2)
        else:
            self.n = len(init)
            
            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)

Solution (Python):
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)
    
    
    
    
    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))
        
        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))

Solution (Python):
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)
    

    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)

Solution (Python):
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)