Bubble sort - MarisaOJ: Marisa Online Judge

The bubble sort algorithm is a very simple

$O(n^2)$ sorting algorithm:

$Assuming p[i] is an array containing a permutation from 1 to n for i = 1 to n do for j = 1 to n - 1 do: if p[i] > p[j] swap(p[i], p[j])$

The number of swaps performed by the algorithm has a lower bound of

$\frac{1}{2} \times \sum_{i=1}^{n}|i-p_i|$ . A permutation is considered good if the number of swaps required to sort the permutation using the bubble sort algorithm exactly equals

$\frac{1}{2} \times \sum_{i=1}^{n}|i-p_i|$ . Please refer to the proof below if needed. Given

$q$ , a permutation of numbers from 1 to

$n$ , count the number of good permutations that are lexicographically greater than

$q$ . ### Input - The first line contains an integer

$T$ , the number of test cases. For each test case: - The first line contains an integer

$n$ . - The second line contains

$n$ integers representing the permutation

$q$ . ### Output - For each test case, output an integer on a new line, representing the count of good permutations modulo

$998244353$ . ### Example Input:

$1 3 1 3 2$

Output:

$3$

Input 2:

$1 4 1 4 2 3$

Output 2:

$9$

### Constraints - In all tests,

$T = 5$ . -

$n_\text{max}$ in the table below is the maximum possible value of

$n$ for a single test case.

Test	$n_\mathrm{max} =$	$\sum n \leq$	Special condition
1	8	$5 \ n_\mathrm{max}$	None
2	9
3	10
4	12
5	13
6	14
7	16
8	16
9	17
10	18
11	18
12	122	$700$	$\forall i \; q_i = i$
13	144		None
14	166
15	200
16	233
17	777	$4000$	$\forall i \; q_i = i$
18	888		None
19	933
20	1000
21	266666	$2000000$	$\forall i \; q_i = i$
22	333333		None
23	444444
24	555555
25	600000

### Proof

$p_i$ represents the value at the

$i$ -th position in the permutation. To reach its correct position, this value must be moved at least

$|p_i - i|$ positions. When two adjacent elements are swapped, the total number of movements decreases by at most

$2$ (one for each element swapped). Therefore, the minimum number of swaps required is given by

$\frac{1}{2} \times \sum_{i=1}^{n}|i-p_i|$ .

(China) National Olympiad in Informatics 2018
	Return
	Bubble sort

Topic

Dynamic Programming

Combinatorics

Rating

2400

Solution (0)

Solution