CF2129D.Permutation Blackhole

对于一个长度为 $n$ 的排列 $p_1, p_2, \ldots, p_n$，可以通过如下的染色过程得到对应的染色序列 $s$：

• 初始时，有 $n$ 个白色格子，从左到右编号为 $1$ 到 $n$。在第 $0$ 秒时，每个格子的分数均为 $0$。
• 在第 $i$ 秒（$1 \le i \le n$）：
  • 如果 $i > 1$，找到距离格子 $p_i$ 最近的黑色格子，并将该格子的分数加 $1$。如果有多个最近的黑色格子，选择编号最小的那个。格子 $y$ 被称为格子 $x$ 最近的黑色格子，当且仅当格子 $y$ 是黑色的，且不存在黑色格子 $z$ 满足 $|x-z|<|x-y|$。
  • 将格子 $p_i$ 染成黑色。

当所有格子都被染成黑色后，记 $s_i$ 为格子 $i$ 的分数（$1 \le i \le n$），则得到染色序列 $s$。

你可以阅读题目下方的注释以更好地理解题意。

现在给定一个不完整的染色序列 $s$，其中部分 $s_i$ 已经确定，部分尚未确定。请你计算有多少种不同的排列 $p$ 能够产生该染色序列。由于答案可能很大，请输出答案对 $998\,244\,353$ 取模后的结果。

每个测试点包含多组测试数据。第一行包含一个整数 $t$（$1 \le t \le 10^3$），表示测试数据的组数。

对于每组测试数据，第一行包含一个整数 $n$（$2 \leq n \leq 100$）。

第二行包含 $n$ 个整数 $s_1, s_2, \ldots, s_n$（$-1 \leq s_i \leq n-1$）。其中 $s_i=-1$ 表示 $s_i$ 尚未确定，$s_i \neq -1$ 表示 $s_i$ 已经确定。

保证所有测试数据中 $n^2$ 的和不超过 $10^4$。

对于每组测试数据，输出能够产生该染色序列 $s$ 的不同排列 $p_1, p_2, \ldots, p_n$ 的总数，对 $998\,244\,353$ 取模。

在第一个测试点中，$p=[3,1,2]$ 和 $p=[3,2,1]$ 都可以产生染色序列 $s=[-1,-1,1]$。

对于 $p=[3,1,2]$，染色过程如下图所示。

分别为 $p=[3,1,2]$ 时第 $0$ 秒、第 $1$ 秒、第 $2$ 秒和第 $3$ 秒的格子状态。

对于 $p=[3,2,1]$，染色过程如下图所示。

分别为 $p=[3,2,1]$ 时第 $0$ 秒、第 $1$ 秒、第 $2$ 秒和第 $3$ 秒的格子状态。

由 ChatGPT 4.1 翻译