Counting Factorizations
Contest: Codeforces Round 856 (Div. 2)
Difficulty rating: 1900
Tags: combinatorics, divide and conquer, dp, math, number theory

The prime factorization of a positive integer $$$m$$$ is the unique way to write it as $$$\displaystyle m=p_1^{e_1}\cdot p_2^{e_2}\cdot \ldots \cdot p_k^{e_k}$$$, where $$$p_1, p_2, \ldots, p_k$$$ are prime numbers, $$$p_1 < p_2 < \ldots < p_k$$$ and $$$e_1, e_2, \ldots, e_k$$$ are positive integers.

For each positive integer $$$m$$$, $$$f(m)$$$ is defined as the multiset of all numbers in its prime factorization, that is $$$f(m)=\{p_1,e_1,p_2,e_2,\ldots,p_k,e_k\}$$$.

For example, $$$f(24)=\{2,3,3,1\}$$$, $$$f(5)=\{1,5\}$$$ and $$$f(1)=\{\}$$$.

You are given a list consisting of $$$2n$$$ integers $$$a_1, a_2, \ldots, a_{2n}$$$. Count how many positive integers $$$m$$$ satisfy that $$$f(m)=\{a_1, a_2, \ldots, a_{2n}\}$$$. Since this value may be large, print it modulo $$$998\,244\,353$$$.

Input format:
The first line contains one integer $$$n$$$ ($$$1\le n \le 2022$$$).

The second line contains $$$2n$$$ integers $$$a_1, a_2, \ldots, a_{2n}$$$ ($$$1\le a_i\le 10^6$$$)  — the given list.

Output format:
Print one integer, the number of positive integers $$$m$$$ satisfying $$$f(m)=\{a_1, a_2, \ldots, a_{2n}\}$$$ modulo $$$998\,244\,353$$$.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

Note:
In the first sample, the two values of $$$m$$$ such that $$$f(m)=\{1,2,3,3\}$$$ are $$$m=24$$$ and $$$m=54$$$. Their prime factorizations are $$$24=2^3\cdot 3^1$$$ and $$$54=2^1\cdot 3^3$$$.

In the second sample, the five values of $$$m$$$ such that $$$f(m)=\{2,2,3,5\}$$$ are $$$200, 225, 288, 500$$$ and $$$972$$$.

In the third sample, there is no value of $$$m$$$ such that $$$f(m)=\{1,4\}$$$. Neither $$$1^4$$$ nor $$$4^1$$$ are prime factorizations because $$$1$$$ and $$$4$$$ are not primes.

Example input:
2
1 3 2 3

Example output:
2

Example input:
2
2 2 3 5

Example output:
5

Editorial:
First, we will count how many times each different element in $$$a$$$ occurs and check which of these elements are prime numbers. This can be done by checking for each element if it has a divisor up to its square root or using the Sieve of Eratosthenes.
To construct a number $$$m$$$ such that $$$f(m)=\{a_1, a_2, \ldots, a_{2n}\}$$$ we have to choose $$$n$$$ elements of $$$a$$$ to be the primes in its factorization and $$$n$$$ elements to be the exponents. The numbers we choose to be the primes in the factorization have to be prime numbers and distinct. If there are less than $$$n$$$ distinct primes in $$$a$$$, then there is no number $$$m$$$ satisfying the property. So, from now on we will assume there are at least $$$n$$$ distinct prime numbers in $$$a$$$.
Let $$$b_1,b_2, \ldots, b_s$$$ be the number of occurrences of each non-prime number in $$$a$$$ and let $$$c_1, c_2, \ldots, c_t$$$ be the number of occurrences of each prime number in $$$a$$$. After we choose the primes for the factorization, let $$$c'_1, c'_2, \ldots, c'_t$$$ be the remaining number of occurrences of each prime number. As we can choose each prime number at most once, then $$$c'_i=c_i$$$ or $$$c'_i=c_i-1$$$. For each way of choosing the primes, the number of possible values for $$$m$$$ is $$$\displaystyle \frac{n!}{b_1!\:\:b_2!\ldots b_s!\:\:c'_1!\:\:c'_2!\ldots c'_t!}$$$ because this is the number of ways to choose where to place the exponents. The answer to the problem is the sum of all these numbers over all ways of choosing the prime numbers.
Observe that when we sum terms of the form $$$\displaystyle \frac{n!}{b_1!\:\:b_2!\ldots b_s!\:\:c'_1!\:\:c'_2!\ldots c'_t!}$$$, the value $$$\displaystyle \frac{n!}{b_1!\:\:b_2!\ldots b_s!}$$$ is a common factor over all these terms. Thus, we just need to find the sum of the terms $$$\displaystyle \frac{1}{c'_1!\:\:c'_2!\ldots c'_t!}$$$ and then multiply by the common factor.
To find this sum, we will use dynamic programming. Let $$$g(x,y)$$$ be the sum considering only the primes from the $$$x$$$-th of them and assuming that $$$y$$$ primes need to be chosen (or that $$$n-y$$$ primes are already chosen). Then $$$\displaystyle g(x,y)=\frac{1}{c_x!}\times g(x+1,y)+\frac{1}{(c_x-1)!}\times g(x+1,y-1)$$$. The value of $$$g(1,n)$$$ will give the desired sum.
Intended complexity: $$$\mathcal{O}(n^2)$$$ (plus the complexity of primality checking)