← 返回题目列表

Codeforces · 2154/F1

F1. 轰炸(简易版)

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

这是问题的简单版本。版本之间的区别在于,在这个版本中,$$$n \le 3000$$$。只有解决了该问题的所有版本,您才能破解。

排列$$$^{\text{*}}$$$ $$$b$$$ 被视为排列$$$a$$$ 的riffle shuffle,如果$$$|a| = |b|$$$ 并且存在 $$$k$$$ 其中 $$$1 \le k \lt |a|$$$ 使得 $$$a_1,a_2,\ldots,a_k$$$ 和 $$$a_{k + 1},a_{k + 2},\ldots,a_{|a|}$$$ 都是子序列$$$^{\text{†}}$$$ $$$b$$$。

例如,$$$[\color{red}{1}, \color{blue}{4}, \color{blue}{5}, \color{red}{2}, \color{red}{3}, \color{blue}{6}]$$$ 是 $$$[\color{red}{1}, \color{red}{2}, \color{red}{3}, \color{blue}{4}, \color{blue}{5}, \color{blue}{6}]$$$ 因为我们可以选择 $$$k = 3$$$ 并且 $$$[\color{red}{1}, \color{red}{2}, \color{red}{3}]$$$ 和 $$$[\color{blue}{4}, \color{blue}{5}, \color{blue}{6}]$$$ 都是子序列。

给你一个长度为 $$$n$$$ 的排列 $$$p$$$,其中一些值被替换为 $$$-1$$$。确定用整数替换每个 $$$-1$$$ 的方法数量,使得 $$$p$$$ 成为 $$$[1,2,\ldots,n]$$$ (排序排列)的 riffle shuffle。

路数可能非常庞大,因此输出它对 $$$998\,244\,353$$$ 取模。

$$$^{\text{*}}$$$长度$$$n$$$的排列是一个由从$$$1$$$到$$$n$$$以任意顺序的$$$n$$$个不同整数组成的数组。例如,$$$[2,3,1,5,4]$$$是一个排列,但$$$[1,2,2]$$$不是排列($$$2$$$在数组中出现两次),$$$[1,3,4]$$$也不是排列($$$n=3$$$但数组中有$$$4$$$)。

$$$^{\text{†}}$$$ 序列 $$$c$$$ 是序列 $$$d$$$ 的子序列,如果 $$$c$$$ 可以通过从任意位置删除几个(可能是零个或全部)元素从 $$$d$$$ 获得。

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 3000$$$) — 排列的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$p_1,p_2,\ldots,p_n$$$ ($$$1 \le p_i \le n$$$ 或 $$$p_i = -1$$$) — $$$p$$$ 的元素。 $$$p$$$ 中不是 $$$-1$$$ 的所有元素都是不同的。

所有测试用例的 $$$n$$$ 总和不超过 $$$3000$$$。

输出

对于每个测试用例,输出填充 $$$p$$$ 的方式数,使其成为 $$$[1,2,\ldots,n]$$$ 模 $$$998\,244\,353$$$ 的 riffle shuffle。

示例

输入
复制

7
5
-1 -1 -1 -1 -1
4
1 2 3 4
5
-1 -1 -1 2 -1
6
-1 3 2 1 -1 -1
18
11 -1 2 -1 -1 -1 -1 6 -1 -1 14 8 9 15 -1 -1 -1 -1
6
-1 3 -1 4 -1 5
3
-1 2 1

输出
复制

27
1
6
0
32
0
0

注意

第三个测试用例的可能排列如下:

  • $$$[\颜色{红色}1,\颜色{蓝色}3,\颜色{蓝色}4,\颜色{红色}2,\颜色{蓝色}5]$$$,
  • $$$[\颜色{红色}1,\颜色{蓝色}4,\颜色{蓝色}5,\颜色{红色}2,\颜色{红色}3]$$$,
  • $$$[\颜色{蓝色}3,\颜色{红色}1,\颜色{蓝色}4,\颜色{红色}2,\颜色{蓝色}5]$$$,
  • $$$[\颜色{蓝色}3,\颜色{蓝色}4,\颜色{红色}1,\颜色{红色}2,\颜色{蓝色}5]$$$,
  • $$$[\颜色{蓝色}4,\颜色{红色}1,\颜色{蓝色}5,\颜色{红色}2,\颜色{红色}3]$$$,
  • $$$[\颜色{蓝色}4、\颜色{蓝色}5、\颜色{红色}1、\颜色{红色}2、\颜色{红色}3]$$$。