← 返回题目列表

Codeforces · 1909/F2

F2. 小排列问题(困难版)

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

在简单版本中,$$$a_i$$$ 的范围为 $$$[0, n]$$$;在硬版本中,$$$a_i$$$ 的范围是 $$$[-1, n]$$$,并且良好排列的定义略有不同。只有当问题的所有版本都得到解决后,你才能进行黑客攻击。

给定一个整数 $$$n$$$ 和一个 $$$a_1, a_2, \dots, a_n$$$ 范围内的整数数组 $$$[-1, n]$$$。

如果对于每个 $$$i$$$,以下条件成立,则 $$$[1, 2, \dots, n]$$$ 的排列 $$$p_1, p_2, \dots, p_n$$$ 是好的:

- 如果 $$$a_i \neq -1$$$,则 $$$[p_1, p_2, \dots, p_i]$$$ 中的值 $$$\leq i$$$ 的数量恰好是 $$$a_i$$$。

计算 $$$[1, 2, \dots, n]$$$ 的良好排列,模 $$$998\,244\,353$$$。

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — 数组 $$$a$$$ 的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$-1 \le a_i \le n$$$),它们描述了良好排列的条件。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一行,其中包含良好排列的数量,以 $$$998\,244\,353$$$ 为模。

示例

输入 #1

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

输出 #1

120
1
4
0
0
494403526
4
0
0
532305727

注意

在第一个测试用例中,长度为 $$$5$$$ 的所有排列都是好的,因此有 $$$120$$$ 好的排列。

在第二个测试用例中,唯一好的排列是 $$$[1, 2, 3, 4, 5]$$$。

在第三个测试用例中,有 $$$4$$$ 好的排列:$$$[2, 1, 5, 6, 3, 4]$$$, $$$[2, 1, 5, 6, 4, 3]$$$, $$$[2, 1, 6, 5, 3, 4]$$$, $$$[2, 1, 6, 5, 4, 3]$$$。例如, $$$[2, 1, 5, 6, 3, 4]$$$ 很好,因为:

- $$$a_1 = 0$$$,$$$[p_1] = [2]$$$ 中有 $$$0$$$ 值 $$$\leq 1$$$;
- $$$a_2 = 2$$$,$$$[p_1, p_2] = [2, 1]$$$ 中有 $$$2$$$ 值 $$$\leq 2$$$;
- $$$a_3 = 2$$$,$$$[p_1, p_2, p_3] = [2, 1, 5]$$$ 中有 $$$2$$$ 值 $$$\leq 3$$$;
- $$$a_4 = 2$$$,$$$[p_1, p_2, p_3, p_4] = [2, 1, 5, 6]$$$ 中有 $$$2$$$ 值 $$$\leq 4$$$;
- $$$a_5 = -1$$$,因此$$$[p_1, p_2, p_3, p_4, p_5]$$$没有限制;
- $$$a_6 = -1$$$,因此 $$$[p_1, p_2, p_3, p_4, p_5, p_6]$$$ 没有限制。