← 返回题目列表

Codeforces · 2129/D

D. 排列黑洞

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

对于长度为$$$n$$$的排列$$$p_1, p_2, \ldots, p_n$$$,可以通过以下着色过程得到对应的着色序列$$$s$$$:

  • 最初,有 $$$n$$$ 个白色单元格,从左到右索引为从 $$$1$$$ 到 $$$n$$$。在第二个$$$0$$$时,每个单元格的分数为$$$0$$$。
  • 在第二个 $$$i$$$ ($$$1 \le i \le n$$$),
    • 如果$$$i \gt 1$$$,找到距离单元格$$$p_i$$$最近的黑色单元格,并将该单元格的分数增加$$$1$$$。如果有多个最近的黑色单元格,请选择索引最低的单元格。仅当单元格 $$$y$$$ 为黑色且不存在满足 $$$|x-z| 的黑色单元格 $$$z$$$ 时,单元格 $$$y$$$ 被称为距单元格 $$$x$$$ 最近的黑色单元格。 \lt |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$$$。

输出

对于每个测试用例,输出可以产生着色序列的不同排列 $$$p_1, p_2, \ldots, p_n$$$ 的总和,模 $$$998\,244\,353$$$。

示例

输入
复制

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

输出
复制

2
6
4
3
8
0
4
10
867303072

注意

在第一个测试用例中, $$$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$$$秒处的网格。