题解 CF1096F 【Inversion Expectation】

ouuan

2018-12-29 10:28:51

Solution

逆序对分为四种: 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; } ```