Small Permutation Problem (Hard Version) (Codeforces 1909F2)
Tags: Math, combinatorics

Andy Tunstall - MiniBoss⠀In the easy version, the $$$a_i$$$ are in the range $$$[0, n]$$$; in the hard version, the $$$a_i$$$ are in the range $$$[-1, n]$$$ and the definition of good permutation is slightly different. You can make hacks only if all versions of the problem are solved.You are given an integer $$$n$$$ and an array $$$a_1, a_2, \dots, a_n$$$ of integers in the range $$$[-1, n]$$$.A permutation $$$p_1, p_2, \dots, p_n$$$ of $$$[1, 2, \dots, n]$$$ is good if, for each $$$i$$$, the following condition is true:   if $$$a_i \neq -1$$$, the number of values $$$\leq i$$$ in $$$[p_1, p_2, \dots, p_i]$$$ is exactly $$$a_i$$$. Count the good permutations of $$$[1, 2, \dots, n]$$$, modulo $$$998\,244\,353$$$.

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — the length of the array $$$a$$$.The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-1 \le a_i \le n$$$), which describe the conditions for a good permutation.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case, output a single line containing the number of good permutations, modulo $$$998\,244\,353$$$.

Note: In the first test case, all the permutations of length $$$5$$$ are good, so there are $$$120$$$ good permutations.In the second test case, the only good permutation is $$$[1, 2, 3, 4, 5]$$$.In the third test case, there are $$$4$$$ good permutations: $$$[2, 1, 5, 6, 3, 4]$$$, $$$[2, 1, 5, 6, 4, 3]$$$, $$$[2, 1, 6, 5, 3, 4]$$$, $$$[2, 1, 6, 5, 4, 3]$$$. For example, $$$[2, 1, 5, 6, 3, 4]$$$ is good because:   $$$a_1 = 0$$$, and there are $$$0$$$ values $$$\leq 1$$$ in $$$[p_1] = [2]$$$;  $$$a_2 = 2$$$, and there are $$$2$$$ values $$$\leq 2$$$ in $$$[p_1, p_2] = [2, 1]$$$;  $$$a_3 = 2$$$, and there are $$$2$$$ values $$$\leq 3$$$ in $$$[p_1, p_2, p_3] = [2, 1, 5]$$$;  $$$a_4 = 2$$$, and there are $$$2$$$ values $$$\leq 4$$$ in $$$[p_1, p_2, p_3, p_4] = [2, 1, 5, 6]$$$;  $$$a_5 = -1$$$, so there are no restrictions on $$$[p_1, p_2, p_3, p_4, p_5]$$$;  $$$a_6 = -1$$$, so there are no restrictions on $$$[p_1, p_2, p_3, p_4, p_5, p_6]$$$. 

Sample Inputs:
10
5
-1 -1 -1 -1 -1
5
1 2 3 4 5
6
0 2 2 2 -1 -1
6
-1 -1 -1 -1 -1 5
6
-1 -1 3 2 -1 -1
15
0 0 -1 -1 -1 2 2 -1 -1 -1 -1 9 11 13 15
6
0 2 2 2 4 6
6
0 1 3 4 5 5
6
1 2 3 2 4 6
15
0 0 1 1 1 2 3 4 5 6 7 9 11 13 15

Sample Outputs:
120
1
4
0
0
494403526
4
0
0
532305727

Solution (Python):
import sys
input = sys.stdin.buffer.readline
MOD = 998244353
MAXN = 2 * 10 ** 5 + 1
fac = [1] * MAXN
ifac = [1] * MAXN
for i in range(2, MAXN):
    fac[i] = fac[i - 1] * i % MOD
ifac[-1] = pow(fac[-1], -1, MOD)
for i in range(MAXN - 2, -1, -1):
    ifac[i] = ifac[i + 1] * (i + 1) % MOD

def choose(n, k):
    if k > n:
        return 0
    return fac[n] * ifac[k] % MOD * ifac[n - k] % MOD

def ways_mat(a, b, c):
    ans = choose(a, c) * choose(b, c) * fac[c]
    return ans
for _ in range(int(input())):
    n = int(input())
    a = [0] + list(map(int, input().split()))
    if a[-1] == -1:
        a[-1] = n
    bad = False
    imp_a = [x for x in a if ~x]
    if a[-1] != n:
        bad = True
    for i in range(len(imp_a) - 1):
        if imp_a[i] > imp_a[i + 1]:
            bad = True
    if bad:
        ans = 0
    else:
        ans = 1
        pi = 0
        for i in range(1, n + 1):
            if ~a[i]:
                need_place = a[i] - a[pi]
                ways = 0
                for place_below_pi in range(need_place + 1):
                    cways = ways_mat(i - pi, pi - a[pi], place_below_pi)
                    cways *= ways_mat(i - a[pi] - place_below_pi, i - pi, need_place - place_below_pi)
                    cways %= MOD
                    ways += cways
                ans = ans * ways % MOD
                pi = i
    print(ans)

