题解 CF1096F 【Inversion Expectation】
ouuan
2018-12-29 10:28:51
逆序对分为四种:
1. 给定的数之间的逆序对。
2. 不确定的数之间的逆序对。
3. 给定的数在不确定的数左边的逆序对。
4. 给定的数在不确定的数右边的逆序对。
## 一、给定的数之间的逆序对
用树状数组/归并排序之类的求即可。
## 二、不确定的数之间的逆序对
任取两个不确定的数,为逆序对的概率为 $\frac1 2$ 。记总的 $-1$ 数量为 $\rm tot$,那么总期望为 $\frac{\rm{tot}\times(\rm{tot}-1)}4$ 。
## 三、给定的数在不确定的数左边的逆序对
对于每个给定的数,记总的 $-1$ 数量为 $\rm tot$,没有出现在给定的数中的数(也就是不确定的数可以取的值)里有 $\rm low$ 个比它小,那么每个在它右边的不确定的位置比它小的概率为 $\frac{\rm low}{\rm tot}$,在它右边有 $r$ 个位置不确定,这个给定的数贡献就是 $\frac{r\times\rm{low}}{\rm tot}$ 。
## 四、给定的数在不确定的数右边的逆序对
与上面一种情况类似,对于每个给定的数,记总的 $-1$ 数量为 $\rm tot$,没有出现在给定的数中的数(也就是不确定的数可以取的值)里有 $\rm high$ 个比它大,那么每个在它左边的不确定的位置比它大的概率为 $\frac{\rm high}{\rm tot}$,在它左边有 $l$ 个位置不确定,这个给定的数贡献就是 $\frac{l\times\rm{high}}{\rm tot}$ 。
## 关于三、四的具体实现
$l$ 和 $r$ 可以用前缀和计算。
预处理出小于等于 $i$ 的数中有 $\mathrm{cnt}[i]$ 个数给定,那么 $\mathrm{low}[i]=i-\mathrm{cnt}[i]$,$\mathrm{high}[i]=\mathrm{tot}-\mathrm{low}[i]$ 。
## 参考代码
```cpp
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
const int N=200010;
const int M=998244353;
int qpow(int x,int y); //快速幂用于求逆元
void add(int p,int x); //树状数组
int query(int p);
int n,a[N],l[N],r[N],BIT[N],cnt[N],ans;
int main()
{
int i,inv;
scanf("%d",&n);
for (i=1;i<=n;++i)
{
scanf("%d",a+i);
if (a[i]!=-1) ++cnt[a[i]];
l[i]=l[i-1]+(a[i]==-1);
}
for (i=1;i<=n;++i)
{
cnt[i]+=cnt[i-1]; //求给定的数个数的前缀和
}
inv=qpow(4,M-2);
ans=(ll)l[n]*(l[n]-1)%M*inv%M; //第二种逆序对
inv=qpow(l[n],M-2); //用l[n]代表tot,求出tot的逆元
for (i=n;i>=1;--i)
{
r[i]=r[i+1]+(a[i]==-1);
if (a[i]!=-1)
{
ans=(ans+query(a[i]))%M; //第一种逆序对
add(a[i],1);
ans=(ans+(ll)r[i]*(a[i]-cnt[a[i]])%M*inv%M)%M; //第三种逆序对
ans=(ans+(ll)l[i]*(l[n]-a[i]+cnt[a[i]])%M*inv%M)%M; //第四种逆序对
}
}
printf("%d",ans);
return 0;
}
int qpow(int x,int y)
{
int out=1;
while (y)
{
if (y&1) out=(ll)out*x%M;
x=(ll)x*x%M;
y>>=1;
}
return out;
}
void add(int p,int x)
{
for (;p<=n;p+=(p&-p))
{
BIT[p]+=x;
}
}
int query(int p)
{
int out=0;
for (;p>0;p-=(p&-p))
{
out+=BIT[p];
}
return out;
}
```