When \(P_L,P_{L+1},\dots,P_R\) is shuffled, how the inversion number will change?

• Block \(X\) … \(P_1,P_2,\dots,P_{L-1}\)
• Block \(Y\) … \(P_L,P_{L+1},\dots,P_R\)
• Block \(Z\) … \(P_{R+1},P_{R+2},\dots,P_N\)

Consider the relative position of the elements \(P_i\) and \(P_j\) \(i<j\) after the shuffle.

• If \(P_i\) belongs to block \(X\) and \(P_j\) to block \(X\) … \(P_i\) still comes earlier than \(P_j\) after the shuffle.
• If \(P_i\) belongs to block \(X\) and \(P_j\) to block \(Y\) … \(P_i\) still comes earlier than \(P_j\) after the shuffle.
• If \(P_i\) belongs to block \(X\) and \(P_j\) to block \(Z\) … \(P_i\) still comes earlier than \(P_j\) after the shuffle.
• If \(P_i\) belongs to block \(Y\) and \(P_j\) to block \(Y\) … After the shuffle, \(P_i\) comes earlier than \(P_j\) with the probability \(1/2\), and \(P_j\) comes earlier than \(P_i\) with the probability \(1/2\).
• If \(P_i\) belongs to block \(Y\) and \(P_j\) to block \(Z\) … \(P_i\) still comes earlier than \(P_j\) after the shuffle.
• If \(P_i\) belongs to block \(Z\) and \(P_j\) to block \(Z\) … \(P_i\) still comes earlier than \(P_j\) after the shuffle.

Thus, the relative position of two elements are preserved unless they are both in block Y, while block Y is shuffled uniformly at random.
By this discussion, it turns out that the expected inversion number is (the inversion number of original \(P\)) \(-\) (the inversion number of original \(P_L,P_{L+1},\dots,P_R\)\(+\) \(((_{R-L+1}C_2)/2)\)).

All that left is to find the inversion number of \(P_i,P_{i+1},\dots,P_{i+K-1}\) for all \(1 \le i \le N-K+1\).

This can be found as follows:

• First, find the inversion number of \(P_1,P_2,\dots,P_K\), denoting it by \(I\).
• Then, for \(i=K+1,K+2,\dots,N\), repeat the following:
  • Subtract from \(I\) the number of elements less than \(P_{i-K}\) among \(P_{i-K+1},P_{i-K+2},\dots,P_{i-1}\).
  • Then, add to \(I\) the number of elements greater than \(P_{i-K+1},P_{i-K+2},\dots,P_{i-1}\) among \(P_{i-K+1},P_{i-K+2},\dots,P_{i-1}\).
  • At this point, \(I\) is the inversion number of \(P_{i-K+1},P_{i-K+2},\dots,P_i\).

This can be evaluated by processing segment-sum queries (using a data structure like a segment tree).

Sample code (C++):

#include<bits/stdc++.h>
#include<atcoder/segtree>

using namespace std;
using namespace atcoder;

#define mod 998244353
#define inv2 499122177

long long op(long long a,long long b){
  if((a+b)>=mod){
    return (a+b)-mod;
  }
  return (a+b);
}
long long e(){
  return 0;
}

long long power(long long a,long long b){
  long long x=1,y=a;
  while(b>0){
    if(b&1ll){
      x=(x*y)%mod;
    }
    y=(y*y)%mod;
    b>>=1;
  }
  return x%mod;
}

long long modular_inverse(long long n){
  return power(n,mod-2);
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  long long n,k;
  cin >> n >> k;
  vector<long long> p(n);
  for(auto &nx : p){
    cin >> nx;
    nx--;
  }

  long long bas=0;
  {
    segtree<long long,op,e> seg(n);
    for(long long i=0;i<n;i++){
      bas+=seg.prod(p[i],n);
      seg.set(p[i],1);
    }
  }

  long long res=0;
  long long sub=0;
  long long add=((k*(k-1))/2)%mod; add*=inv2; add%=mod;

  segtree<long long,op,e> seg(n);
  for(long long i=0;i<k;i++){
    sub+=seg.prod(p[i],n); sub%=mod;
    seg.set(p[i],1);
  }

  for(long long i=k;i<=n;i++){
    long long cur=(mod+bas-sub+add)%mod;
    res+=cur; res%=mod;
    if(i==n){break;}

    seg.set(p[i-k],0);
    sub+=(mod-seg.prod(0,p[i-k])); sub%=mod;
    sub+=seg.prod(p[i],n); sub%=mod;
    seg.set(p[i],1);
  }

  res*=modular_inverse(n-k+1); res%=mod;
  cout << res << "\n";
  return 0;
}