CF1753C.Wish I Knew How to Sort

You are given a binary array $a$ (all elements of the array are $0$ or $1$) of length $n$. You wish to sort this array, but unfortunately, your algorithms teacher forgot to teach you sorting algorithms. You perform the following operations until $a$ is sorted:

1. Choose two random indices $i$ and $j$ such that $i \lt j$. Indices are chosen equally probable among all pairs of indices $(i, j)$ such that $1 \le i \lt j \le n$.
2. If $a_i \gt a_j$, then swap elements $a_i$ and $a_j$.

What is the expected number of such operations you will perform before the array becomes sorted?

It can be shown that the answer can be expressed as an irreducible fraction $\frac{p}{q}$, where $p$ and $q$ are integers and $q \not \equiv 0 \pmod{998\,244\,353}$. Output the integer equal to $p \cdot q^{-1} \bmod 998\,244\,353$. In other words, output such an integer $x$ that $0 \le x \lt 998\,244\,353$ and $x \cdot q \equiv p \pmod{998\,244\,353}$.

给你一个长度为 $n$ 的二进制数组 $a$（数组中所有元素均为 $0$ 或 $1$）。你想将该数组排序，但不幸的是，你的算法老师忘记教你排序算法了。你将持续执行以下操作，直到数组 $a$ 被排好序：

1. 随机选择两个下标 $i$ 和 $j$，满足 $i \lt j$。所有满足 $1 \le i \lt j \le n$ 的下标对 $(i, j)$ 被选中的概率相等。
2. 若 $a_i \gt 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$。换言之，请输出满足 $0 \le x \lt 998\,244\,353$ 且 $x \cdot q \equiv p \pmod{998\,244\,353}$ 的整数 $x$。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^5$). Description of the test cases follows.

The first line of each test case contains an integer $n$ ($1 \le n \le 200\,000$) — the number of elements in the binary array.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($a_i \in {0, 1}$) — elements of the array.

It's guaranteed that sum of $n$ over all test cases does not exceed $200\,000$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For each test case print one integer — the value $p \cdot q^{-1} \bmod 998\,244\,353$.

对于每个测试用例，输出一个整数——即 $p \cdot q^{-1} \bmod 998\,244\,353$ 的值。

Consider the first test case. If the pair of indices $(2, 3)$ will be chosen, these elements will be swapped and array will become sorted. Otherwise, if one of pairs $(1, 2)$ or $(1, 3)$ will be selected, nothing will happen. So, the probability that the array will become sorted after one operation is $\frac{1}{3}$, the probability that the array will become sorted after two operations is $\frac{2}{3} \cdot \frac{1}{3}$, the probability that the array will become sorted after three operations is $\frac{2}{3} \cdot \frac{2}{3} \cdot \frac{1}{3}$ and so on. The expected number of operations is $\sum \limits_{i=1}^{\infty} \left(\frac{2}{3} \right)^{i - 1} \cdot \frac{1}{3} \cdot i = 3$.

In the second test case the array is already sorted so the expected number of operations is zero.

In the third test case the expected number of operations equals to $\frac{75}{4}$ so the answer is $75 \cdot 4^{-1} \equiv 249\,561\,107 \pmod {998\,244\,353}$.

考虑第一个测试用例。若选择下标对 $(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$。

在第二个测试用例中，数组初始即为有序，因此期望操作次数为 $0$。

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