P4561 [JXOI2018] Sorting Problem

Kujou Karen is a girl who loves thinking.

Kujou Karen has recently been studying the properties of various sorting algorithms, and she discovered a very interesting sorting method: Gobo sort! The algorithm of Gobo sort is roughly as follows: - Suppose we want to sort a sequence $a$ of size $n$. - Randomly and uniformly generate a permutation $p$ of size $n$. - Construct a sequence $b$ of size $n$ such that $b_i = a_{p_i}$, check whether $b$ is sorted. If $b$ is already sorted, end the algorithm and return $b$; otherwise, go back to step 2. Obviously, the expected time complexity of this algorithm is $O(n \times n!)$. However, to her surprise, by using the magic of quantum mechanics, in a quantum system this algorithm can be optimized to linear time. Kujou Karen studied this sorting algorithm further and found that if a sequence satisfies certain properties, Gobo sort will quickly compute the correct result. To quantify this speed, she defines the number of rounds of Gobo sort as the number of times step 2 is executed. Then she came up with the following problem: Now there is a sequence $x$ of length $n$. Kujou Karen will append $m$ elements to the end of this sequence, each element being a positive integer in $[l, r]$. She wants the expected number of rounds for Gobo sort on the new sequence of length $n + m$ to be as large as possible. She wants to obtain this maximum expected number of rounds. Kujou Karen is very smart and quickly computed the answer. She wants to check it with you. Since this expected number is too large, she only asks you to output the result modulo $998244353$.

The first line contains an integer $T$, the number of test cases. The next $2 \times T$ lines describe the $T$ test cases. Each test case consists of two lines. The first line contains four positive integers $n, m, l, r$, representing the length of the sequence, the number of added numbers, and the range of the added numbers. The second line contains $n$ positive integers; the $i$-th is $x_i$.

Output $T$ integers, the answers.

### Sample Explanation For the first test case, we can append $\{1, 2, 2\}$ to the end of the sequence, making it `1 3 4 1 2 2`. Then the success probability in one round is $\frac{1}{180}$, so the expected number of rounds is $180$. For the second test case, we can append $\{5, 6, 7\}$ to the end of the sequence, making it `1 3 4 5 6 7`. Then the success probability in one round is $\frac{1}{720}$, so the expected number of rounds is $720$. ### Constraints - For 30% of the testdata, $T \leq 10$, $n, m, l, r \leq 8$. - For 50% of the testdata, $T \leq 300$, $n, m, l, r, a_i \leq 300$. - For 60% of the testdata, $\sum (r - l + 1) \leq 10^7$. - For 70% of the testdata, $\sum n \leq 2 \times 10^5$. - For 90% of the testdata, $m \leq 2 \times 10^5$. - For 100% of the testdata, $T \leq 10^5$, $n \leq 2 \times 10^5$, $m \leq 10^7$, $1 \leq l \leq r \leq 10^9$, $1 \leq a_i \leq 10^9$, $\sum n \leq 2 \times 10^6$. Translated by ChatGPT 5