做题时间：2022.10.25
\(【题目描述】\)
给定一个长度为 \(n\) 的01序列 \(a\) 和一种操作，你需要用这种操作将序列从小到大排序。操作为：等概率随机选择两个位置 \(i,j(i<j)\)，若 \(a_i>a_j\)，则交换 \(a_i\) 和 \(a_j\)（当 \(a_i\leq a_j\)，交换失败也算一次操作）
求出执行操作的期望次数，对 \(998244353\) 取模
\(【输入格式】\)
第一行一个整数 \(T\) 表示数据组数
每组数据第一行一个整数 \(n\) 表示序列长度
接下来一行 \(n\) 个整数表示序列 \(a\)
\(【输出格式】\)
对于每组数据，输出一行一个整数表示答案
\(【考点】\)
期望、概率
\(【做法】\)
最终单调不降的目标序列肯定是 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;
}