摘要:考虑随机序列中逆序对的贡献方式

CF1096F Inversion Expectation

题面

题目分析

先考虑序列中原有的数的逆序对个数,这一部分是一定得算进期望.

然后是随机出现的数之间的逆序对个数,对于这些数,相当于随机一个排列,求其中的逆序对个数,那么对于一个数对$( a , b )$,因为是一个排列,所以一定有$a < b$或者$a > b$,它们产生逆序对关系的概率为大的一个在小的一个前面的概率,这个概率无疑是$\frac{1}{2}$,那么对期望的贡献为$\frac{1}{2} \times 1 = \frac{1}{2}$.

设随机出现的数个数为$x$,这一部分的期望为$\frac{x \cdot (x-1)}{4}$.

最后是随机出现的数对原有的数产生的逆序对的个数的期望,可以前缀和处理出随机出现的数中比一个原有的数小的数的数目和这个原有位置之后有多少位置是随机的,设这两个数为$numsuf$和$suf$,那么这种情况对期望的贡献是$\frac{numsuf}{x}\times suf$,前面出现比原有的数大的数同理.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include "iostream"
#include "cstdlib"
#include "cstdio"
#include "cstring"
#include "cmath"
#include "cctype"
#include "ctime"
#include "iomanip"
#include "algorithm"
#include "set"
#include "queue"
#include "map"
#include "stack"
#include "deque"
#include "vector"
#define R register
#define INF 0x3f3f3f3f
#define debug(x) printf("debug:%lld\n",x)
#define debugi(x) printf("debug:%d\n",x)
#define debugf(x) printf("debug:%llf\n",x)
#define endl putchar('\n')
#define lowbit(x) (x&-x)
typedef long long lxl;
const lxl big=200010,p=998244353;
lxl n,sum,x;
lxl ard[big],a[big],t[big],b[big],pre[big],suf[big],prenum[big],sufnum[big];
inline lxl read()
{
char c(getchar());
lxl f(1),x(0);
for(;!isdigit(c);(c=='-')&&(f=-1),c=getchar());
for(;isdigit(c);x=(x<<1)+(x<<3)+(c^48),c=getchar());
return f*x;
}
inline void modify(lxl x,lxl k){for(;x<big;x+=lowbit(x))t[x]+=k;}
inline lxl query(lxl x){lxl sum(0);for(;x;x-=lowbit(x))sum+=t[x];return sum;}
inline lxl FastPow(lxl a,lxl b)
{
lxl sum(1);
for(;b;a=a*a%p,b>>=1)(b&1)&&(sum=sum*a%p);
return sum;
}
inline lxl origin()
{
lxl sum(0);
for(R int i(b[0]);i;--i)
{
sum=(sum+query(b[i]-1))%p;
modify(b[i],1);
}
return sum;
}
int main(void)
{
n=read();
for(R int i(1);i<=n;++prenum[i],++sufnum[i],++i)
{
a[i]=read();
if(~a[i])ard[i]=true,--prenum[a[i]],--sufnum[a[i]],b[++b[0]]=a[i];
else ++x,pre[i]=suf[i]=1;
}
if(!x)
{
printf("%lld\n",origin()%p);
return 0;
}
sum=(sum+2*x*origin()%p)%p,sum=(sum+(x*x*(x-1)/2)%p)%p;
for(R int i(1);i<=n;++i)pre[i]+=pre[i-1],prenum[i]+=prenum[i-1];
for(R int i(n);i;--i)suf[i]+=suf[i+1],sufnum[i]+=sufnum[i+1];
for(R int i(1);i<=n;++i)
if(ard[i])
sum=(sum+2*pre[i]*sufnum[a[i]]%p)%p,
sum=(sum+2*suf[i]*prenum[a[i]]%p)%p;
printf("%lld\n",sum*FastPow(2*x,p-2)%p);
return 0;
}