Codeforces 1096F Inversion Expectation
题目链接
http://codeforces.com/contest/1096/problem/F
题目大意
给你一个不完整的 $1$ 到 $n$ 的排列，问期望的逆序对数量为多少。
题目分析
首先考虑一共有多少种可能出现逆序对的地方。第一种是已经确定位置的数之间产生逆序对；第二种是为确定位置的两个数之间产生逆序对，第三种则是未确定位置的数和已经确定位置的数产生逆序对。
设共 $k$ 个位置的数未确定。
对于第一种情况，显然非常的简单，就是个简单的逆序对统计问题，使用树状数组即可维护。
对于第二种情况，求期望也比较简单，任意两个数的组合，成逆序对与不成逆序对的概率是相同的，因此这一种情况产生逆序对的期望是 $\frac{C_{k}^2}{2}$
对于第三种情况，考虑任何其中一个数，那么这个数在任何一个位置出现的概率是 $\frac{1}{k}$，那么它所能组成的逆序对的期望数量就为它在所有位置上产生的逆序对数量的总和再乘以 $\frac{1}{k}$。那么再考虑维护同时全部的数。既然所有的数的期望均需要乘以 $\frac{1}{k}$ ，也就是说统计出来所有位置能产生的逆序对数量总和即可。考虑从已经确定位置的数字入手，那么它能产生逆序对的数量为比它大的未确定位置的数的数量再乘上可能出现在它左边的位置数量，以及，还有比它小的未确定位置的数的数量再乘上可能出现在它右侧的位置数量。这样一来，这一种情况的期望也可以求出来了。
将三者加和，就可以得到答案。
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 2e5 + 5;
long long mod = 998244353;
long long n, m;
long long a[maxn];
bool vis[maxn];
struct btree {
long long tree[maxn];
long long t;
long long lowbit(long long x){
return x & -x;
}
long long sum(long long x){
long long ret = 0;
while(x){
ret += tree[x];
x -= lowbit(x);
}
return ret;
}
long long update(long long x, long long p){
while(x <= n){
tree[x] += p;
x += lowbit(x);
}
return 0;
}
};
long long read(){
long long x;
scanf("%lld", &x);
return x;
}
long long qpow(long long b, long long x){
long long ret = 1;
while(x){
if(x & 1){
ret = ret * b % mod;
}
b = b * b % mod;
x >>= 1;
}
return ret;
}
btree treea;
btree treeb;
vector <long long> vec;
vector <long long> b;
long long query_min(long long x){
long long l = 0, r = (long long)b.size() - 1;
long long mid;
if(b.size() == 0 or b[0] > x){
return 0;
}
while(l + 1 < r){
mid = (l + r) / 2;
if(b[mid] < x){
l = mid;
}else{
r = mid;
}
}
if(b[r] < x){
l = r;
}
return l + 1;
}
int main(){
long long i, j;
long long ans = 0;
long long x = 0, y = 0, ret = 0;
n = read();
for(i=1;i<=n;i++){
a[i] = read();
if(a[i] != -1){
vec.push_back(a[i]);
vis[a[i]] = true;
}
}
for(i=(long long)vec.size()-1;i>=0;i--){
ans = (ans + treea.sum(vec[i])) % mod;
treea.update(vec[i], 1);
}
for(i=1;i<=n;i++){
if(!vis[i]){
b.push_back(i);
}
}
for(i=1;i<=n;i++){
if(a[i] == -1){
y++;
}else{
x = ((long long)b.size() - query_min(a[i])) % mod;
ret = (ret + x * y % mod) % mod;
}
}
y = 0, x = 0;
for(i=n;i>0;i--){
if(a[i] == -1){
y++;
}else{
x = (query_min(a[i])) % mod;
ret = (ret + x * y % mod) % mod;
}
}
y = (long long)b.size() * ((long long)b.size() - 1) % mod * qpow(4, mod - 2) % mod;
ans = (ans + y + ret * qpow((long long)b.size(), mod - 2) % mod) % mod;
printf("%lld\n", ans);
return 0;
}