← 返回题目列表

Codeforces · 1753/C

C. 希望我知道如何排序

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

给你一个长度为$$$n$$$的二进制数组$$$a$$$(数组的所有元素都是$$$0$$$或$$$1$$$)。你想对这个数组进行排序,但不幸的是,你的算法老师忘记教你排序算法。您执行以下操作,直到 $$$a$$$ 被排序:

1. 选择两个随机索引 $$$i$$$ 和 $$$j$$$,使得 $$$i < j$$$。在所有索引对 $$$(i, j)$$$ 中选择索引的概率相同,使得 $$$1 \le i < j \le n$$$。
2. 如果 $$$a_i > a_j$$$,则交换元素 $$$a_i$$$ 和 $$$a_j$$$。

在数组排序之前,您预计将执行多少次此类操作?

可以证明,答案可以表示为不可约分数 $$$\frac{p}{q}$$$,其中 $$$p$$$ 和 $$$q$$$ 是整数,$$$q \not \equiv 0 \pmod{998\,244\,353}$$$。输出等于 $$$p \cdot q^{-1} \bmod 998\,244\,353$$$ 的整数。换句话说,输出这样一个整数$$$x$$$,$$$0 \le x < 998\,244\,353$$$ 和 $$$x \cdot q \equiv p \pmod{998\,244\,353}$$$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^5$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 200\,000$$$) — 二进制数组中的元素数量。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$a_i \in \{0, 1\}$$$) — 数组的元素。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$200\,000$$$。

输出

对于每个测试用例,打印一个整数 - 值 $$$p \cdot q^{-1} \bmod 998\,244\,353$$$。

示例

输入 #1

3
3
0 1 0
5
0 0 1 1 1
6
1 1 1 0 0 1

输出 #1

3
0
249561107

注意

考虑第一个测试用例。如果选择索引对 $$$(2, 3)$$$,这些元素将被交换并且数组将被排序。否则,如果选择 $$$(1, 2)$$$ 或 $$$(1, 3)$$$ 之一,则不会发生任何情况。因此,数组在一次操作后排序的概率为 $$$\frac{1}{3}$$$,数组在两次操作后排序的概率为 $$$\frac{2}{3} \cdot \frac{1}{3}$$$,数组在三次操作后排序的概率为 $$$\frac{2}{3} \cdot \frac{2}{3} \cdot \frac{1}{3}$$$ 等等。预期操作数为 $$$\sum \limits_{i=1}^{\infty} \left(\frac{2}{3} \right)^{i - 1} \cdot \frac{1}{3} \cdot i = 3$$$。

在第二个测试用例中,数组已经排序,因此预期的操作数为零。

在第三个测试用例中,预期操作数等于 $$$\frac{75}{4}$$$,因此答案为 $$$75 \cdot 4^{-1} \equiv 249\,561\,107 \pmod {998\,244\,353}$$$。