1666F - Fancy Stack - CodeForces Solution

import os
import sys
from io import BytesIO, IOBase

_str = str
str = lambda x=b"": x if type(x) is bytes else _str(x).encode()
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)

class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")

sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

from collections import Counter

def main():
    t = int(input())
    while t:
        n = int(input())
        a = list(map(int, input().strip().split(' ')))
        MOD = 998244353
        fac = [1] * (n + 1)
        inv = [1] * (n + 1)
        finv = [1] * (n + 1)
        for i in range(2, n + 1):
            fac[i] = fac[i-1] * i % MOD
            inv[i] = MOD - MOD // i * inv[MOD%i] % MOD
            finv[i] = finv[i-1] * inv[i] % MOD
        
        def C(n, m):
            if m == 0:
                return 1
            if m > n:
                return 0
            return fac[n] * finv[m] * finv[n-m] % MOD

        cnt = Counter(a)
        cnt = sorted(cnt.items(), key=lambda x: x[0], reverse=True)
        dp = [[0] * (n//2+1) for _ in range(len(cnt)+1)]
        dp[0][0] = 1
        pre_sum = [0] * (len(cnt)+1)
        for i in range(1, len(cnt)+1):
            pre_sum[i] = pre_sum[i-1] + cnt[i-1][1]
        for i in range(len(cnt)):
            for j in range(min(i+1, n//2+1)):
                small = pre_sum[i]-j
                if j < n // 2:
                    dp[i+1][j+1] = (dp[i+1][j+1] + dp[i][j] * C(j-1-small, cnt[i][1]-1)) % MOD
                slot = j-1-small
                if j == n // 2:
                    slot += 1
                dp[i+1][j] = (dp[i+1][j] + dp[i][j] * C(slot, cnt[i][1])) % MOD
        print(dp[len(cnt)][n//2])
        t -= 1
    return

main()