Solution (Python):
import sys
input = sys.stdin.buffer.readline

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

def ri():
    return int(input())

def rs():
    return input().decode('utf-8')[:-2]

def rm():
    return map(int, input().split())
mod = 998244353

def main():
    n = ri()
    a = rl()
    if a[-1] != n and a[-1] != -1:
        return 0
    lsti = -1
    lstp = 0
    res = 1
    for i in range(n):
        if a[i] == -1:
            continue
        if not 0 <= a[i] - lstp <= 2 * (i - lsti):
            return 0
        todo = a[i] - lstp
        rem1 = lsti + 1 - lstp
        rem2 = i - lsti
        lg = i - lsti
        al = i + 1 - lstp
        cnt = 0
        cnt1 = [1] * (todo + 1)
        cnt2 = [1] * (todo + 1)
        for j in range(1, todo + 1):
            if lg - j + 1 > 0 and rem1 - j + 1 > 0:
                cnt1[j] = cnt1[j - 1] * (lg - j + 1) * pow(j, -1, mod) * (rem1 - j + 1)
                cnt1[j] %= mod
            else:
                cnt1[j] = 0
            if al - todo + j > 0 and rem2 - j + 1 > 0:
                cnt2[j] = cnt2[j - 1] * (al - todo + j) * pow(j, -1, mod) * (rem2 - j + 1)
                cnt2[j] %= mod
            else:
                cnt2[j] = 0
        for j in range(todo + 1):
            cnt += cnt1[j] * cnt2[todo - j]
            cnt %= mod
        res *= cnt
        res %= mod
        lsti = i
        lstp = a[i]
    rem1 = lsti + 1 - lstp
    lg = n - 1 - lsti
    al = n - lstp
    for i in range(rem1):
        res *= lg - i
        res %= mod
    for i in range(1, al - rem1 + 1):
        res *= i
        res %= mod
    return res
t = ri()
for i in range(t):
    print(main())

Solution (Python):
import sys
import io
import os
from string import *
from re import *
from collections import *
from heapq import *
from bisect import *
from copy import *
from random import *
from itertools import *
from functools import *
from typing import *
MOD = 998244353
inf = 1 << 60

class Combi:

    def __init__(self, max_n, mod):
        max_n += 1
        self.mod = mod
        self.fact = [0] * max_n
        self.rev = [0] * max_n
        self.fact_rev = [0] * max_n
        self.fact[0] = 1
        self.rev[0] = 1
        self.fact_rev[0] = 1
        for i in range(max_n):
            if i <= 1:
                self.fact[i] = 1
                self.rev[i] = 1
                self.fact_rev[i] = 1
                continue
            self.fact[i] = i * self.fact[i - 1] % mod
            self.rev[i] = mod - mod // i * self.rev[mod % i] % mod
            self.fact_rev[i] = self.fact_rev[i - 1] * self.rev[i] % mod

    def cnk(self, n, k):
        if n < k:
            return 0
        ans = self.fact_rev[n - k] * self.fact_rev[k] % self.mod
        return ans * self.fact[n] % self.mod

    def ank(self, n, k):
        if n < k:
            return 0
        return self.fact[n] * self.fact_rev[n - k] % self.mod
C = Combi(200000 + 5, MOD)
comb = C.cnk
perm = C.ank

def solve():
    n = read_int()
    A = read_int_list()
    if A[-1] not in (-1, n):
        return 0
    (res, A[-1]) = (1, n)
    p = c = 0
    for (t, a) in enumerate(A, 1):
        if a == -1:
            continue
        if t < a or a < c:
            return 0
        cnt = 0
        for x in range(a - c + 1):
            cnt += comb(t - p, x) * perm(p - c, x) * comb(t - p, a - c - x) * perm(t - c - x, a - c - x) % MOD
        res = res * cnt % MOD
        (p, c) = (t, a)
    return res

def main():
    T = 1
    T = read_int()
    for t in range(T):
        print(solve())
BUFSIZE = 8192

class FastIO(io.IOBase):
    newlines = 0

    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.buffer = io.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(io.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')

def print(*args, **kwargs):
    """"""
    (sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop('end', '\n'))
    if kwargs.pop('flush', False):
        file.flush()
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

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

def read_ints_minus_one():
    return [int(x) - 1 for x in input().split()]

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

def read_encode_str(d=97):
    return [ord(x) - d for x in input()]

def read_graph(n: int, m: int, d=1):
    g = [[] for _ in range(n)]
    for _ in range(m):
        (u, v) = map(int, input().split())
        g[u - d].append(v - d)
        g[v - d].append(u - d)
    return g

def read_grid(m: int):
    return [input() for _ in range(m)]

def read_int():
    return int(input())
read_str = input
if __name__ == '__main__':
    main()