3663. [统一省选 2022]卡牌游戏

【题目描述】

小 A 有 $n$ 张卡牌，编号为 $1, 2, \ldots, n$。每张卡牌上写着一个正整数，第 $i$ 张卡牌上的正整数为 $s_i$。

现在有 $m$ 轮游戏，第 $i$ 轮游戏会给出 $c_i$ 个质数，小 A 需要选择任意多张卡牌，使得这些卡牌上面的正整数的乘积能被该轮游戏给出的每个质数整除。

这当然难不倒小 A，于是他开始思考一个更难的问题，对于每一轮游戏，他有多少种卡牌的选法。

这给小 A 整不会了，于是他只能来求助你，你只需要告诉他答案模 $998244353$ 的值即可。两种选法 A 和 B 互不相同当且仅当存在一张卡牌在 A 中被选择但在 B 中未被选择或者存在一张卡牌在 B 中被选择但在 A 中未被选择。注意：牌面上的数字相同但编号不相同的两张卡牌被视为不同的卡牌。

【输入格式】

第一行一个正整数 $n$，表示卡牌数量。

第二行 $n$ 个正整数 $s_i$，表示每张卡牌上写的数字。

第三行一个正整数 $m$，表示游戏轮数。

接下来 $m$ 行，每行第一个正整数 $c_i$，表示该轮游戏给出的质数个数，接下来 $c_i$ 个质数 $p_{i, j}$，表示该轮游戏给出的所有质数。数据保证 $\sum_i c_i \le 18000$，即所有 $c_i$ 之和不超过 $18000$。

【输出格式】

输出 $m$ 行，每行一个整数，第 $i$ 行表示第 $i$ 轮游戏的方案数模 $998244353$ 的值。

【样例输入1】

5
10 2 10 5 46
4
2 2 5
2 2 23
1 3
1 23

【样例输出1】

27
16
0
16

样例数据下载

【样例1说明】

第一轮游戏：除了以下 $5$ 种方案外其它方案都可行：什么都不选、选 $2$、选 $5$、选 $46$、选 $2$ 和 $46$。所以答案为 $2^5 - 5 = 27$。

第二轮游戏：只要选了 $46$，其它卡牌选不选均可，所以答案为 $2^4 = 16$。

【数据规模与约定】

对于 $100 \%$ 的数据，$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$。

【来源】

统一省选2022 Day2 Task1