← 返回题目列表

Codeforces · 1096/F

F. 反转预期

中文机器翻译题面 查看原题

大小 $$$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} \pmod {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} \pmod {998244353}$$$ 的值。

示例

输入 #1

3
3 -1 -1

输出 #1

499122179

输入 #2

2
1 2

输出 #2

0

输入 #3

2
-1 -1

输出 #3

499122177

注意

在第一个示例中,可能有两种有效排列:

- $$$[3, 1, 2]$$$ — $$$2$$$ 反转;
- $$$[3, 2, 1]$$$ — $$$3$$$ 反转。

预期值为 $$$\frac{2 \cdot 1 + 3 \cdot 1}{2} = 2.5$$$。

在第二个示例中,不存在 $$$-1$$$,因此唯一有效的排列是可能的 - 给定的排列。它有 $$$0$$$ 反转。

在第三个示例中,有两种有效排列 - 一种具有 $$$0$$$ 反转,一种具有 $$$1$$$ 反转。