这是问题的困难版本。版本之间的区别在于,在这个版本中,$$$n \le 10^6$$$。只有解决了该问题的所有版本,您才能破解。
排列$$$^{\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 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 10^6$$$) — 排列的长度。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$p_1,p_2,\ldots,p_n$$$ ($$$1 \le p_i \le n$$$ 或 $$$p_i = -1$$$) — $$$p$$$ 的元素。 $$$p$$$ 中不是 $$$-1$$$ 的所有元素都是不同的。
所有测试用例的 $$$n$$$ 总和不超过 $$$10^6$$$。
输出
对于每个测试用例,输出填充 $$$p$$$ 的方式数,使其成为 $$$[1,2,\ldots,n]$$$ 模 $$$998\,244\,353$$$ 的 riffle shuffle。
示例
输入复制
75-1 -1 -1 -1 -141 2 3 45-1 -1 -1 2 -16-1 3 2 1 -1 -11811 -1 2 -1 -1 -1 -1 6 -1 -1 14 8 9 15 -1 -1 -1 -16-1 3 -1 4 -1 53-1 2 1
输出复制
271603200
注意
第三个测试用例的可能排列如下:
- $$$[\颜色{红色}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]$$$。