原题链接

Problem - 1914G1 - Codeforces

1. 做完后记得选择这个选择题。 {{ select(1) }}

• 提交并且通过了
• 还没有提交，或者提交了 WA 了。

题目描述

给定一个长度为 $2n$ 的数组，$1$ 到 $n$ 中每个数出现两次。

现在你可以对一个集合 $S$ 的数进行初始染色，接下来遵从以下规则：

• 如果一个数被染色了，则另一个相同的数也会被染色。
• 如果某两个相同的数被染色了，那么它们之间所有数都会被染色。

你要求出最小可能的 $S$ 集合大小使得所有数都被染色，并且求出有多少 $S$ 满足其大小到达最小。输出对 $998244353$ 取模。

输入格式

输入

输入的第一行包含一个整数 $t$ ( $1 \le t \le 10^4$ )--测试用例的数量。然后是测试用例的说明。

每个测试用例的第一行包含一个整数 $n$ ( $2 \le n \le 1000$ ) - 灯泡的对数。

每个测试用例的第二行包含 $2n$ 个整数 $c_1, c_2, \dots, c_{2n}$ ( $1 \le c_i \le n$ )，其中 $c_i$ 是第 $i$ 个灯泡的颜色。对于从 $1$ 到 $n$ 的每种颜色，正好有两个灯泡具有这种颜色。

输入的附加限制：所有测试用例中 $n^2$ 的值之和不超过 $10^6$ 。

输出格式

输出

对于每个测试用例，输出两个整数：

• 最初开启的集合 $S$ 的最小大小；
• 最小大小的集合 $S$ 的数量（取模 $998244353$ ）。

4
2
2 2 1 1
2
1 2 2 1
2
1 2 1 2
5
3 4 4 5 3 1 1 5 2 2

2 4
1 2
1 4
2 8