[省选联考 2022] 卡牌

询问有多少种选取的方案，使得取出的集合的并包含给定集合。

一眼 NP，于是考虑暴力容斥。

将选出集合的并包含给定集合 $\{a_1,a_2,\cdots,a_n\}$ 看作选出的集合并包含 $a_1$ 且包含 $a_2$ 且包含 $a_3$……。经过一步容斥后转化为选出的集合并不包含 $b_1$ 且不包含 $b_2$ 且不包含 $b_3$……（其中 $\{b_1,b_2,\cdots,b_n\}\subseteq\{a_1,a_2,\cdots,a_n\}$），也就是对于询问集合的每个子集，求可选集合中与它不交的有多少个。

暴力显然不可取，考虑到质因数分解带自然根号：每个质因数至多有一个不小于 $\sqrt n$ 的质因子。所以我们只用状压前 13 个质数，单独讨论最大的质数即可。