[联合省选 2022 D2T1] 卡牌

首先直接按题意模拟一下，发现“所有质数都要被选上”这个条件很烦，因为选上一个卡牌后有很多质数会受到影响，非常不好做。换言之，题中的限制很强。

考虑正难则反，钦定一些质数使得它们 恰好 没有被选上，其它质数都被选上。然后会发现 恰好 这个条件还是很强，不好搞，直接上容斥，把 恰好 弱化成 一部分 被选上，另一部分不用管。这样限制条件就松了很多。

回到题目，\(n\le 10^6\) 这个条件是唬人的，真正互不相同的数字只有 \(2000\) 个，拿桶记一下数 \(n\) 就可以扔了。

对于 \(s_i\le 30\) 的部分分，显然可以状压预处理然后容斥计算。这为我们提供了一些思路。

[NOI2015] 寿司晚宴 这道题给出了一个相当经典的处理手段：一个数至多有一个 \(\gt \sqrt n\) 的质因子，对于 \(\le \sqrt n\) 的质因子状压，对于 \(\gt \sqrt n\) 的质因子单独考虑。为了方便，称这类质因子为“大质因子”。

本题 \(V=2\times 10^3\)，发现 \(\le \sqrt V\) 的质数只有 \(2\sim 43\) 这 14 个，进一步地，\(43\times 47\gt 2000\)，所以 43 也不用参与状压，进一步压缩了状态。

然后统计，令 \(f(i,j)\) 表示前 13 个质数没有被选的状态为 \(i\)，当前大质因子为 \(j\) 时的方案数。预处理是简单的。

然后我们考虑容斥，容易发现容斥系数为 \((-1)^{|S|}\)。

计算答案并不难。对于一个状态 \(i\)，枚举 \(j\in [43,2000],j\in \mathbb P\)，如果 \(j\) 在询问集合中，那么有 \(2^{f(i,j)}-1\) 的贡献（筛去空集），反之有 \(2^{f(i,j)}\) 的贡献。

把询问集合存成 std::vector，每次就不用枚举 \(j\)，直接扫一遍 std::vector 然后统计答案，和容斥系数乘起来加到答案里即可。实现可以参考代码。

时间复杂度 \(\mathcal O(\sum c_i\times 2^{13})\)。

// 此时此刻的光辉，盼君勿忘。

#include <bits/stdc++.h>
#define pb emplace_back

const int N = 2e3;
const int M = 1 << 13;
const int mod = 998244353;
const int SIZE = 1e6 + 5;
int prime[N], cnt, buc[N + 5];
bool flag[N + 5];
std::vector<int> G[N + 5];

int pri[13] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 31}, pos[N + 5];

int m, n, sum[N + 5], res[M + 5], f[M + 5][305], pw[SIZE], popcnt[M + 5];

void add(int &x, int y) {
    x += y;

    if (x >= mod)
        x -= mod;

    return ;
}

void sub(int &x, int y) {
    x -= y;

    if (x < 0)
        x += mod;

    return ;
}

int power(int x, int y) {
    int ans = 1;

    for (; y; y >>= 1) {
        if (y & 1)
            ans = 1ll * ans * x % mod;

        x = 1ll * x * x % mod;
    }

    return ans;
}

int main() {
    freopen("card.in", "r", stdin);
    freopen("card.out", "w", stdout);
    scanf("%d", &n);

    for (int i = 1, x; i <= n; ++ i)
        scanf("%d", &x), ++ sum[x];

    for (int i = 1; i < M; ++ i)
        popcnt[i] = popcnt[i >> 1] + (i & 1);

    for (int i = 2; i <= N; ++ i) {
        if (!flag[i])
            prime[++ cnt] = i, pos[i] = cnt;

        for (int j = 1; j <= cnt && i * prime[j] <= N; ++ j) {
            flag[i * prime[j]] = true;

            if (!(i % prime[j]))
                break ;
        }
    }

    pw[0] = 1;

    for (int i = 1; i < SIZE; ++ i)
        pw[i] = 2ll * pw[i - 1] % mod;

    for (int i = 1; i <= cnt; ++ i)
        for (int k = 2; k <= N; ++ k) {
            if (k % prime[i])
                continue ;

            G[k].pb(i);

            if (i <= 13)
                buc[k] |= 1 << (i - 1);
        }

    for (int i = 0; i < M; ++ i) {
        for (int j = 2; j <= N; ++ j) {
            if (buc[j] & i)
                continue ;

            res[i] += sum[j];
            f[i][G[j].back()] += sum[j];
        }

        res[i] += sum[1];
    }

    scanf("%d", &m);
    std::vector<int> T;

    while (m --) {
        int c, x, form = 0, ans = 0, cur, cnt;
        scanf("%d", &c);
        T.clear();

        for (int i = 1; i <= c; ++ i) {
            scanf("%d", &x);
            T.pb(x);

            if (pos[x] <= 13)
                form |= 1 << (pos[x] - 1);
        }

        std::sort(T.begin(), T.end());

        for (int j = 0; j < M; ++ j) {
            if ((j | form) != form)
                continue ;

            cur = res[j];
            cnt = 1;

            for (int k = 0; k < c; ++ k) {
                if (T[k] < 43)
                    continue ;

                cnt = 1ll * cnt * (pw[f[j][pos[T[k]]]] + mod - 1) % mod;
                cur -= f[j][pos[T[k]]];
            }

            cnt = 1ll * cnt * pw[cur] % mod;

            if (popcnt[j] & 1)
                sub(ans, cnt);
            else
                add(ans, cnt);
        }

        printf("%d\n", ans);
    }

    return 0;
}