A92147.「2021 营员交流」数串

本题包含三个问题：

• 问题 0：给定一个长度为 $n$ 的序列以及它的后缀数组 $\boldsymbol p$，求这个序列中有多少个不同的数。
• 问题 1：给定一个长度为 $n$ 的排列 $\boldsymbol p$，对于所有满足后缀数组为 $\boldsymbol p$ 的长度为 $n$ 的序列，求不同的数的数量的最小值。
• 问题 2：给定一个长度为 $n$ 的残缺的排列 $\tilde {\boldsymbol p}$ (有 $k$ 个位置未知)，对于所有 $k!$ 种完整的排列，求问题 1 的答案之和。

在不同的测试点中，你将可能需要回答不同的问题。我们将用 $\mathrm{op}$ 来指代你需要回答的问题编号 (对应上述 $0, 1, 2$)。

在问题 2 中，由于答案可能很大，因此你只需要输出答案对 $998244353$ 取模的结果即可。

第一行包含两个非负整数 $n, \mathrm{op}$，分别表示鼠的数量和子问题的类型。

如果 $\mathrm{op} = 0$，则第二行包含 $n$ 个正整数 $a_1, a_2, \ldots, a_n$，表示每只鼠的体型大小；第三行包含 $n$ 个正整数 $p_1, p_2, \cdots, p_n$，表示小 S 得到的排列。

如果 $\mathrm{op} = 1$，则第二行包含 $n$ 个正整数 $p_1, p_2, \ldots, p_n$，表示小 S 得到的排列。

如果 $\mathrm{op} = 2$，则第二行包含 $n$ 个非负整数 $\tilde p_1, \tilde p_2, \ldots, \tilde p_n$，表示小 S 的残缺的排列。$\tilde p_i = 0$ 表示这一个值被鼠 "咬掉" 的，否则 $\tilde p_i$ 表示排列中第 $i$ 位的值。

每行中的两个整数之间均用一个空格隔开，鼠的编号是从 $1$ 开始的。

输出一行一个整数，表示对应问题的答案对 $998244353$ 取模的结果。

对于所有的测试点，均满足 $1 \leq n \leq 5 \times 10^5; 1 \leq a_i \leq 10^9; 1 \leq p_i \leq n; 0 \leq \tilde p_i \leq n$，当 $\mathrm{op} = 2$ 时存在至少一个 $i$ 使得 $\tilde p_i = 0$。

问题类型 ($\mathrm{op} =$)	测试点编号	$n$	其它性质
0	1	$\leq 10$	无
0	2	$\leq 5 \times 10^5$	无
0	3	$\leq 5 \times 10^5$	无
1	4	$= 3$	无
1	5	$= 5$	无
1	6	$\leq 10$	无
1	7	$\leq 500$	无
1	8	$\leq 5000$	无
1	9	$\leq 5000$	无
1	10	$\leq 50000$	无
1	11	$\leq 50000$	无
1	12	$\leq 5 \times 10^5$	$p_i = i$
1	13	$\leq 5 \times 10^5$	无
1	14	$\leq 5 \times 10^5$	无
2	15	$= 3$	无
2	16	$= 5$	无
2	17	$\leq 10$	无
2	18	$\leq 500$	满足 $\tilde p_i = 0$ 的 $i$ 不超过 $5$ 个
2	19	$\leq 5000$	无
2	20	$\leq 5000$	满足 $\tilde p_i = 0$ 的 $i$ 不超过 $5$ 个
2	21	$\leq 50000$	无
2	22	$\leq 50000$	所有 $\tilde p_i = 0$
2	23	$\leq 5 \times 10^5$	存在整数 $t$ ($1 \leq t < n$)，满足 $\tilde p_i = \begin{cases} i & i \leq t \\ 0 & i > t \end{cases}$
2	24	$\leq 5 \times 10^5$	存在整数 $t$ ($1 \leq t < n$)，满足 $\tilde p_i = 0$ 当且仅当 $i > t$
2	25	$\leq 5 \times 10^5$	无