CF1753C Wish I Knew How to Sort

· · 题解

写篇题解纪念一下这道因为赛时打 mc 而不够时间写的题

最终单调不降的目标序列肯定是 00...00111...111，交换过程就是以中间的 0 和 1 为分界线，左边的 1 全部移动到右边，右边的 0 全部移动到左边，根据期望线性性质，我们可以单独考虑每一次操作，最后将每次操作的期望值加起来即可。

设当前分界线左边有 i 个 1，则分界线右边会有 i 个 0，交换一次左边的 1 和右边的 0 的概率为：

\frac{i^2}{\binom{n}{2}}

而期望是概率的倒数，因此最终我们要求的便是：

\sum\limits_{i=1}^k \frac{\binom{n}{2}}{i^2}

其中 k 是一开始分界线左边的 1 数量（右边的 0 数量）

然后就完力（喜）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+50;
const ll mod=998244353;
int n,a[N],cnt,k,t;
ll Pow(ll a,ll b)
{
    ll ans=1ll,base=a%mod;
    while(b){
        if(b&1) ans*=base,ans%=mod;
        base*=base,base%=mod;
        b>>=1;
    }
    return ans;
}
void Wish()
{
    cnt=0,k=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]),cnt+=(a[i]==0);//计算分界线
    for(int i=1;i<=cnt;i++){
        if(a[i]) k++;
    }
    ll ans=0;
    for(int i=1;i<=k;i++){//计算答案
        ans+=1ll*n*(n-1)%mod*Pow(2ll*i*i,mod-2)%mod;
        ans%=mod;
    }
    printf("%lld\n",ans);
}
int main()
{
    scanf("%d",&t);
    while(t--) Wish();
    return 0;
}