A7158 | $Wish I Knew How to Sort$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

给定一个长度为 $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\}$），表示数组的元素。

对于每个测试用例，输出一个整数，表示 $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

C++ 编辑器

输入

输出