AT_abc380_g 题解

如你所见，这是一道 diff 为 1995 的题目，看上去十分困难。

你十分惊慌，恐怕这道题你根本就无法做出来，马上就要面临着 rating -114 的到来。

你冷静地思考了一会，发现这是你最擅长的逆序对题目，你逐渐有了一些自信。

你发现如果把序列分成三段：[1,i-1],[i,i+k-1],[i+k,n]，那么三段之间互相的逆序对影响不会改变，设总的逆序对数量为 s，当前长度为 k 的区间里的逆序对数量为 t，则只要求出 s-t，再加上这段区间的期望逆序对数量，最后除以 n-k+1 就好了。

前面这一步可以用树状数组快速解决，但是区间的期望逆序对数量该如何求出？

在耀眼的光芒中，你看见了可爱的 lxy，她只给了你六个字符 CF749E，让你自己领会。

在艰难的探索中，你终于发现，因为两个数形成逆序对的概率是 \frac{1}2，所以 \frac{1}2C_n^2 就是长度为 n 的排列的期望逆序对数。

你非常高兴，很快就打出了一份代码，它十分的正确，仅一遍就通过了样例，并获得了一个绿色的 AC。

#include<bits/stdc++.h>
#define int long long
#define N 200005
using namespace std;
const int mod=998244353;
int n,k,a[N],sum,now,ans;
struct BIT{
    int c[N];
    void add(int x,int k){while(x<=n)c[x]+=k,x+=x&-x;}
    int ask(int x){int ans=0;while(x)ans+=c[x],x-=x&-x;return ans;}
    void clear(){memset(c,0,sizeof(c));}
}A;
int inv(int x,int y=mod-2){
    int ans=1;
    while(y){
        if(y&1)ans=ans*x%mod;
        x=x*x%mod;y>>=1;
    }
    return ans;
}
signed main(){
    cin>>n>>k;
    for(int i=1;i<=n;++i)cin>>a[i];
    for(int i=n;i>=1;--i)sum+=A.ask(a[i]),A.add(a[i],1);
    A.clear();
    for(int i=k;i>=1;--i)now+=A.ask(a[i]),A.add(a[i],1);
    ans=sum-now;
    for(int i=1;i<=n-k;++i){
        A.add(a[i],-1);
        now-=A.ask(a[i]);now+=A.ask(n)-A.ask(a[i+k]);
        A.add(a[i+k],1);ans=(ans+sum-now)%mod;
    }
    cout<<(ans*inv(n-k+1)+k*(k-1)%mod*inv(4))%mod;
    return 0;
}

你醒过来，原来这一切都是梦。

你根本就没有看 G，而是被 F 卡了半个多小时，注定只能获得一个失败的青色 perf。