← 返回题目

题库练习「2021 营员交流」数串

← 上一题下一题 →

A6451 | $「2021 营员交流」数串$

时间限制1s

内存限制512MB

通过 / 提交0/0

题目描述

本题包含三个问题： * 问题 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

3 0
10 20 30
1 2 3

输出 #1

输入 #2

3 1
1 2 3

输出 #2

输入 #3

3 2
0 0 3

输出 #3

对于所有的测试点，均满足 $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$ | 无 |

C++ 编辑器

输入

输出