Conditional Mix

题意翻译

第一行输入一个正整数 $n\le 2\times 10^3$。 第二行输入 $n$ 个正整数 $1\le a_i\le n$。 把 $a_i$ 看成一个一元集 $\{a_i\}$ , 每次可以合并两个交集为空的集合（合并完集合数 $-1$）。可以经过任意次合并。设合并完每个集合的元素个数组成可重集 $S$。求 $S$ 的种类数，对 $998244353$ 取模。

题目描述

Pak Chanek is given an array $ a $ of $ n $ integers. For each $ i $ ( $ 1 \leq i \leq n $ ), Pak Chanek will write the one-element set $ \{a_i\} $ on a whiteboard. After that, in one operation, Pak Chanek may do the following: 1. Choose two different sets $ S $ and $ T $ on the whiteboard such that $ S \cap T = \varnothing $ ( $ S $ and $ T $ do not have any common elements). 2. Erase $ S $ and $ T $ from the whiteboard and write $ S \cup T $ (the union of $ S $ and $ T $ ) onto the whiteboard. After performing zero or more operations, Pak Chanek will construct a multiset $ M $ containing the sizes of all sets written on the whiteboard. In other words, each element in $ M $ corresponds to the size of a set after the operations. How many distinct $ ^\dagger $ multisets $ M $ can be created by this process? Since the answer may be large, output it modulo $ 998\,244\,353 $ . $ ^\dagger $ Multisets $ B $ and $ C $ are different if and only if there exists a value $ k $ such that the number of elements with value $ k $ in $ B $ is different than the number of elements with value $ k $ in $ C $ .

输入输出格式

输入格式

The first line contains a single integer $ n $ ( $ 1 \le n \le 2000 $ ). The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \leq a_i \leq n $ ).

输出格式

Output the number of distinct multisets $ M $ modulo $ 998\,244\,353 $ .

输入输出样例

输入样例 #1

6
1 1 2 1 4 3

输出样例 #1

7

输入样例 #2

7
3 5 4 3 7 4 5

输出样例 #2

11

说明

In the first example, the possible multisets $ M $ are $ \{1,1,1,1,1,1\} $ , $ \{1,1,1,1,2\} $ , $ \{1,1,1,3\} $ , $ \{1,1,2,2\} $ , $ \{1,1,4\} $ , $ \{1,2,3\} $ , and $ \{2,2,2\} $ . As an example, let's consider a possible sequence of operations. 1. In the beginning, the sets are $ \{1\} $ , $ \{1\} $ , $ \{2\} $ , $ \{1\} $ , $ \{4\} $ , and $ \{3\} $ . 2. Do an operation on sets $ \{1\} $ and $ \{3\} $ . Now, the sets are $ \{1\} $ , $ \{1\} $ , $ \{2\} $ , $ \{4\} $ , and $ \{1,3\} $ . 3. Do an operation on sets $ \{2\} $ and $ \{4\} $ . Now, the sets are $ \{1\} $ , $ \{1\} $ , $ \{1,3\} $ , and $ \{2,4\} $ . 4. Do an operation on sets $ \{1,3\} $ and $ \{2,4\} $ . Now, the sets are $ \{1\} $ , $ \{1\} $ , and $ \{1,2,3,4\} $ . 5. The multiset $ M $ that is constructed is $ \{1,1,4\} $ .

**题目大意**：

给定一个数组，数组中的每个元素代表一个一元集。每次操作可以合并两个没有交集的集合。求最终可能形成的所有集合大小的种类数，结果对 $998244353$ 取模。

**输入输出数据格式**：

**输入格式**：
- 第一行输入一个正整数 $n \le 2 \times 10^3$。
- 第二行输入 $n$ 个正整数 $1 \le a_i \le n$。

**输出格式**：
- 输出形成的不同种类集合大小的数量，对 $998244353$ 取模。

**输入输出样例**：

**输入样例 #1**：
```
6
1 1 2 1 4 3
```

**输出样例 #1**：
```
7
```

**输入样例 #2**：
```
7
3 5 4 3 7 4 5
```

**输出样例 #2**：
```
11
```**题目大意**： 给定一个数组，数组中的每个元素代表一个一元集。每次操作可以合并两个没有交集的集合。求最终可能形成的所有集合大小的种类数，结果对 $998244353$ 取模。 **输入输出数据格式**： **输入格式**： - 第一行输入一个正整数 $n \le 2 \times 10^3$。 - 第二行输入 $n$ 个正整数 $1 \le a_i \le n$。 **输出格式**： - 输出形成的不同种类集合大小的数量，对 $998244353$ 取模。 **输入输出样例**： **输入样例 #1**： ``` 6 1 1 2 1 4 3 ``` **输出样例 #1**： ``` 7 ``` **输入样例 #2**： ``` 7 3 5 4 3 7 4 5 ``` **输出样例 #2**： ``` 11 ```