CF2208E.Counting Cute Arrays

给定长度为 $n$ 的正整数数组 $[A_1, A_2, \ldots, A_n]$，定义数组 $f(A)$ 如下：

对于每个 $i$ 从 $1$ 到 $n$：

• 如果存在 $j < i$ 满足 $A_j < A_i$，则 $f(A)_i = \max\limits_{j < i,\, A_j < A_i} j$，即 $f(A)_i$ 是位于 $i$ 前且值严格小于 $A_i$ 的最右边元素的下标。
• 否则，$f(A)_i = 0$。

我们称非负整数数组 $[P_1, P_2, \ldots, P_n]$ 是一个“cute array”，如果存在数组 $A$ 使得 $f(A)=P$。

现在给定一个长度为 $n$ 的数组 $X$，其中 $-1 \leq X_i \leq n$ 对所有 $i$ 都成立。统计将 $X$ 中的 $-1$ 替换为 $0$ 到 $n$ 之间的整数后，形成的“cute array” $X'$ 的个数。由于答案可能很大，请对 $998\,244\,353$ 取模输出。

每组测试数据包含多个测试用例。第一行包含整数 $t$（$1 \leq t \leq 10^3$），表示测试用例数量。

每组测试用例第一行包含一个整数 $n$（$1 \leq n \leq 5000$），表示 $X$ 的长度。

第二行包含 $n$ 个整数 $X_1, X_2, \ldots, X_n$（$-1 \leq X_i \leq n$）。

保证所有测试用例中 $n$ 的总和不超过 $5000$。

对于每个测试用例，输出一个整数，表示满足条件的“cute array” $X'$ 的数量，对 $998\,244\,353$ 取模。

对于第一个测试用例，在所有可能的 $X'$ 中，只有 $[0,0,0]$ 和 $[0,0,2]$ 是“cute array”。
$[0,0,0]$ 是一个“cute array”，因为 $f([1,1,1]) = [0,0,0]$，$[0,0,2]$ 也是一个好数组，因为 $f([1,1,2])=[0,0,2]$。

对于第二个测试用例，只有 $[0,1,1,0]$、$[0,1,1,1]$ 和 $[0,1,1,3]$ 是“cute array”。

由 ChatGPT 5 翻译