Fancy Stack (Codeforces 1666F)
Tags: Implement, combinatorics

Little Fiona has a collection of $$$n$$$ blocks of various sizes $$$a_1, a_2, \ldots, a_n$$$, where $$$n$$$ is even. Some of the blocks can be equal in size. She would like to put all these blocks one onto another to form a fancy stack.Let $$$b_1, b_2, \ldots, b_n$$$ be the sizes of blocks in the stack from top to bottom. Since Fiona is using all her blocks, $$$b_1, b_2, \ldots, b_n$$$ must be a permutation of $$$a_1, a_2, \ldots, a_n$$$. Fiona thinks the stack is fancy if both of the following conditions are satisfied:   The second block is strictly bigger than the first one, and then each block is alternately strictly smaller or strictly bigger than the previous one. Formally, $$$b_1 < b_2 > b_3 < b_4 > \ldots > b_{n-1} < b_n$$$.  The sizes of the blocks on even positions are strictly increasing. Formally, $$$b_2 < b_4 < b_6 < \ldots < b_n$$$ (remember that $$$n$$$ is even).   Two stacks are considered different if their corresponding sequences $$$b_1, b_2, \ldots, b_n$$$ differ in at least one position.Fiona wants to know how many different fancy stacks she can build with all of her blocks. Since large numbers scare Fiona, find this number modulo $$$998\,244\,353$$$.

Input: Each input contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 2500$$$). Description of the test cases follows.The first line of each test case contains a single integer $$$n$$$ — the number of blocks at Fiona's disposal ($$$2 \le n \le 5000$$$; $$$n$$$ is even). The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ — the sizes of the blocks in non-decreasing order ($$$1 \le a_1 \le a_2 \le \dotsb \le a_n \le n$$$).It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5000$$$.

Output: For each test case, print the number of ways to build a fancy stack, modulo $$$998\,244\,353$$$.


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

Sample Outputs:
2
4

Solution (Python):
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()

Solution (Python):
from io import BytesIO, IOBase
import sys
import os
import bisect
import math
import random
from collections import Counter, defaultdict, deque
from copy import deepcopy
from functools import cmp_to_key, lru_cache, reduce
from heapq import heapify, heappop, heappush, heappushpop, nlargest, nsmallest
from itertools import accumulate, combinations, permutations, count
from operator import add, iand, ior, itemgetter, mul, xor
from string import ascii_lowercase, ascii_uppercase
from typing import *

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')
BUFSIZE = 4096

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 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))

    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()
sys.stdin = IOWrapper(sys.stdin)
sys.stdout = IOWrapper(sys.stdout)
input = lambda : sys.stdin.readline().rstrip('\r\n')

def I():
    return input()

def II():
    return int(input())

def MII():
    return map(int, input().split())

def LI():
    return list(input().split())

def LII():
    return list(map(int, input().split()))

def GMI():
    return map(lambda x: int(x) - 1, input().split())

def LGMI():
    return list(map(lambda x: int(x) - 1, input().split()))
inf = float('inf')

class Factorial:

    def __init__(self, N, mod) -> None:
        N += 1
        self.mod = mod
        self.f = [1 for _ in range(N)]
        self.g = [1 for _ in range(N)]
        for i in range(1, N):
            self.f[i] = self.f[i - 1] * i % self.mod
        self.g[-1] = pow(self.f[-1], mod - 2, mod)
        for i in range(N - 2, -1, -1):
            self.g[i] = self.g[i + 1] * (i + 1) % self.mod

    def fac(self, n):
        return self.f[n]

    def fac_inv(self, n):
        return self.g[n]

    def comb(self, n, m):
        if n < m or m < 0 or n < 0:
            return 0
        return self.f[n] * self.g[m] % self.mod * self.g[n - m] % self.mod

    def perm(self, n, m):
        if n < m or m < 0 or n < 0:
            return 0
        return self.f[n] * self.g[n - m] % self.mod

    def catalan(self, n):
        return (self.comb(2 * n, n) - self.comb(2 * n, n - 1)) % self.mod

    def inv(self, n):
        return self.f[n - 1] * self.g[n] % self.mod
mod = 998244353
fact = Factorial(5000, mod)
t = II()
for _ in range(t):
    n = II()
    nums = LII()
    smaller_pos = [None] * n
    pt = n - 1
    for i in range(n - 1, -1, -1):
        while pt >= 0 and nums[pt] >= nums[i]:
            pt -= 1
        smaller_pos[i] = pt + 1
    dp = smaller_pos[:]
    for cnt in range(1, n // 2):
        for i in range(n):
            dp[i] *= max(0, smaller_pos[i] + 1 - 2 * cnt)
            if i:
                dp[i] += dp[i - 1]
            dp[i] %= mod
        dp = [dp[smaller_pos[i] - 1] if smaller_pos[i] else 0 for i in range(n)]
    ans = dp[-1]
    for x in Counter(nums).values():
        ans *= fact.fac_inv(x)
        ans %= mod
    print(ans)

Solution (Python):
MOD = 998244353

def mod_mul(x, y, c=0):
    return (x * y + c) % MOD

def inv(x):
    return pow(x, MOD - 2, MOD)
t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    denom = 1
    pre = [0] * n
    for i in range(1, n):
        if a[i] == a[i - 1]:
            pre[i] = pre[i - 1]
        else:
            pre[i] = i
        denom = mod_mul(denom, i - pre[i] + 1)
    curr = [1] * n
    pref = [i for i in range(n)]
    for i in range(n // 2 - 1):
        new = []
        for j in range(n):
            if pre[j] < 2 * (i + 1):
                new.append(0)
                continue
            new.append(mod_mul(pref[pre[j]], pre[j] - 2 * i - 1))
        pref = [0]
        for j in range(n - 1):
            pref.append((pref[-1] + new[j]) % MOD)
        curr = new
    print(mod_mul(pref[pre[-1]], inv(denom)))