310965: CF1914G1. Light Bulbs (Easy Version)
Description
The easy and hard versions of this problem differ only in the constraints on $n$. In the easy version, the sum of values of $n^2$ over all test cases does not exceed $10^6$. Furthermore, $n$ does not exceed $1000$ in each test case.
There are $2n$ light bulbs arranged in a row. Each light bulb has a color from $1$ to $n$ (exactly two light bulbs for each color).
Initially, all light bulbs are turned off. You choose a set of light bulbs $S$ that you initially turn on. After that, you can perform the following operations in any order any number of times:
- choose two light bulbs $i$ and $j$ of the same color, exactly one of which is on, and turn on the second one;
- choose three light bulbs $i, j, k$, such that both light bulbs $i$ and $k$ are on and have the same color, and the light bulb $j$ is between them ($i < j < k$), and turn on the light bulb $j$.
You want to choose a set of light bulbs $S$ that you initially turn on in such a way that by performing the described operations, you can ensure that all light bulbs are turned on.
Calculate two numbers:
- the minimum size of the set $S$ that you initially turn on;
- the number of sets $S$ of minimum size (taken modulo $998244353$).
The first line of the input contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Then follow the descriptions of the test cases.
The first line of each test case contains a single integer $n$ ($2 \le n \le 1000$) — the number of pairs of light bulbs.
The second line of each test case contains $2n$ integers $c_1, c_2, \dots, c_{2n}$ ($1 \le c_i \le n$), where $c_i$ is the color of the $i$-th light bulb. For each color from $1$ to $n$, exactly two light bulbs have this color.
Additional constraint on the input: the sum of values of $n^2$ over all test cases does not exceed $10^6$.
OutputFor each test case, output two integers:
- the minimum size of the set $S$ that you initially turn on;
- the number of sets $S$ of minimum size (taken modulo $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 2Output
2 4 1 2 1 4 2 8
Output
这个问题的简单和困难版本仅在关于 $ n $ 的约束上有所不同。在简单版本中，所有测试用例的 $ n^2 $ 值的总和不超过 $ 10^6 $。此外，每个测试用例中 $ n $ 的值不超过 1000。
有 $ 2n $ 个灯泡排成一行，每个灯泡有一个从 1 到 $ n $ 的颜色（每种颜色恰好有两个灯泡）。
最初，所有灯泡都是关闭的。你选择一个灯泡集合 $ S $，最初打开这些灯泡。在此之后，你可以按任何顺序、任意次数执行以下操作：
1. 选择两个相同颜色的灯泡 $ i $ 和 $ j $，其中恰好有一个是开着的，然后打开另一个；
2. 选择三个灯泡 $ i, j, k $，使得灯泡 $ i $ 和 $ k $ 都是开着的且颜色相同，灯泡 $ j $ 位于它们之间（$ i < j < k $），然后打开灯泡 $ j $。
你想要选择一个灯泡集合 $ S $，使得通过执行上述操作，你可以确保所有灯泡都被打开。
计算两个数字：
1. 初始打开的集合 $ S $ 的最小大小；
2. 最小大小的集合 $ 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 $）。
示例输入输出见原文。题目大意： 这个问题的简单和困难版本仅在关于 $ n $ 的约束上有所不同。在简单版本中，所有测试用例的 $ n^2 $ 值的总和不超过 $ 10^6 $。此外，每个测试用例中 $ n $ 的值不超过 1000。 有 $ 2n $ 个灯泡排成一行，每个灯泡有一个从 1 到 $ n $ 的颜色（每种颜色恰好有两个灯泡）。 最初，所有灯泡都是关闭的。你选择一个灯泡集合 $ S $，最初打开这些灯泡。在此之后，你可以按任何顺序、任意次数执行以下操作： 1. 选择两个相同颜色的灯泡 $ i $ 和 $ j $，其中恰好有一个是开着的，然后打开另一个； 2. 选择三个灯泡 $ i, j, k $，使得灯泡 $ i $ 和 $ k $ 都是开着的且颜色相同，灯泡 $ j $ 位于它们之间（$ i < j < k $），然后打开灯泡 $ j $。 你想要选择一个灯泡集合 $ S $，使得通过执行上述操作，你可以确保所有灯泡都被打开。 计算两个数字： 1. 初始打开的集合 $ S $ 的最小大小； 2. 最小大小的集合 $ 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 $）。 示例输入输出见原文。