← 返回题目列表

Codeforces · 2208/E

E. 计算可爱的数组

中文机器翻译题面 查看原题

令 $$$[A_1, A_2, \ldots, A_n]$$$ 为 $$$n$$$ 正整数数组。定义数组 $$$f(A)$$$ 如下:

对于从 $$$1$$$ 到 $$$n$$$ 的每个整数 $$$i$$$:

  • 如果存在整数 $$$j$$$ 使得 $$$j \lt i$$$ 和 $$$A_j \lt A_i$$$,$$$f(A)_i=\max\limits_{j \lt i,A_j \lt A_i} j$$$。也就是说,$$$f(A)_i$$$ 是$$$i$$$ 之前最右边元素的索引,其值严格小于$$$A_i$$$。
  • 否则$$$f(A)_i=0$$$。

我们将非负整数数组 $$$[P_1,P_2,\ldots,P_n]$$$ 称为 a 可爱 数组,如果存在数组 $$$A$$$ 使得 $$$f(A)=P$$$。

给定一个长度$$$n$$$数组$$$X$$$,其中$$$-1\le X_i\le n$$$适用于从$$$1$$$到$$$n$$$的所有$$$i$$$。计算通过将 $$$X$$$ 中的 $$$-1$$$ 替换为 $$$0$$$ 到 $$$n$$$ 之间的整数而形成的可爱数组 $$$X'$$$ 的数量。由于数字可能非常大,因此打印它对 $$$998\,244\,353$$$ 取模。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^3$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数$$$n$$$ ($$$1\le n\le5000$$$),表示$$$X$$$的长度。

第二行包含 $$$n$$$ 整数 $$$X_1,X_2,\ldots,X_n$$$ ($$$-1\le X_i\le n$$$)。

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

输出

对于每个测试用例,输出一个整数,表示数组 $$$X'$$$ 的数量,使得 $$$X'$$$ 是一个可爱的数组,模 $$$998\,244\,353$$$。

示例

输入
复制

6
3
-1 0 -1
4
-1 -1 1 -1
5
-1 -1 -1 -1 -1
4
-1 0 2 3
4
1 1 2 3
4
0 0 0 1

输出
复制

2
3
42
1
0
0

注意

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

对于第二个测试用例,在所有可能的 $$$X'$$$ 中,只有 $$$[0,1,1,0]$$$、$$$[0,1,1,1]$$$ 和 $$$[0,1,1,3]$$$ 是可爱的数组。