P9171 [NOI Qualifier Joint Contest 2023] Colored Array

Given a positive integer array $A$ of length $n$, where each number is between $1$ and $m$, arranged from left to right. Now we want to color each number either red or green. We call a coloring scheme an excellent coloring scheme if and only if it satisfies: 1. Each number $A_{i}$ is colored either red or green. 2. The red numbers are strictly increasing from left to right, and the green numbers are strictly decreasing from left to right. For example, in $1\;9\;3\;4\;7\;6$, coloring $1\;3\;4\;7$ red and $9\;6$ green is an excellent coloring scheme ($\color{red}1\color{green}9\color{red}347\color{green}6$). Coloring $1\;3\;4\;6$ red and $9\;7$ green is also an excellent coloring scheme ($\color{red}1\color{green}9\color{red}34\color{green}7\color{red}6$). However, coloring $1\;4\;7\;6$ red and $9\;3$ green is **not** an excellent coloring scheme, because $1\;4\;7\;6$ is not increasing. In $1\;9\;5\;5$, coloring $1$ and either one of the $5$'s red, and coloring $9$ and the other $5$ green, is also an excellent coloring scheme (one possible scheme is $\color{red}1\color{green}95\color{red}5$). If an array has **at least two different** excellent coloring schemes, then this array is called **perfect**. (Two coloring schemes are different if and only if there exists at least one position where the number is colored differently.) For example, $1\;9\;3\;4\;7\;6$ and $1\;9\;5\;5$ are both perfect, because $2$ excellent coloring schemes have already been given for each above. But $2\;3\;3\;3$ is not perfect, because no excellent coloring scheme exists. Also, $1\;5\;3\;6\;4$ is not perfect, because there is only one excellent coloring scheme ($\color{red}1\color{green}5\color{red}36\color{green}4$). Additional note: If there are only $0$ or $1$ red numbers, we also consider them strictly increasing; similarly, if there are only $0$ or $1$ green numbers, we also consider them strictly decreasing. For example, $\color{red}123$ and $\color{red}1\color{green}2\color{red}3$ are both excellent coloring schemes, so $1\;2\;3$ is a perfect array. We define a way to score a coloring scheme. For each ordered pair of elements $A_{i}, A_{j}(i

**This problem contains multiple test cases.** The first line of input contains a positive integer $C$, denoting the number of test cases. Then there are $C$ test cases. Each test case is formatted as follows: The first line contains three integers $n, m, t$, denoting the array length, the maximum value in the array, and the length of the fixed prefix. The second line contains $t$ positive integers $A_{1} \ldots A_{t}$, denoting the fixed prefix.

For each test case, output one line containing two integers separated by a single space. - The first integer is the number of perfect arrays modulo $998244353$. - The second integer is the sum of scores of all perfect arrays modulo $998244353$.

**【Scoring】** Each test point is worth $5$ points. Each line should output the answers to the two questions in order. Any output that does not match the required format will get $0$ points. If your program answers only Question 1 correctly, you get $1$ point. If it answers only Question 2 correctly, you get $4$ points. If it answers both correctly, you get $5$ points. If you do not answer Question 1 or Question 2, you still need to output any integer in the corresponding position to satisfy the output format. **【Subtasks】** For all testdata, it is guaranteed that: $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$.  Translated by ChatGPT 5