3883. [省选 2023]染色数组

【题目描述】

给定一个长度为 $n$ 的正整数数组 $A$，其中每个数都在 $1$ 到 $m$ 之间，从左到右排成一排。现在要将每个数字染成红色或者绿色，我们定义一个染色方案为优秀的染色方案，当且仅当它满足：

1. 每个数 $A_{i}$ 要么被染成红色，要么被染成绿色。

2. 红色的数从左到右依次严格递增，绿色的数从左到右依次严格递减。

例如：$1\;9\;3\;4\;7\;6$ 中，将 $1\;3\;4\;7$ 染成红色，$9\;6$ 染成绿色是优秀的染色方案（$\color{red}1\color{green}9\color{red}{347}\color{green}6$）；$1\;3\;4\;6$ 染成红色，$9\;7$ 染成绿色也是优秀的染色方案（$\color{red}1\color{green}9\color{red}{34}\color{green}7\color{red}6$）。但是将 $1\;4\;7\;6$ 染成红色，$9\;3$ 染成绿色则不是优秀的染色方案，因为 $1\;4\;7\;6$ 不是递增的。$1\;9\;5\;5$ 中，将 $1$ 和任意一个 $5$ 染色红色，$9$ 和另一个 $5$ 染成绿色，也是优秀的染色方案（其中一种是 $\color{red}1\color{green}{95}\color{red}5$）。

如果一个数组至少存在两个不同的优秀的染色方案，那么称这个数组是完美的。(两个染色方案不同当且仅当至少存在一个位置上的数字被染成不同的颜色）。

例如，$1\;9\;3\;4\;7\;6$ 和 $1\;9\;5\;5$ 都是完美的，因为上面已经分别给出了 $2$ 种优秀的染色方案。而 $2\;3\;3\;3$ 则不是完美的，因为找不到任何一种优秀的染色方案。同时 $1\;5\;3\;6\;4$ 也不是完美的，因为仅存在一种优秀的染色方案（$\color{red}1\color{green}5\color{red}{36}\color{green}4$）。

补充说明：如果红色的数只有 $0$ 个或者 $1$ 个，我们也认为它严格递增；同理如果绿色的数只有 $0$ 个或者 $1$ 个，我们也认为它严格递减。例如 $\color{red}{123}$，$\color{red}1\color{green}2\color{red}3$ 都是优秀的的染色方案，因此 $1\;2\;3$ 是完美的数组。

我们定义一种给染色方案打分的方式。

对于每个的有序元素对 $A_{i}, A_{j}(i<j)$ :

1. 如果 $A_{j}$ 染成红色，且 $A_{j}<A_{i}$，则该元素对得 $m-A_{j}+1$ 分;

2. 如果 $A_{j}$ 染成绿色，且 $A_{j}>A_{i}$，则该元素对得 $A_{j}$ 分;

3. 不满足 1 或 2 ，则该元素对得 $0$ 分。

则一个染色方案的得分为所有有序元素对的得分和。

一个完美的数组的得分为它所有优秀的染色方案的得分的最大值。

现在确定数组 $A$ 的前 $t$ 个数 $A_{1}, A_{2}, \ldots，A_{t}$, 你需要回答以下两个问题:

·第一问：有多少种确定 $A$ 中后 $n-t$ 个数的方案使得 $A$ 是一个完美数组？

·第二问：所有可能的完美数组的得分和是多少？

由于答案太大，你只需要输出答案在模 $998244353$ 下的结果即可。

【输入格式】

本题有多组测试数据。

输入的第一行包含一个正整数 $C$，表示数据组数。

接下来包含 $C$ 组数据，每组数据的格式如下：

第一行包含三个整数 $n, m, t$，分别表示数组长度，数组内数字的最大值和确定的前缀长度。

第二行包含 $t$ 个正整数 $A_{1} \ldots A_{t}$，表示已经确定的前缀。

【输出格式】

对于每组测试数据输出一行包含两个用单个空格隔开的整数。

·第一个整数表示优秀数组的数量模 $998244353$ 的值；

·第二个整数表示优秀数组的得分之和模 $998244353$ 的值。

【样例1输入】

5
6 10 6
1 9 3 4 7 6
5 8 4
1 7 2 6
9 10 2
3 6
6 11 6
1 7 5 8 3 9
9 10 5
5 10 6 4 7

【样例1输出】

1 63
8 245
29378 1267731
1 17
78 1820

【样例下载】

样例下载

【评分方式】

每个测试点 $5$ 分。

每一行应按顺序输出两问的答案，不符合输出格式的输出得 $0$ 分。

程序仅回答对第一问得 $1$ 分，仅回答对第二问得 $4$ 分，两问都答对得 $5$ 分。

如果你不回答第一问或第二问，也需要在对应位置上输出任意一个整数以满足输出格式。

【数据规模与约定】

对于所有的数据，保证： $1 \leq C \leq 5$；$2 \leq n \leq 50$；$1 \leq t \leq n$；$1 \leq m \leq 200$；$1 \leq A_{i} \leq m$ 。

【来源】

统一省选 2023 Day2 Task3