AT_abc380_g Another Shuffle Window 题解

题目大意：给定 n,k 和一个长度为 n 的排列，问随机选择一个长度为 k 的区间进行随机打乱，排列的逆序对数的期望。

考虑对每一个长度为 k 的区间分别计算答案。先计算随机打乱的这个区间对其他数的贡献，也就是总逆序对数减去原来区间内的逆序对数。这一部分我们在移动区间的时候用树状数组直接计算即可。然后就是区间内部的贡献，一个长为 m 的区间随机打乱之后，对于所有的 \dfrac{m \times (m-1)}{2} 个二元组，显然都有 \dfrac{1}{2} 的概率构成逆序对，因此答案再加上 \dfrac{k \times (k-1)}{4} 即可。

代码：

#include<bits/stdc++.h>
using namespace std;
inline void rd(){}
template<typename T,typename ...U>
inline void rd(T &x,U &...args){
    char ch=getchar();
    T f=1;x=0;
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    x*=f;rd(args...);
}
const int N=2e5+5,mod=998244353;
int n,k,p[N];
inline int KSM(int x,int n){
    int ans=1;
    while(n){
        if(n&1)ans=1ll*x*ans%mod;
        x=1ll*x*x%mod;
        n>>=1;
    }
    return ans;
}
int t[N];
inline void Add(int x,int v){while(x<=n)t[x]+=v,x+=x&-x;}
inline int Query(int x){int ans=0;while(x)ans+=t[x],x-=x&-x;return ans;}
inline void Insert(int x,int &sum){
    (sum+=(Query(n)-Query(x-1)+mod)%mod)%=mod;
    Add(x,1);
}
inline void Delete(int x,int &sum){
    Add(x,-1);
    (sum+=mod-Query(x))%=mod;
}
signed main(){
    rd(n,k);
    for(int i=1;i<=n;i++)rd(p[i]);
    int now=0,ans=0,sum=0;
    for(int i=1;i<=n;i++)Insert(p[i],sum);
    memset(t,0,sizeof t);
    for(int i=1;i<=k;i++)Insert(p[i],now);
    const int INV=KSM(n-k+1,mod-2),SUM=1ll*(k-1)*k%mod*KSM(4,mod-2)%mod;
    for(int i=1;i+k-1<=n;i++){
        (ans+=INV*(0ll+sum-now+SUM+mod)%mod)%=mod;
        if(i+k-1<n){
            Insert(p[i+k],now);
            Delete(p[i],now);
        }
    }printf("%d\n",ans);
    return 0;
}