CF1096F Inversion Expectation

一个长度为 $n$ 的排列是一个长度为 $n$ 的数组，其中每个整数 $1$ 到 $n$ 恰好出现一次。对于排列 $p$，一次逆序对定义为一对下标 $(i, j)$，满足 $i > j$ 且 $a_i < a_j$。例如，排列 $[4, 1, 3, 2]$ 包含 $4$ 个逆序对：$(2, 1)$，$(3, 1)$，$(4, 1)$，$(4, 3)$。 现在给定一个长度为 $n$ 的排列 $p$，但其中某些位置上的数字被替换成了 $-1$。我们称“有效排列”为：将这些 $-1$ 替换回 $1$ 到 $n$ 中未出现的数字，使得最终序列是一个长度为 $n$ 的排列。 假设每一种有效排列都等概率地被选中。 请计算最终有效排列中逆序对的期望总数。 可以证明答案可以表示为 $\frac{P}{Q}$，其中 $P$ 和 $Q$ 是非负整数且 $Q \ne 0$。请输出 $P \cdot Q^{-1} \bmod {998244353}$。

第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）——序列的长度。 第二行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$（$-1 \le p_i \le n$，$p_i \ne 0$）——初始序列。 保证所有不等于 $-1$ 的元素两两不同。

输出一个整数，表示最终有效排列中逆序对的期望总数。 可以证明答案可以表示为 $\frac{P}{Q}$，其中 $P$ 和 $Q$ 是非负整数且 $Q \ne 0$。请输出 $P \cdot Q^{-1} \bmod {998244353}$。

在第一个样例中，有两种可能的有效排列： - $[3, 1, 2]$ —— $2$ 个逆序对； - $[3, 2, 1]$ —— $3$ 个逆序对。 期望值为 $\frac{2 \cdot 1 + 3 \cdot 1}{2} = 2.5$。 在第二个样例中，没有 $-1$，因此只有给定的排列本身是有效排列，逆序对数为 $0$。 在第三个样例中，有两种有效排列，一种有 $0$ 个逆序对，一种有 $1$ 个逆序对。 由 ChatGPT 4.1 翻译