数列のうち \(P_L,P_{L+1},\dots,P_R\) を一様ランダムにシャッフルした場合、転倒数の期待値がどうなるか考察しましょう。

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

要素 \(P_i, P_j\) ( \(i<j\) ) の操作後の位置関係について考えます。

• \(P_i\) がブロック \(X\) 、 \(P_j\) がブロック \(X\) に属する時 … 操作後も必ず \(P_i\) の後に \(P_j\) がある。
• \(P_i\) がブロック \(X\) 、 \(P_j\) がブロック \(Y\) に属する時 … 操作後も必ず \(P_i\) の後に \(P_j\) がある。
• \(P_i\) がブロック \(X\) 、 \(P_j\) がブロック \(Z\) に属する時 … 操作後も必ず \(P_i\) の後に \(P_j\) がある。
• \(P_i\) がブロック \(Y\) 、 \(P_j\) がブロック \(Y\) に属する時 … 操作後、 \(1/2\) の確率で \(P_i\) の後に \(P_j\) が、 \(1/2\) の確率で \(P_j\) の後に \(P_i\) がある。
• \(P_i\) がブロック \(Y\) 、 \(P_j\) がブロック \(Z\) に属する時 … 操作後も必ず \(P_i\) の後に \(P_j\) がある。
• \(P_i\) がブロック \(Z\) 、 \(P_j\) がブロック \(Z\) に属する時 … 操作後も必ず \(P_i\) の後に \(P_j\) がある。

つまり、ブロック \(Y\) にある \(2\) 要素間以外の位置の前後関係は保存され、ブロック \(Y\) は一様ランダムにシャッフルされます。
この議論から、転倒数の期待値は (元の \(P\) の転倒数) \(-\) (元の \(P_L,P_{L+1},\dots,P_R\) の転倒数) \(+\) \(((_{R-L+1}C_2)/2)\) であることがわかります。

あとは、全ての \(1 \le i \le N-K+1\) について \(P_i,P_{i+1},\dots,P_{i+K-1}\) の転倒数が求められればこの問題に正解できます。

これは以下のように求められます。

• まず、 \(P_1,P_2,\dots,P_K\) の転倒数を求め、 \(I\) とする。
• その後、 \(i=K+1,K+2,\dots,N\) について以下を繰り返す。
  • \(I\) から \(P_{i-K+1},P_{i-K+2},\dots,P_{i-1}\) に含まれる \(P_{i-K}\) 以下の要素の個数を減算。
  • その後、 \(I\) に \(P_{i-K+1},P_{i-K+2},\dots,P_{i-1}\) に含まれる \(P_i\) 以上の要素の個数を加算。
  • この時点での \(I\) が \(P_{i-K+1},P_{i-K+2},\dots,P_i\) の転倒数である。

(Segment Tree などを利用して) 区間和クエリを処理することができれば、上記の求値が実現できます。

実装例 (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;
}