题意：
对于长度为$n$的排列，在已知一些位的前提下求逆序对的期望
思路：
将答案分为$3$部分
$1.$$-1$与$-1$之间对答案的贡献。由于逆序对考虑的是数字之间的大小关系，故假设$-1$的数量为$cnt$，可以等效成求长度为$cnt$的排列的逆序对期望。设$dp[i]$为长度为$i$的全排列的逆序对期望，有$dp[i]=dp[i-1]+$$\frac{i-1}{2}$，可以理解成在原$dp[i-1]$的基础上，数值$i$对每个长度为$i-1$的排列产生$\sum_{t=1}^{i-1}t$个逆序对，共有$(i-1)!$个排列，所以期望为$\frac{(i-1)!*i*(i-1)}{(2*i!)}$$=\frac{i-1}{2}$，移项后使用累加法可以求出通项为$dp[i]=$$\frac{i*(i-1)}{4}$。
$2.$非$-1$之间对答案的贡献。可以将出现概率看作$1$，所以贡献就是逆序对数量，用树状数组求。
$3.$$-1$与非$-1$之间的贡献。设共有$cnt$个$-1$，考虑每个$a[i]$$\neq$$-1$，设这个$a[i]$它前边$-1$的数量为$nop$，它大的未填的数的数量为$high[a[i]]$，那么$a[i]$对这部分答案的贡献为$\frac{nop*high[a[i]]*(cnt-1)!}{cnt!}$$=$$\frac{nop*high[a[i]]}{cnt}$。比$a[i]$小的数与$a[i]$后边的$-1$构成类似的关系。
代码：
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cassert>
#include <cstring>
#include <iostream>
#include <algorithm>
#define IOS ios::sync_with_stdio(0),cin.tie(0);
#define DBG(x) cerr << #x << " = " << x << endl;
#define PII pair<int,int>
#define FI first
#define SE second
using namespace std;
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
const double eps = 1e-8;
const double pi = acos(-1.0);
void file(){
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
}
namespace BakuretsuMahou{
const int N = 2e5 + 5;
const int inv2 = (mod + 1) / 2;
int n, a[N], vis[N];
int high[N], low[N];
int pre[N], cnt;
LL ans, fac[N];
LL add(LL a, LL b){
return (a+b)%mod;
}
LL mul(LL a, LL b){
return (a*b)%mod;
}
struct BIT{
int c[N];
int lowbit(int x){
return (x)&(-x);
}
void update(int x, int y){
while(x <= n){
c[x] += y;
x += lowbit(x);
}
}
LL query(int x){
LL res = 0;
while(x >= 1){
res += c[x];
x -= lowbit(x);
}
return res;
}
}tree;
LL qpow(LL a, LL b, LL p){
LL res = 1;
while(b){
if(b&1)res = mul(res, a);
a = mul(a, a);
b >>= 1;
}
return res;
}
LL Fermat(LL a, LL p){
return qpow(a, p - 2, p);
}
LL dp(LL x){
return mul(mul(x, x - 1), Fermat(4, mod));
}
void init(){
fac[0] = 1;
for(int i = 1; i < N; i++){
fac[i] = mul(fac[i - 1], i);
}
}
void Explosion(){
init();
scanf("%d", &n);
for(int i = 1; i <= n; i++){
scanf("%d", &a[i]);
if(a[i] != -1){
vis[a[i]] = 1;
ans = add(ans, i - 1 - cnt - tree.query(a[i]));
tree.update(a[i], 1);
}else cnt++, pre[i]++;
pre[i] += pre[i - 1];
}
ans = add(ans, dp(cnt));
LL inv = Fermat(cnt, mod);
for(int i = 2; i <= n; i++)low[i] = low[i - 1] + (vis[i - 1] ^ 1);
for(int i = n - 1; i >= 1; i--)high[i] = high[i + 1] + (vis[i + 1] ^ 1);
for(int i = 1; i <= n; i++){
if(a[i] != -1){
LL nop = pre[i], nos = pre[n] - pre[i];
ans = add(ans, mul(mul(nos, low[a[i]]), inv));
ans = add(ans, mul(mul(nop, high[a[i]]), inv));
}
}
printf("%I64d\n", ans);
}
}
int main(){
//IOS
//file();
BakuretsuMahou::Explosion();
return 0;
}
原文：https://www.cnblogs.com/DuskOB/p/10353091.html