309890: CF1753C. Wish I Knew How to Sort

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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

Input

题意翻译

给定一个长度为 $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\}$。

Output

**题目大意:**
给定一个长度为 $ 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} $。

加入题单

上一题 下一题 算法标签: