← 返回题目列表

Codeforces · 2223/B

B. 芝利和巴克奈特

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

Zhily 开发了一款名为 Barknights 的游戏,她正准备在 3 月份发布重大更新 $$$25$$$。具体来说,她计划为游戏中的每个干员添加一个模块,将他们的功率水平乘以模块的功率。

更新发布后,著名游戏主播Jily将评估干员的实力等级,并在等级列表中进行排名。每当一个较早发布的干员排名高于一个较晚发布的干员时,就会引起一波大戏。

不幸的是,Zhily不小心打翻了一个热水壶,摔坏了她的电脑,导致所有模块被随机重新排列。现在Zhily想知道预计会产生多少波戏剧,但由于她必须继续处理下一个问题,所以她把这个任务委托给了你。

给定两个数组 $$$a$$$ 和 $$$b$$$,其中 $$$n$$$ 正整数。令 $$$b'$$$ 为数组 $$$b$$$ 的排列,在所有 $$$n!$$$ 可能的排列中均匀随机选择。定义 $$$c_i = a_i \cdot b'_i$$$ 为 $$$1\le i \le n$$$。

求数组 $$$c$$$ 的预期反转次数$$$^{\text{*}}$$$。

$$$^{\text{*}}$$$数组 $$$c$$$ 中的反转是一对索引 $$$(i, j)$$$,使得 $$$1 \le i \lt j \le n$$$ 和 $$$c_i \gt 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}$$$。输出等于 $$$p \cdot q^{-1} \bmod M$$$ 的整数。换句话说,输出这样一个整数 $$$x$$$ 使得 $$$0 \le x \lt M$$$ 和 $$$x \cdot q \equiv p \pmod{M}$$$ 。

示例

输入
复制

3
5
1 14 5 1 4
1 1 1 1 1
3
3 2 5
3 2 5
10
10 72 65 43 73 23 78 13 49 99
31 90 45 19 44 18 59 31 48 29

输出
复制

5
665496236
820778710

注意

在第一个测试用例中,由于 $$$b$$$ 的所有元素都是 $$$1$$$,任何 $$$5!$$$ 排列都会导致 $$$b' = (1, 1, 1, 1, 1)$$$。因此,$$$c = (1, 14, 5, 1, 4)$$$ 始终是常数。反转为 $$$(2, 3)、(2, 4)、(2, 5)、(3, 4)、$$$ 和 $$$(3, 5)$$$。预期的反转次数为 $$$5 \equiv 5 \pmod{998\,244\,353}$$$。

在第二个测试用例中,有 $$$3! = 6$$$ 等概率排列 $$$b'$$$。生成的数组 $$$c$$$ 及其各自的反转计数如下所示:

$$$b'$$$$$$c = (3b'_1, 2b'_2, 5b'_3)$$$反转计数
$$$(3, 2, 5)$$$$$$(9, 4, 25)$$$1
$$$(3, 5, 2)$$$$$$(9, 10, 10)$$$0
$$$(2, 3, 5)$$$$$$(6, 6, 25)$$$0
$$$(2, 5, 3)$$$$$$(6, 10, 15)$$$0
$$$(5, 3, 2)$$$$$$(15, 6, 10)$$$2
$$$(5, 2, 3)$$$$$$(15, 4, 15)$$$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}$$$。