Conditional Mix
Contest: Codeforces Round 831 (Div. 1 + Div. 2)
Difficulty rating: 2600
Tags: combinatorics, dp, math

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$$$.

Input format:
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 format:
Output the number of distinct multisets $$$M$$$ modulo $$$998\,244\,353$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
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\}$$$.

Example input:
6
1 1 2 1 4 3

Example output:
7

Example input:
7
3 5 4 3 7 4 5

Example output:
11

Editorial:
Let $$$cnt_i$$$ denote the number of occurrences of element $$$i$$$ in array $$$a$$$.
Claim: A multiset $$$M$$$ of size $$$n$$$, $$$M_1,M_2,\ldots,M_n$$$ where $$$M_1 \geq M_2 \geq \ldots \geq M_n \geq 0$$$ is good if and only if $$$\sum_{i=1}^{n} M_i=n$$$ and $$$\sum_{i=1}^k M_i \leq \sum_{i=1}^n \min(k,cnt_i)$$$ for every $$$1 \leq k \leq n$$$.
The proof of that claim has been discussed in the comment section here.
We proceed with formulating a dynamic programming solution. Let $$$dp[pos][sum][last]$$$ denote that we have picked a prefix $$$P_1,P_2,\ldots,P_{pos}$$$ such that $$$\sum_{i=1}^{pos} P_i = sum$$$ and $$$P_{pos}=last$$$. Our transition is going from $$$dp[pos][sum][last]$$$ to $$$dp[pos+1][sum+x][x]$$$ for all $$$x \leq last$$$, this can be easily handled using prefix sums. However, we still have $$$O(n^3)$$$ states.
We can cut down the number of states by noting that $$$n \geq \sum_{i=1}^{pos} P_i \geq last \cdot pos$$$. That is, for each value of $$$pos$$$, there are only $$$\frac{n}{pos}$$$ values of $$$last$$$. Since $$$\frac{n}{1}+\frac{n}{2}+\frac{n}{3}+\ldots+\frac{n}{n} \approx n\log n$$$, the number of states is bounded by $$$O(n^2 \log n)$$$.
Time complexity: $$$O(n^2 \log n)$$$