#PQJ927x4052. QOJ 927_4052

    ID: 3063 传统题 1000ms 512MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:NOI 2022 统一省选数学动态规划

QOJ 927_4052

NOI2022 省选 DAY2 卡牌(card) 卡牌(card) 【题目描述】 小A 有n 张卡牌,编号为1, 2, ..., n。每张卡牌上写着一个正整数,第i 张卡牌上 的正整数为si。 现在有m 轮游戏,第i 轮游戏会给出ci 个质数,小A 需要选择任意多张卡牌,使 得这些卡牌上面的正整数的乘积能被该轮游戏给出的每个质数整除。 这当然难不倒小A,于是他开始思考一个更难的问题,对于每一轮游戏,他有多少 种卡牌的选法。 这给小A 整不会了,于是他只能来求助你,你只需要告诉他答案模998244353 的 值即可。两种选法A 和B 互不相同当且仅当存在一张卡牌在A 中被选择但在B 中未 被选择或者存在一张卡牌在B 中被选择但在A 中未被选择。注意:牌面上的数字相同 但编号不相同的两张卡牌被视为不同的卡牌。 【输入格式】 从文件card.in 中读入数据。 第一行一个正整数n,表示卡牌数量。 第二行n 个正整数si,表示每张卡牌上写的数字。 第三行一个正整数m,表示游戏轮数。 接下来m 行,每行第一个正整数ci,表示该轮游戏给出的质数个数,接下来ci 个 质数pi,j,表示该轮游戏给出的所有质数。数据保证∑ i ci ≤18000,即所有ci 之和不超 过18000。 【输出格式】 输出到文件card.out 中。 输出m 行,每行一个整数,第i 行表示第i 轮游戏的方案数模998244353 的值。 【样例1 输入】 1 5 2 10 2 10 5 46 3 4 4 2 2 5 5 2 2 23 6 1 3 7 1 23 第2 页 共8 页

NOI2022 省选 DAY2 卡牌(card) 【样例1 输出】 1 27 2 16 3 0 4 16 【样例1 解释】 第一轮游戏:除了以下5 种方案外其它方案都可行:什么都不选、选2、选5、选 46、选2 和46。所以答案为25 −5 = 27 第二轮游戏:只要选了46,其它卡牌选不选均可,所以答案为24 = 16。 【样例2】 见选手目录下的card/card2.in 与card/card2.ans。 【数据范围】 对于100% 的数据,n ≤106, si ≤2000, m ≤1500, ∑ i ci ≤18000, 2 ≤pi,j ≤2000 测试点 n ≤ m ≤ ∑ i ci ≤ 其他限制 1,2 10 10 20 si ≤30 3 ∼5 20 50 无 6 ∼8 106 1500 10000 si ≤30 9 ∼11 10000 1000 5000 si ≤500 12,13 1000 100 1000 无 14 ∼17 5000 600 7000 18 ∼20 106 1500 18000 第3 页 共8 页