题目大意：
给定\(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;
}