P8292 [NOI Qualifier Joint Contest 2022] Cards

Little A has $n$ cards, numbered $1, 2, \ldots, n$. Each card has a positive integer written on it, and the positive integer on the $i$-th card is $s_i$. Now there are $m$ rounds of games. In the $i$-th round, $c_i$ primes are given. Little A needs to choose any number of cards such that the product of the positive integers on these chosen cards is divisible by every prime given in that round. This is not hard for Little A, so he starts thinking about a harder problem: for each round, how many different ways are there to choose cards. Little A cannot figure it out, so he asks you for help. You only need to output the answer modulo $998244353$. Two selections $A$ and $B$ are different if and only if there exists a card that is chosen in $A$ but not in $B$, or there exists a card that is chosen in $B$ but not in $A$. Note: two cards with the same number written on them but different indices are considered different cards.

The first line contains a positive integer $n$, indicating the number of cards. The second line contains $n$ positive integers $s_i$, indicating the number written on each card. The third line contains a positive integer $m$, indicating the number of rounds. The next $m$ lines describe the rounds. In each line, the first positive integer is $c_i$, indicating the number of primes given in that round, followed by $c_i$ primes $p_{i, j}$, indicating all primes given in that round. The testdata guarantees that $\sum_i c_i \le 18000$, i.e., the sum of all $c_i$ does not exceed $18000$.

Output $m$ lines. Each line contains one integer. The $i$-th line is the number of valid selections for the $i$-th round modulo $998244353$.

**[Sample Explanation #1]** Round 1: Except for the following $5$ selections, all other selections are valid: selecting nothing, selecting $2$, selecting $5$, selecting $46$, selecting $2$ and $46$. Therefore, the answer is $2^5 - 5 = 27$. Round 2: As long as $46$ is selected, it does not matter whether other cards are selected, so the answer is $2^4 = 16$. **[Constraints]** For $100 \%$ of the testdata, $1 \le n \le {10}^6$, $1 \le s_i \le 2000$, $1 \le m \le 1500$, $1 \le c_i, \sum_i c_i \le 18000$, $2 \le p_{i, j} \le 2000$. | Test Point | $n \le$ | $m \le$ | $\sum_i c_i \le$ | Other Constraints | |:-:|:-:|:-:|:-:|:-:| | $1 \sim 2$ | $10$ | $10$ | $20$ | $s_i \le 30$ | | $3 \sim 5$ | $10$ | $20$ | $50$ | None | | $6 \sim 8$ | ${10}^6$ | $1500$ | $10000$ | $s_i \le 30$ | | $9 \sim 11$ | $10000$ | $1000$ | $5000$ | $s_i \le 500$ | | $12 \sim 13$ | $1000$ | $100$ | $1000$ | None | | $14 \sim 17$ | $5000$ | $600$ | $7000$ | None | | $18 \sim 20$ | ${10}^6$ | $1500$ | $18000$ | None | Translated by ChatGPT 5