CF2223B Zhily and Barknights

Zhily 开发了一款名为 Barknights 的游戏，她准备在 3 月 25 日发布一次重大更新。具体来说，她计划为游戏中的每个干员增加一个模块，使他们的能力值乘上模块的能力值。 更新发布后，著名游戏主播 Jily 将会评价各个干员的能力并进行排名。如果某位更早上线的干员的排名高于某位之后上线的干员，就会引发一波“撕逼”风波。 不幸的是，Zhily 不小心打翻了热水壶，损坏了她的电脑，导致所有的模块被随机重新分配。现在 Zhily 想知道最终将会产生的“撕逼”风波的期望次数，但由于她要处理下一个问题，因此把这个任务交给了你。 给定两个长度为 $n$ 的正整数数组 $a$ 和 $b$。记 $b'$ 为 $b$ 的一个全排列，且从所有 $n!$ 个排列中等概率随机选择。定义 $c_i = a_i \cdot b'_i$，其中 $1 \le i \le n$。 请计算数组 $c$ 的逆序对 $^{\text{∗}}$ 的期望数量。 $^{\text{∗}}$ 数组 $c$ 中的逆序对是形如 $(i, j)$ 的一对下标，满足 $1 \le i < j \le n$ 且 $c_i > c_j$。

每组测试包含多个测试用例。第一行包含测试用例数 $t$（$1 \le t \le 100$）。 接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2000$），表示数组 $a$ 和 $b$ 的长度。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^9$），表示数组 $a$。 第三行包含 $n$ 个整数 $b_1, b_2, \ldots, b_n$（$1 \le b_i \le 10^9$），表示数组 $b$。 保证所有测试用例中 $n$ 的总和不超过 $2000$。

对于每个测试用例，输出数组 $c$ 的逆序对数的期望值对 $998\,244\,353$ 取模的结果。 形式化地，记 $M = 998\,244\,353$。可以证明，精确答案可表示为不可约分数 $\frac{p}{q}$，其中 $p$、$q$ 为整数，且 $q \not\equiv 0 \pmod{M}$。输出一个整数 $x$，使得 $0 \le x < M$ 且 $x \cdot q \equiv p \pmod{M}$。

在第一个测试用例中，所有 $b$ 的元素都是 $1$，因此无论如何排列，$b' = (1, 1, 1, 1, 1)$，$c = (1, 14, 5, 1, 4)$ 总是不会变。此时逆序对为 $(2,3),(2,4),(2,5),(3,4),(3,5)$，共 $5$ 个。期望逆序对数量为 $5 \equiv 5 \pmod{998\,244\,353}$。 在第二个测试用例中，共有 $3! = 6$ 个等可能的排列 $b'$。每种对应 $c$ 和对应的逆序对数量如下： - $b'$：$(3,2,5)$ \quad $c = (9,4,25)$ \quad 逆序对数量 $1$ - $b'$：$(3,5,2)$ \quad $c = (9,10,10)$ \quad 逆序对数量 $0$ - $b'$：$(2,3,5)$ \quad $c = (6,6,25)$ \quad 逆序对数量 $0$ - $b'$：$(2,5,3)$ \quad $c = (6,10,15)$ \quad 逆序对数量 $0$ - $b'$：$(5,3,2)$ \quad $c = (15,6,10)$ \quad 逆序对数量 $2$ - $b'$：$(5,2,3)$ \quad $c = (15,4,15)$ \quad 逆序对数量 $1$ 逆序对期望值为 $\frac{1+0+0+0+2+1}{6} = \frac{4}{6} = \frac{2}{3}$。 模 $998\,244\,353$ 后，答案为 $2 \cdot 3^{-1} \equiv 665\,496\,236 \pmod{998\,244\,353}$。 由 ChatGPT 5 翻译