Wish I Knew How to Sort

题意翻译

给定一个长度为 $n$ 的 01 序列 $a$ 和一种操作，你需要用这种操作将序列从小到大排序。 操作如下： - 等概率随机选取两个位置 $i,j\ (i<j)$，若 $a_i>a_j$，则交换 $a_i,a_j$。 **注意**：当 $a_i\le a_j$ 时，交换失败，也算作一次操作。 请你求出操作被执行的 **期望次数**。对 998244353 取模。$1\le n\le2\times 10^5,\ a_i\in \{0,1\}$。

题目描述

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 < j $ . Indices are chosen equally probable among all pairs of indices $ (i, j) $ such that $ 1 \le i < j \le n $ . 2. If $ a_i > a_j $ , then swap elements $ a_i $ and $ a_j $ . What is the [expected number](https://en.wikipedia.org/wiki/Expected_value) 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 < 998\,244\,353 $ and $ x \cdot q \equiv p \pmod{998\,244\,353} $ .

输入输出格式

输入格式

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 $ .

输出格式

For each test case print one integer — the value $ 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

说明

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} $ .

**题目大意：**
给定一个长度为 $ n $ 的由 0 和 1 组成的序列 $ a $，你可以进行以下操作，直到序列被从小到大排序：

1. 随机选择两个索引 $ i $ 和 $ j $ 使得 $ i < j $。选择的索引在所有可能的索引对中是等概率的。
2. 如果 $ a_i > a_j $，则交换 $ a_i $ 和 $ a_j $ 的值。

求出执行这些操作直到序列被排序的期望次数。结果可以表示为不可约分数 $ \frac{p}{q} $，其中 $ p $ 和 $ q $ 是整数，且 $ q $ 在模 $ 998\,244\,353 $ 下不为 0。输出 $ 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} $，以此类推。期望的操作次数是 $ \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} $。**题目大意：** 给定一个长度为 $ n $ 的由 0 和 1 组成的序列 $ a $，你可以进行以下操作，直到序列被从小到大排序： 1. 随机选择两个索引 $ i $ 和 $ j $ 使得 $ i < j $。选择的索引在所有可能的索引对中是等概率的。 2. 如果 $ a_i > a_j $，则交换 $ a_i $ 和 $ a_j $ 的值。 求出执行这些操作直到序列被排序的期望次数。结果可以表示为不可约分数 $ \frac{p}{q} $，其中 $ p $ 和 $ q $ 是整数，且 $ q $ 在模 $ 998\,244\,353 $ 下不为 0。输出 $ 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} $，以此类推。期望的操作次数是 $ \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} $。