Jury Meeting (Codeforces 1569C)
Tags: Math, combinatorics

$$$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.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).Then the discussion goes as follows:  If a jury member $$$p_1$$$ has some tasks left to tell, then they tell one task to others. Otherwise, they are skipped.  If a jury member $$$p_2$$$ has some tasks left to tell, then they tell one task to others. Otherwise, they are skipped.  ...  If a jury member $$$p_n$$$ has some tasks left to tell, then they tell one task to others. Otherwise, they are skipped.  If there are still members with tasks left, then the process repeats from the start. Otherwise, the discussion ends. A permutation $$$p$$$ is nice if none of the jury members tell two or more of their own tasks in a row. Count the number of nice permutations. The answer may be really large, so print it modulo $$$998\,244\,353$$$.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.The first line of the test case contains a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — number of jury members.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.The sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case, print one integer — the number of nice permutations, taken modulo $$$998\,244\,353$$$.

Note: Explanation of the first test case from the example:There are two possible permutations, $$$p = [1, 2]$$$ and $$$p = [2, 1]$$$. For $$$p = [1, 2]$$$, the process is the following:  the first jury member tells a task;  the second jury member tells a task;  the first jury member doesn't have any tasks left to tell, so they are skipped;  the second jury member tells a task. So, the second jury member has told two tasks in a row (in succession), so the permutation is not nice.For $$$p = [2, 1]$$$, the process is the following:  the second jury member tells a task;  the first jury member tells a task;  the second jury member tells a task. So, this permutation is nice.

Sample Inputs:
4
2
1 2
3
5 5 5
4
1 3 3 7
6
3 4 2 1 3 3

Sample Outputs:
1
6
0
540

Solution (Python):
mod = 998244353

def fact(n):
    numb = 1
    for i in range(1, n + 1):
        numb = numb * i % mod
    return numb

def fact1(n, k):
    numb = 1
    for i in range(1, n + 1):
        if i != k + 1:
            numb = numb * i % mod
    return numb
t = int(input())
for i in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    if a[-1] == a[-2]:
        print(fact(n))
    elif a[-1] > a[-2] + 1:
        print(0)
    else:
        k = a.count(a[-2])
        ans = fact1(n, k)
        ans *= k
        ans %= mod
        print(ans)

Solution (Python):
modulo = 998244353

def bin_pow(a, n):
    result = 1
    while n > 0:
        if n % 2 == 1:
            result = result * a % modulo
        a = a * a % modulo
        n //= 2
    return result
factorials = [1 for _ in range(200001)]
for i in range(2, 200001):
    factorials[i] = factorials[i - 1] * i % modulo
t = int(input())
for _ in range(t):
    n = int(input())
    jury = list(map(int, input().split()))
    mx = max(jury)
    answer = factorials[n]
    if jury.count(mx) == 1:
        a = jury.count(mx - 1)
        answer = answer * a % modulo * bin_pow(a + 1, modulo - 2) % modulo
    print(answer)

Solution (Python):
def factorial(n):
    ans = 1
    for k in range(2, n + 1):
        ans = ans * k % MOD
    return ans

def factorial_absent(n, absent):
    ans = 1
    for k in range(2, n + 1):
        if k != absent:
            ans = ans * k % MOD
    return ans
MOD = 998244353
TestCases = int(input())
for _ in range(TestCases):
    N = int(input())
    a = list(map(int, input().split()))
    mx = max(a)
    mx_count = a.count(mx)
    mx2_count = a.count(mx - 1)
    if mx_count > 1:
        print(factorial(N))
    elif mx2_count == 0:
        print(0)
    else:
        print((factorial(N) - factorial_absent(N, mx2_count + 1) + MOD) % MOD)