Divisor Set
Contest: Educational Codeforces Round 76 (Rated for Div. 2)
Difficulty rating: 2600
Tags: divide and conquer, fft, greedy, math, number theory

You are given an integer $$$x$$$ represented as a product of $$$n$$$ its prime divisors $$$p_1 \cdot p_2, \cdot \ldots \cdot p_n$$$. Let $$$S$$$ be the set of all positive integer divisors of $$$x$$$ (including $$$1$$$ and $$$x$$$ itself).

We call a set of integers $$$D$$$ good if (and only if) there is no pair $$$a \in D$$$, $$$b \in D$$$ such that $$$a \ne b$$$ and $$$a$$$ divides $$$b$$$.

Find a good subset of $$$S$$$ with maximum possible size. Since the answer can be large, print the size of the subset modulo $$$998244353$$$.

Input format:
The first line contains the single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of prime divisors in representation of $$$x$$$.

The second line contains $$$n$$$ integers $$$p_1, p_2, \dots, p_n$$$ ($$$2 \le p_i \le 3 \cdot 10^6$$$) — the prime factorization of $$$x$$$.

Output format:
Print the maximum possible size of a good subset modulo $$$998244353$$$.

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

Note:
In the first sample, $$$x = 2999999 \cdot 43 \cdot 2999957$$$ and one of the maximum good subsets is $$$\{ 43, 2999957, 2999999 \}$$$.

In the second sample, $$$x = 2 \cdot 3 \cdot 2 \cdot 3 \cdot 2 \cdot 2 = 144$$$ and one of the maximum good subsets is $$$\{ 9, 12, 16 \}$$$.

Example input:
3
2999999 43 2999957

Example output:
3

Example input:
6
2 3 2 3 2 2

Example output:
3

Editorial:
The problem consists of two parts: what do we want to calculate and how to calculate it?
What do we want to calculate? There are several ways to figure it out. At first, you could have met this problem before and all you need is to remember a solution.
At second, you can come up with the solution in a purely theoretical way — Hasse diagram can help with it greatly. Let's define $$$deg(x)$$$ as the number of primes in prime factorization of $$$x$$$. For example, $$$deg(2 \cdot 3 \cdot 2) = 3$$$ and $$$deg(1) = 0$$$. If you look at Hasse diagram of $$$p_1 \cdot \ldots \cdot p_n$$$ you can see that all divisors with $$$deg(d) = i$$$ lies on level $$$i$$$. If $$$x$$$ is divisible by $$$y$$$ then $$$deg(x) > deg(y)$$$ so all divisors on the same level don't divide each other. Moreover, the diagram somehow symmetrical about its middle level and sizes of levels are increasing while moving to the middle. It gives us an idea that the answer is the size of the middle level, i.e. the number of divisors with $$$deg(d) = \frac{n}{2}$$$.
The final way is just to brute force the answers for small $$$x$$$-s and find the sequence in OEIS with name A096825, where the needed formulas are described.
The second step is to calculate the number of divisors with $$$deg(d) = \frac{n}{2}$$$. Suppose we have $$$m$$$ distinct primes $$$p_j$$$ and the number of occurences of $$$p_j$$$ is equal to $$$cnt_j$$$. Then we need to calculate pretty standard knapsack problem where you need to calculate number of ways to choose subset of size $$$\frac{n}{2}$$$ where you can take each $$$p_j$$$ up to $$$cnt_j$$$ times. Or, formally, number of vectors $$$(x_1, x_2, \dots x_m)$$$ with $$$\sum\limits_{j = 0}^{j = m}{x_j} = \frac{n}{2}$$$ and $$$0 \le x_j \le cnt_j$$$.
Calculating the answer using $$$dp[pos][sum]$$$ will lead to time limit, so we need to make the following transformation. Let's build for each $$$p_j$$$ a polynomial $$$f_j(x) = 1 + x + x^2 + \dots + x^{cnt_j}$$$. Now the answer is just a coefficient before $$$x^{\frac{n}{2}}$$$ in product $$$f_1(x) \cdot f_2(x) \cdot \ldots \cdot f_m(x)$$$. Note, that the product has degree $$$n$$$, so we can multiply polynomials efficiently with integer FFT in the special order to acquire $$$O(n \log^2(n))$$$ time complexity.
There several ways to choose the order of multiplications. At first, you can, at each step, choose two polynomials with the lowest degree and multiply them. At second, you can use the divide-and-conquer technique by dividing the current segment in two with pretty same total degrees. At third, you can also use D-n-C but divide the segment at halves and, it seems still to be $$$O(n \log^2(n))$$$ in total.
What about the proof of the solution? Thanks to tyrion__ for the link at the article: https://pure.tue.nl/ws/files/4373475/597494.pdf.
The result complexity is $$$O(n \log^2(n))$$$ time and $$$O(n)$$$ space (if carefully written). Note, that the hidden constant in integer FFT is pretty high and highly depends on the implementation, so it's possible for poor implementations not to pass the time limit.