CF1753C Wish I Knew How to Sort

给定一个长度为 $n$ 的二进制数组 $a$（数组中的所有元素均为 $0$ 或 $1$）。你希望将该数组排序，但不幸的是，你的算法老师忘记教你排序算法。你按照如下操作，直到数组变为有序： 1. 随机选择两个下标 $i$ 和 $j$，满足 $i < j$。在所有满足 $1 \le i < j \le n$ 的下标对 $(i, j)$ 中，每一对被选中的概率相等。 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$ 的值。

考虑第一个测试用例。如果选择下标对 $(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}$。 由 ChatGPT 4.1 翻译