ACL001E Shuffle Window

题面

简化题意

给定一个排列 $p_{1...n}$ 和一个整数 $K$，进行如下操作 $n-K+1$ 次：

• 第 $i$ 次操作时，随机打乱 $p_{i},p_{i+1},p_{i+2},\cdots,p_{i+K-1}$ 这些数字。

求操作完成后序列逆序对数的期望，对 $998244353$ 取模。

$n\leq 2\times10^5$。

题解

每次随机打乱一个区间长得很丑，我们发现相邻两个操作的区间是相邻的。考虑转化一下操作的形式：

1. 初始时有一个空序列 $a$ 和一个集合 $S = \{p_i | 1\leq i\leq K\}$。
2. 第 $i$ 次操作时，随机选择 $S$ 中的一个数字加入到 $a$ 序列的末尾，然后把 $p_{i+K}$ 加入到 $S$ 中。
3. 将 $S$ 中剩余的数字随机打乱，依次加入 $a$ 末尾。

于是我们可以求出 $f_i = \max\{0,i-K\}$ 表示 $p_i$ 会在第几次操作中加入到 $S$ 内。下面考虑计算某两个数 $p_i,p_j$ 的相对位置改变的概率。不妨设 $i<j$。

当两个数都在 $S$ 内时，概率等价于 $p_j$ 比 $p_i$ 先选的概率，显然为 $\frac{1}{2}$。而这两个数能同时出现在 $S$ 内的概率为 $(\frac{K-1}{K})^{f_{j}-f_{i}}$。因此两数交换的概率为 $\frac{1}{2}(\frac{K-1}{K})^{f_{j}-f_{i}}$。

于是我们先求出原序列有多少逆序对，再求出逆序对的期望变化量即可。前者一个 BIT 就可以了，求后者的关键在于对于满足 $i<j$ 且 $a_{i}>a_{j}$（或反过来）的下标数对 $i,j$，求 $(\frac{K-1}{K})^{f_{j}-f_{i}}$ 的和。也是一个 BIT 就可以了。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
bool Begin;
const int max_n=200005,mod=998244353,iv2=499122177;
inline int read(){
    int x=0;bool w=0;char c=getchar();
    while(c<'0' || c>'9') w|=c=='-',c=getchar();
    while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return w?-x:x;
}
inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10^48);
}
inline int Plus(int &x,int y){return x=(x+y>=mod?x+y-mod:x+y);}
inline int Minu(int &x,int y){return x=(x<y?x-y+mod:x-y);}
inline int MOD(int x){return x>=mod?x-mod:x;}
inline int mi(int a,int p=mod-2){
    int res=1;
    while(p){
        if(p&1) res=res*a%mod;
        a=a*a%mod,p>>=1;
    }
    return res;
}

int n,K,P,a[max_n],ans;

struct BIT{
    int a[max_n];
    inline void add(int i,int x){
        for(;i<=n;i+=i&-i) Plus(a[i],x);
    }
    inline int pre(int i){
        int res=0;
        for(;i;i-=i&-i) Plus(res,a[i]);
        return res;
    }
    inline int ask(int l,int r){
        return MOD(pre(r)-pre(l-1)+mod);
    }
}bit1,bit2;

int mip[max_n],inv[max_n],f[max_n];

bool End;
#define File ""
signed main(){
    // #ifndef ONLINE_JUDGE
    // freopen(File ".in","r",stdin);
    // freopen(File ".out","w",stdout);
    // #endif
    n=read(),K=read(),P=(K-1)*mi(K)%mod;
    mip[0]=inv[0]=1;
    for(int i=1;i<=n;++i)
        mip[i]=mip[i-1]*P%mod;
    inv[n]=mi(mip[n]);
    for(int i=n-1,ip=mi(P);i;--i)
        inv[i]=inv[i+1]*P%mod;
    iota(f+K+1,f+n+1,1);
    for(int i=1;i<=n;++i){
        a[i]=read();
        ans=MOD((ans+mip[f[i]]*bit1.pre(a[i])-mip[f[i]]*bit1.ask(a[i],n)+bit2.ask(a[i],n))%mod+mod);
        bit1.add(a[i],iv2*inv[f[i]]%mod);
        bit2.add(a[i],1);
    }
    write(ans);
    return 0;
}