CF1909F1.Small Permutation Problem (Easy Version)

Andy Tunstall - MiniBoss

⠀

In the easy version, the $a_i$ are in the range $[0, n]$; in the hard version, the $a_i$ are in the range $[-1, n]$ and the definition of good permutation is slightly different. You can make hacks only if all versions of the problem are solved.

You are given an integer $n$ and an array $a_1, a_2 \dots, a_n$ of integers in the range $[0, n]$.

A permutation $p_1, p_2, \dots, p_n$ of $[1, 2, \dots, n]$ is good if, for each $i$, the following condition is true:

• the number of values $\leq i$ in $[p_1, p_2, \dots, p_i]$ is exactly $a_i$.

Count the good permutations of $[1, 2, \dots, n]$, modulo $998\,244\,353$.

Andy Tunstall - MiniBoss

⠀

在简单版本中，$a_i$ 的取值范围为 $[0, n]$；在困难版本中，$a_i$ 的取值范围为 $[-1, n]$，且“好排列”的定义略有不同。仅当本题的所有版本均已被解决时，才允许进行 hack。

给定一个整数 $n$ 和一个长度为 $n$ 的整数数组 $a_1, a_2, \dots, a_n$，其中每个 $a_i$ 均属于区间 $[0, n]$。

排列 $p_1, p_2, \dots, p_n$ 是 $[1, 2, \dots, n]$ 的一个好排列，当且仅当对每个 $i$，以下条件成立：

• 在子数组 $[p_1, p_2, \dots, p_i]$ 中，值 $\leq i$ 的元素个数恰好为 $a_i$。

请计算 $[1, 2, \dots, n]$ 的好排列的个数，并对 $998\,244\,353$ 取模。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the length of the array $a$.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le n$), which describe the conditions for a good permutation.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$（$0 \le a_i \le n$），用于描述“好排列”的条件。

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

For each test case, output a single line containing the number of good permutations, modulo $998\,244\,353$.

对于每个测试用例，输出一行，包含好排列的数量对 $998\,244\,353$ 取模的结果。

In the first test case, the only good permutation is $[1, 2, 3, 4, 5]$.

In the second test case, there are $4$ good permutations: $[2, 1, 5, 6, 3, 4]$, $[2, 1, 5, 6, 4, 3]$, $[2, 1, 6, 5, 3, 4]$, $[2, 1, 6, 5, 4, 3]$. For example, $[2, 1, 5, 6, 3, 4]$ is good because:

• $a_1 = 0$, and there are $0$ values $\leq 1$ in $[p_1] = [2]$;
• $a_2 = 2$, and there are $2$ values $\leq 2$ in $[p_1, p_2] = [2, 1]$;
• $a_3 = 2$, and there are $2$ values $\leq 3$ in $[p_1, p_2, p_3] = [2, 1, 5]$;
• $a_4 = 2$, and there are $2$ values $\leq 4$ in $[p_1, p_2, p_3, p_4] = [2, 1, 5, 6]$;
• $a_5 = 4$, and there are $4$ values $\leq 5$ in $[p_1, p_2, p_3, p_4, p_5] = [2, 1, 5, 6, 3]$;
• $a_6 = 6$, and there are $6$ values $\leq 6$ in $[p_1, p_2, p_3, p_4, p_5, p_6] = [2, 1, 5, 6, 3, 4]$.

In the third test case, there are no good permutations, because there are no permutations with $a_6 = 5$ values $\leq 6$ in $[p_1, p_2, p_3, p_4, p_5, p_6]$.

在第一个测试用例中，唯一的好排列是 $[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 = 4$，且在 $[p_1, p_2, p_3, p_4, p_5] = [2, 1, 5, 6, 3]$ 中有 $4$ 个值 $\leq 5$；
• $a_6 = 6$，且在 $[p_1, p_2, p_3, p_4, p_5, p_6] = [2, 1, 5, 6, 3, 4]$ 中有 $6$ 个值 $\leq 6$。

在第三个测试用例中，不存在好排列，因为没有任何排列能满足：在 $[p_1, p_2, p_3, p_4, p_5, p_6]$ 中恰好有 $a_6 = 5$ 个值 $\leq 6$。