Mergesort Strikes Back

Mergesort Strikes Back

题意

给你两个正整数 \(n,k\)，问长度为 \(n\) 的随机排列，做深度为 \(k\) 的归并排序（\(k=1\) 就是不排）后，期望逆序对个数。对给定素数取模。

思路

首先如果 \(k \ge \log n\) 就可以排好序，逆序对个数为 \(0\)。

否则，假设排列给定，那么最后一次分治形成的若干个长度为 \(len\) 或者 \(len+1\) 的区间内相对顺序是不变的，因此我们可以先算出这些区间的逆序对。对于四个随机的排列，一个长度为 \(len\) 的区间的逆序对个数期望是，对于任意一对数字，都有 \(\frac{1}{2}\) 的概率正序，\(\frac{1}{2}\) 的概率逆序，所以期望逆序对个数是 \(\frac{len(len-1)}{4}\)。

然后我们探寻归并排序的性质，计算不同区间的逆序对个数。

考虑一个合并的过程。两个不一定有序的序列 \(A,B\)，先比较 \(a_1,b_1\) 的大小，若 \(a_1<b_1\)，则插入 \(a_1\)，同时 \(a_1\) 后面跟着的若干个比 \(a_1\) 小的 \(a_i\) 也会插入，假设一共插入了 \(j\) 个数字。然后再比较 \(a_{j+1}\) 和 \(b_1\)，以此类推。

我们发现其实就是按照前缀最大值把 \(A,B\) 分成若干块，然后按照前缀最大值对这些块排序。

我们计算逆序对个数，考虑 \((a_i,b_j)\) 的贡献。设 \(a_{1 \sim i},b_{1 \sim j}\) 的最大值为 \(x\)，假设 \(x\) 是 \(a_i\)，那么 \(a_i\) 一定会放在这两个前缀的所有数的最后，因此没有逆序对，\(b_j\) 是最大值情况同理。

若 \(x\) 不是 \(a_i\) 或 \(b_j\)，如果 \(x\) 在 \(a_{1 \sim i-1}\)，则 \(x\) 后面那一坨，当然包括了 \(a_i\) 会放到 \(b_j\) 的后面，因为 \(A,B\) 都是随机的，所以有 \(\frac{1}{2}\) 的概率 \(a_i > b_j\)，同样 \(\frac{1}{2}\) 的概率 \(a_i < b_j\)，若 \(x\) 在 \(b_{1 \sim j-1}\) 同理。则逆序对个数期望是 \(\frac{1}{2}\) 的。

因此对于 \(a_i,b_j\)，有 \(\frac{2}{i+j}\) 的概率没有逆序对，有 \(\frac{i+j-2}{i+j}\) 的概率有 \(\frac{1}{2}\) 的逆序对，所以我们要计算 \(\sum_i \sum_j \frac{i+j-2}{2(i+j)}\)。

变成：

\[\sum_{i=1}^{len_A} \sum_{j=i+1}^{i+len_B} \frac{j-2}{2j} \]

求这个东西是 \(len^2\) 的，\(O(len)\) 预处理 \(\frac{x-2}{2x}\) 的前缀和就可以变成 \(O(len)\) 了。如果你的预处理每次都要求逆元，可能时间是带 \(\log\) 的。

实际上，因为本质上我们是在按照每一小块的前缀最大值排序，所以我们可以抛弃这个归并的过程，计算任意两个小块的贡献。

由于小块的长度只有两种，所以最终复杂度是 \(O(len)\) 的，常数其实应该也不算很大。

题目的归并分治时是令 \(mid=\lfloor \frac{l+r}{2} \rfloor\)，把 \([l,r]\) 分成 \([l,mid]\) 和 \([mid+1,r]\) 的，和我平常写的线段树一样。

计算每种长度的一对小块有多少个，一个不用动脑的做法是类似于 CDQ 分治统计。当然这样做是带 $\log $ 的，显然有更优美的做法。

AC Code

思维难度较低的常数巨大写法。

#include<bits/stdc++.h>
//#define LOCAL
#define sf scanf
#define pf printf
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
using namespace std;
typedef long long ll;
const int N=1e5+7;
int n,k,mod;
ll pre[N];
ll add(ll a,ll b) {return a+b>=mod?a+b-mod:a+b;}
ll ksm(ll a,ll b) {ll s=1;while(b) {if(b&1) s=s*a%mod;a=a*a%mod;b>>=1;}return s;
}
void init(int n) {rep(i,3,n) {pre[i]=1ll*(i-2)*ksm(i*2,mod-2)%mod;pre[i]=add(pre[i-1],pre[i]);}
}
int len;
struct node {ll x[4],y[2];node () {memset(x,0,sizeof(x)),memset(y,0,sizeof(y));}
};
node operator + (node a,node b) {a.x[0]+=a.y[0]*b.y[0]%mod;a.x[1]+=a.y[0]*b.y[1]%mod;a.x[2]+=a.y[1]*b.y[0]%mod;a.x[3]+=a.y[1]*b.y[1]%mod;rep(i,0,1) a.y[i]+=b.y[i];rep(i,0,3) a.x[i]+=b.x[i];rep(i,0,1) a.y[i]%=mod;rep(i,0,3) a.x[i]%=mod;return a;
} 
node cal(int l,int r,int k) {if(k==0) {node a;if(r-l+1==len) a.y[0]=1;else a.y[1]=1;return a;}int mid=(l+r)>>1;node ls=cal(l,mid,k-1);node rs=cal(mid+1,r,k-1);return ls+rs;
}
ll ans;
int main(){#ifdef LOCALfreopen("in.txt","r",stdin);
//	freopen("my.out","w",stdout);#endifsf("%d%d%d",&n,&k,&mod);k--;if(k>__lg(n)) {pf("0\n");return 0;}len=n>>k;if(k==0) {pf("%lld\n",1ll*n*(n-1)%mod*ksm(4,mod-2)%mod);return 0;}init(n);node a=cal(1,n,k);ans=add(1ll*len*(len-1)%mod*ksm(4,mod-2)%mod*a.y[0]%mod,1ll*(len+1)*len%mod*ksm(4,mod-2)%mod*a.y[1]%mod);rep(i,1,len) {ans=add(ans,add(pre[i+len],mod-pre[i])*a.x[0]%mod);ans=add(ans,add(pre[i+len+1],mod-pre[i])*a.x[1]%mod);}rep(i,1,len+1) {ans=add(ans,add(pre[i+len],mod-pre[i])*a.x[2]%mod);ans=add(ans,add(pre[i+len+1],mod-pre[i])*a.x[3]%mod);}pf("%lld\n",ans);
}