310183: CF1794D. Counting Factorizations
Memory Limit：256 MB
Time Limit：4 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Counting Factorizations
题意翻译
任何一个正整数 $m$ 都可以被唯一的分解为 $p_1^{e_1} \cdot p_2^{e_2} \ldots p_k^{e_k}$ 的形式。将正整数 $m$ 的唯一质数分解转化为一个长度为 $2k$ 的 **可重集合** 记为 $f(m)$。 $$ f(m)=\{p_1,e_1,p_2,e_2,p_3,e_3, \ldots ,p_k,e_k \}$$ 给定正整数 $n$ 和一个长度为 $2n$ 的可重集 $A$。求出满足 $f(m) = A$ 的正整数 $m$ 的个数。答案对 $998\ 244\ 353$ 取模。题目描述
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 $ .输入输出格式
输入格式
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.
输出格式
Print one integer, the number of positive integers $ m $ satisfying $ f(m)=\{a_1, a_2, \ldots, a_{2n}\} $ modulo $ 998\,244\,353 $ .
输入输出样例
输入样例 #1
2
1 3 2 3输出样例 #1
2输入样例 #2
2
2 2 3 5输出样例 #2
5输入样例 #3
1
1 4输出样例 #3
0说明
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.Input
题意翻译
任何一个正整数 $m$ 都可以被唯一的分解为 $p_1^{e_1} \cdot p_2^{e_2} \ldots p_k^{e_k}$ 的形式。将正整数 $m$ 的唯一质数分解转化为一个长度为 $2k$ 的 **可重集合** 记为 $f(m)$。 $$ f(m)=\{p_1,e_1,p_2,e_2,p_3,e_3, \ldots ,p_k,e_k \}$$ 给定正整数 $n$ 和一个长度为 $2n$ 的可重集 $A$。求出满足 $f(m) = A$ 的正整数 $m$ 的个数。答案对 $998\ 244\ 353$ 取模。Output
**题目大意：**
任何正整数 $ m $ 都可以被唯一地分解为 $ p_1^{e_1} \cdot p_2^{e_2} \ldots p_k^{e_k} $ 的形式，其中 $ p_1, p_2, \ldots, p_k $ 是质数，且 $ p_1 < p_2 < \ldots < p_k $，$ e_1, e_2, \ldots, e_k $ 是正整数。将正整数 $ m $ 的唯一质数分解转化为一个长度为 $ 2k $ 的 **可重集合** 记为 $ f(m) $。
给定正整数 $ n $ 和一个长度为 $ 2n $ 的可重集 $ A $。求出满足 $ f(m) = A $ 的正整数 $ m $ 的个数。答案对 $ 998\ 244\ 353 $ 取模。
**输入格式：**
第一行包含一个整数 $ n $（$ 1 \le n \le 2022 $）。
第二行包含 $ 2n $ 个整数 $ a_1, a_2, \ldots, a_{2n} $（$ 1 \le a_i \le 10^6 $）——给定的列表。
**输出格式：**
打印一个整数，满足 $ f(m) = \{a_1, a_2, \ldots, a_{2n}\} $ 的正整数 $ m $ 的个数模 $ 998\,244\,353 $。
**输入输出样例：**
**输入样例 #1**
```
2
1 3 2 3
```
**输出样例 #1**
```
2
```
**输入样例 #2**
```
2
2 2 3 5
```
**输出样例 #2**
```
5
```
**输入样例 #3**
```
1
1 4
```
**输出样例 #3**
```
0
```
**说明：**
在第一个样例中，满足 $ f(m) = \{1,3,2,3\} $ 的两个 $ m $ 的值是 $ m = 24 $ 和 $ m = 54 $。它们的质数分解分别是 $ 24 = 2^3 \cdot 3^1 $ 和 $ 54 = 2^1 \cdot 3^3 $。
在第二个样例中，满足 $ f(m) = \{2,2,3,5\} $ 的五个 $ m $ 的值是 $ 200, 225, 288, 500 $ 和 $ 972 $。
在第三个样例中，没有 $ m $ 的值满足 $ f(m) = \{1,4\} $。因为 $ 1^4 $ 和 $ 4^1 $ 都不是质数分解，因为 $ 1 $ 和 $ 4 $ 不是质数。**题目大意：** 任何正整数 $ m $ 都可以被唯一地分解为 $ p_1^{e_1} \cdot p_2^{e_2} \ldots p_k^{e_k} $ 的形式，其中 $ p_1, p_2, \ldots, p_k $ 是质数，且 $ p_1 < p_2 < \ldots < p_k $，$ e_1, e_2, \ldots, e_k $ 是正整数。将正整数 $ m $ 的唯一质数分解转化为一个长度为 $ 2k $ 的 **可重集合** 记为 $ f(m) $。 给定正整数 $ n $ 和一个长度为 $ 2n $ 的可重集 $ A $。求出满足 $ f(m) = A $ 的正整数 $ m $ 的个数。答案对 $ 998\ 244\ 353 $ 取模。 **输入格式：** 第一行包含一个整数 $ n $（$ 1 \le n \le 2022 $）。 第二行包含 $ 2n $ 个整数 $ a_1, a_2, \ldots, a_{2n} $（$ 1 \le a_i \le 10^6 $）——给定的列表。 **输出格式：** 打印一个整数，满足 $ f(m) = \{a_1, a_2, \ldots, a_{2n}\} $ 的正整数 $ m $ 的个数模 $ 998\,244\,353 $。 **输入输出样例：** **输入样例 #1** ``` 2 1 3 2 3 ``` **输出样例 #1** ``` 2 ``` **输入样例 #2** ``` 2 2 2 3 5 ``` **输出样例 #2** ``` 5 ``` **输入样例 #3** ``` 1 1 4 ``` **输出样例 #3** ``` 0 ``` **说明：** 在第一个样例中，满足 $ f(m) = \{1,3,2,3\} $ 的两个 $ m $ 的值是 $ m = 24 $ 和 $ m = 54 $。它们的质数分解分别是 $ 24 = 2^3 \cdot 3^1 $ 和 $ 54 = 2^1 \cdot 3^3 $。 在第二个样例中，满足 $ f(m) = \{2,2,3,5\} $ 的五个 $ m $ 的值是 $ 200, 225, 288, 500 $ 和 $ 972 $。 在第三个样例中，没有 $ m $ 的值满足 $ f(m) = \{1,4\} $。因为 $ 1^4 $ 和 $ 4^1 $ 都不是质数分解，因为 $ 1 $ 和 $ 4 $ 不是质数。
任何正整数 $ m $ 都可以被唯一地分解为 $ p_1^{e_1} \cdot p_2^{e_2} \ldots p_k^{e_k} $ 的形式，其中 $ p_1, p_2, \ldots, p_k $ 是质数，且 $ p_1 < p_2 < \ldots < p_k $，$ e_1, e_2, \ldots, e_k $ 是正整数。将正整数 $ m $ 的唯一质数分解转化为一个长度为 $ 2k $ 的 **可重集合** 记为 $ f(m) $。
给定正整数 $ n $ 和一个长度为 $ 2n $ 的可重集 $ A $。求出满足 $ f(m) = A $ 的正整数 $ m $ 的个数。答案对 $ 998\ 244\ 353 $ 取模。
**输入格式：**
第一行包含一个整数 $ n $（$ 1 \le n \le 2022 $）。
第二行包含 $ 2n $ 个整数 $ a_1, a_2, \ldots, a_{2n} $（$ 1 \le a_i \le 10^6 $）——给定的列表。
**输出格式：**
打印一个整数，满足 $ f(m) = \{a_1, a_2, \ldots, a_{2n}\} $ 的正整数 $ m $ 的个数模 $ 998\,244\,353 $。
**输入输出样例：**
**输入样例 #1**
```
2
1 3 2 3
```
**输出样例 #1**
```
2
```
**输入样例 #2**
```
2
2 2 3 5
```
**输出样例 #2**
```
5
```
**输入样例 #3**
```
1
1 4
```
**输出样例 #3**
```
0
```
**说明：**
在第一个样例中，满足 $ f(m) = \{1,3,2,3\} $ 的两个 $ m $ 的值是 $ m = 24 $ 和 $ m = 54 $。它们的质数分解分别是 $ 24 = 2^3 \cdot 3^1 $ 和 $ 54 = 2^1 \cdot 3^3 $。
在第二个样例中，满足 $ f(m) = \{2,2,3,5\} $ 的五个 $ m $ 的值是 $ 200, 225, 288, 500 $ 和 $ 972 $。
在第三个样例中，没有 $ m $ 的值满足 $ f(m) = \{1,4\} $。因为 $ 1^4 $ 和 $ 4^1 $ 都不是质数分解，因为 $ 1 $ 和 $ 4 $ 不是质数。**题目大意：** 任何正整数 $ m $ 都可以被唯一地分解为 $ p_1^{e_1} \cdot p_2^{e_2} \ldots p_k^{e_k} $ 的形式，其中 $ p_1, p_2, \ldots, p_k $ 是质数，且 $ p_1 < p_2 < \ldots < p_k $，$ e_1, e_2, \ldots, e_k $ 是正整数。将正整数 $ m $ 的唯一质数分解转化为一个长度为 $ 2k $ 的 **可重集合** 记为 $ f(m) $。 给定正整数 $ n $ 和一个长度为 $ 2n $ 的可重集 $ A $。求出满足 $ f(m) = A $ 的正整数 $ m $ 的个数。答案对 $ 998\ 244\ 353 $ 取模。 **输入格式：** 第一行包含一个整数 $ n $（$ 1 \le n \le 2022 $）。 第二行包含 $ 2n $ 个整数 $ a_1, a_2, \ldots, a_{2n} $（$ 1 \le a_i \le 10^6 $）——给定的列表。 **输出格式：** 打印一个整数，满足 $ f(m) = \{a_1, a_2, \ldots, a_{2n}\} $ 的正整数 $ m $ 的个数模 $ 998\,244\,353 $。 **输入输出样例：** **输入样例 #1** ``` 2 1 3 2 3 ``` **输出样例 #1** ``` 2 ``` **输入样例 #2** ``` 2 2 2 3 5 ``` **输出样例 #2** ``` 5 ``` **输入样例 #3** ``` 1 1 4 ``` **输出样例 #3** ``` 0 ``` **说明：** 在第一个样例中，满足 $ f(m) = \{1,3,2,3\} $ 的两个 $ m $ 的值是 $ m = 24 $ 和 $ m = 54 $。它们的质数分解分别是 $ 24 = 2^3 \cdot 3^1 $ 和 $ 54 = 2^1 \cdot 3^3 $。 在第二个样例中，满足 $ f(m) = \{2,2,3,5\} $ 的五个 $ m $ 的值是 $ 200, 225, 288, 500 $ 和 $ 972 $。 在第三个样例中，没有 $ m $ 的值满足 $ f(m) = \{1,4\} $。因为 $ 1^4 $ 和 $ 4^1 $ 都不是质数分解，因为 $ 1 $ 和 $ 4 $ 不是质数。