CF1081G Mergesort Strikes Back

题目大意：

给定\(n\)，\(k\)，\(mod\)，求随机排列在\(k\)层归并排序下逆序对的期望。

题解

考虑这\(k\)层归并会把序列分成若干个块。

这些块内的顺序是原序列的相对顺序，我们要把这些序列归并起来。

考虑一个块内，每对元素都会有\(\frac{1}{2}\)的概率成为一个逆序对.

所以每个块的贡献就是\(\binom{n}{2}\frac{1}{2}\)。

再考虑块之间的贡献，对于两个元素不在一个块内，考虑这两个元素到它们的块头的序列。如果这两个序列的最大值是这两个元素之一，那么它们肯定不会成为逆序对(思考归并排序的过程)，否则它们的位置关系就和它们本身无关了，那么它们成为逆序对的概率还是\(\frac{1}{2}\)，最后就是\(\frac{i+j-2}{2*(i+j)}\)

所以我们枚举每种块的长度值算一下就好了。

代码

#include<bits/stdc++.h>

#define N 100009

using namespace std;

typedef long long ll;

int n,k,mod;

ll inv[N],sum[N],ans;

map<int,int>tong;

map<int,int>::iterator it1,it2;

inline ll rd(){

  ll x=0;char c=getchar();bool f=0;

  while(!isdigit(c)){if(c=='-')f=1;c=getchar();}

  while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}

  return f?-x:x;

}

inline ll power(ll x,ll y){

    ll ans=1;

    while(y){

        if(y&1)ans=ans*x%mod;

        x=x*x%mod;

        y>>=1;

    }

    return ans;

}

inline void MOD(ll &x){x=x>=mod?x-mod:x;}

inline ll C(ll n){return n*(n-1)/2%mod;}

inline void solve(int l,int r,int k){

    if(k==1||l==r){tong[r-l+1]++;return;}

    int mid=(l+r)>>1;

    solve(l,mid,k-1);solve(mid+1,r,k-1);

}

inline ll calc(int a,int b){

    ll ans=1ll*a*b%mod*inv[2]%mod;

    for(int i=1;i<=a;++i)MOD(ans=ans-(sum[i+b]-sum[i])+mod);

    return ans;

}

int main(){

    n=rd();k=rd();mod=rd();

    for(int i=1;i<=n;++i)inv[i]=power(i,mod-2),MOD(sum[i]=sum[i-1]+inv[i]);

    solve(1,n,k);

    for(it1=tong.begin();it1!=tong.end();++it1){

        MOD(ans+=C(it1->first)*inv[2]%mod*it1->second%mod);

        MOD(ans+=C(it1->second)*calc(it1->first,it1->first)%mod);

    }

    for(it1=tong.begin();it1!=tong.end();++it1)

        for(it2=tong.begin();it2!=tong.end();++it2){

          if(it1->first<=it2->first)break;

          MOD(ans+=1ll*it1->second*it2->second%mod*calc(it1->first,it2->first)%mod);

        }

    cout<<ans;

    return 0;

}

巴特西

CF1081G Mergesort Strikes Back

题目大意：

题解

代码

最新文章

热门文章