1569C.md (2663B)
1 Source: https://codeforces.com/problemset/problem/1569/C 2 3 C. Jury Meeting 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 $n$ people gathered to hold a jury meeting of the upcoming competition, the $i$-th member of the jury came up with $a_i$ tasks, which they want to share with each other. 22 23 First, the jury decides on the order which they will follow while describing the tasks. Let that be a permutation $p$ of numbers from $1$ to $n$ (an array of size $n$ where each integer from $1$ to $n$ occurs exactly once). 24 25 Then the discussion goes as follows: 26 27 * If a jury member $p_1$ has some tasks left to tell, then they tell one task to others. Otherwise, they are skipped. 28 * If a jury member $p_2$ has some tasks left to tell, then they tell one task to others. Otherwise, they are skipped. 29 * ... 30 * If a jury member $p_n$ has some tasks left to tell, then they tell one task to others. Otherwise, they are skipped. 31 * If there are still members with tasks left, then the process repeats from the start. Otherwise, the discussion ends. 32 33 A permutation $p$ is nice if none of the jury members tell two or more of their own tasks in a row. 34 35 Count the number of nice permutations. The answer may be really large, so print it modulo $998\,244\,353$. 36 37 Input 38 39 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 40 41 The first line of the test case contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$) — number of jury members. 42 43 The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$) — the number of problems that the $i$-th member of the jury came up with. 44 45 The sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 46 47 Output 48 49 For each test case, print one integer — the number of nice permutations, taken modulo $998\,244\,353$. 50 51 Example 52 53 Input 54 55 ``` 56 4 57 2 58 1 2 59 3 60 5 5 5 61 4 62 1 3 3 7 63 6 64 3 4 2 1 3 3 65 ``` 66 67 Output 68 69 ``` 70 1 71 6 72 0 73 540 74 ``` 75 76 Note 77 78 Explanation of the first test case from the example: 79 80 There are two possible permutations, $p = [1, 2]$ and $p = [2, 1]$. For $p = [1, 2]$, the process is the following: 81 82 1. the first jury member tells a task; 83 2. the second jury member tells a task; 84 3. the first jury member doesn't have any tasks left to tell, so they are skipped; 85 4. the second jury member tells a task. 86 87 So, the second jury member has told two tasks in a row (in succession), so the permutation is not nice. 88 89 For $p = [2, 1]$, the process is the following: 90 91 1. the second jury member tells a task; 92 2. the first jury member tells a task; 93 3. the second jury member tells a task. 94 95 So, this permutation is nice.