题目概述

ACL Contest 1E

解题报告

神仙转化题我根本做不来……我又来翻译题解了。

按顺序random_shuffle可以转化为以下形式：

• 有一个数组 $A$ ，刚开始有排列 $p$ 中 $[1,K]$ 的元素，还有一个空的数组 $B$ 。
• 第 $i$ 次操作时，从 $A$ 中随机选出一个元素插入 $B$ 中。
• 第 $i$ 次操作后，如果 $p_{i+K}$ 存在，则将 $p_{i+K}$ 加入 $A$ 中。
• 求最后数组 $B$ 中的逆序对个数。

感性理解一下这种方式和原来的方式效果是一样的。我们定义 $f(i)=\max\{i-K,0\}$ 表示 $i$ 加入 $A$ 的时间。

那么我们考虑 $i$ 和 $j$ 产生逆序对的情况（ $i<j$ ）：

• $p_i<p_j$ ，那么 $i,j$ 必须交换过位置，前提条件是 $i,j$ 同时出现在了 $A$ 数组中。

  令 $p={K-1\over K}$ ，由于 $i$ 在 $j$ 加入之前一直在 $A$ 中，因此概率为 $p^{f(j)-f(i)}$ 。

  $i,j$ 同时出现在 $A$ 之后，显然 $i,j$ 交换位置的概率为 $1\over 2$ 。

  因此概率为 $p^{f(j)-f(i)}\over 2$ 。

• $p_i>p_j$ ，那么 $i,j$ 没有交换过位置，显然概率为 $1-{p^{f(j)-f(i)}\over 2}$ 。

所以用树状数组维护就行了。

示例程序

#include<cstdio>
using namespace std;
typedef long long LL;
const int maxn=200000,MOD=998244353,INV2=MOD+1>>1;

int n,K,a[maxn+5],ans;
int pw[maxn+5],INV[maxn+5],c[2][maxn+5];

#define ADD(x,y) (((x)+(y))%MOD)
#define MUL(x,y) ((LL)(x)*(y)%MOD)
int Pow(int w,int b) {int s=1;while (b) {if (b&1) s=MUL(s,w);w=MUL(w,w);b>>=1;}return s;}
void Insert(int *c,int x,int y) {for (int i=x;i<=n;i+=i&-i) c[i]=ADD(c[i],y);}
int Sum(int *c,int x) {int sum=0;for (int i=x;i;i-=i&-i) sum=ADD(sum,c[i]);return sum;}
int main(){
    scanf("%d%d",&n,&K);int p=MUL(K-1,Pow(K,MOD-2));
    pw[0]=1;for (int i=1;i<=n;i++) pw[i]=MUL(pw[i-1],p);
    p=Pow(p,MOD-2);INV[0]=1;for (int i=1;i<=n;i++) INV[i]=MUL(INV[i-1],p);
    for (int i=1,x;i<=n;i++){
        scanf("%d",&x);
        int F=i>K?i-K:0,pre=Sum(c[1],x-1),suf=ADD(Sum(c[1],n),MOD-Sum(c[1],x));
        ans=ADD(ans,Sum(c[0],n)-Sum(c[0],x));
        ans=ADD(ans,MOD-MUL(pw[F],suf));
        ans=ADD(ans,MUL(pw[F],pre));
        Insert(c[0],x,1);Insert(c[1],x,MUL(INV[F],INV2));
    }
    printf("%d\n",ans);return 0;
}