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 |
| 9 |
17 |
| 10 |
18 |
| 11 |
| 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|$.
Topic
Dynamic Programming
Combinatorics
Rating
2400
Solution (0)
Solution
