ouuan 的博客

ouuan 的博客

题解 CF1096F 【Inversion Expectation】

posted on 2018-12-29 10:28:51 | under 题解 |

逆序对分为四种:

  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]$ 。

参考代码

#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;
}