CFCF2190E.Median Permutation

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

对于一个长度为 $m \ge 3$ 的排列 $q$ ，定义 $f(q)$ 为一个长度为 $m-2$ 的序列 $b$ ，其中对于所有 $1 \le i \le m-2$ ，都有 $b_i = \operatorname{med}(q_i, q_{i+1}, q_{i+2})$ 。这里， $\operatorname{med}(x, y, z)$ 表示 $\{x, y, z\}$ 中的第二小元素。

给定一个长度为 $n$ 的数组 $a$ ，其中有些元素可能为 $0$ 。保证 $a$ 中包含 $1$ 和 $n$ ，即存在下标 $i, j$ 使得 $a_i = 1$ 并且 $a_j = n$ 。

请你计算有多少个满足以下条件的长度为 $n$ 的排列 $p$ ：

$p$ 与 $a$ 一致：对于所有 $1 \le i \le n$ ，如果 $a_i \neq 0$ ，则 $p_i = a_i$ 。
$f(p)$ 的所有元素都互不相同。

由于答案可能很大，请输出对 $998\,244\,353$ 取模的结果。

$^{\text{∗}}$ 排列指长度为 $n$ 的、包含 $1$ 到 $n$ 且各不相同的数的序列。例如， $[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是（ $2$ 出现了两次）， $[1,3,4]$ 也不是（ $n=3$ 却出现了 $4$ ）。

输入格式

每组测试包含多组数据。第一行包含测试组数 $t$ （ $1 \le t \le 10^4$ ）。以下是每组测试的数据。

每组测试的第一行包含一个整数 $n$ ，表示数组的长度（ $3 \le n \le 2 \cdot 10^5$ ）。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ （ $0 \le a_i \le n$ ）。

保证 $a$ 中所有非零元素均互不相同，且 $a$ 中一定包含 $1$ 和 $n$ 。

保证所有测试数据中 $n$ 之和不超过 $2 \cdot 10^5$ 。

输出格式

对于每组测试数据，输出一行一个整数，表示满足条件的排列 $p$ 的个数，对 $998\,244\,353$ 取模。

输入输出样例

输入#1

5
3
1 3 2
5
0 5 4 1 0
7
0 0 1 0 0 7 0
10
1 10 0 0 0 0 0 0 0 0
15
0 0 10 0 0 15 0 0 6 7 0 1 0 0 3

输出#1

说明/提示

在第一个样例中，唯一与输入一致的排列是 $p=[1,3,2]$ 。有 $f(p)=[2]$ ，因为 $\operatorname{med}(1,3,2)=2$ 。 $f(p)$ 的元素互不相同，因此这个排列是合法的。答案为 $1$ 。

在第二个样例中，有两种与输入一致的排列： $p=[3,5,4,1,2]$ 和 $p=[2,5,4,1,3]$ 。

对于 $p=[3,5,4,1,2]$ ，有 $f(p)=[4,4,2]$ 。
对于 $p=[2,5,4,1,3]$ ，有 $f(p)=[4,4,3]$ 。

在这两种情况下， $f(p)$ 中值 $4$ 出现了两次。因此没有合法排列，答案是 $0$ 。

首页