[省选联考 2022] 卡牌 解题报告

作为一道著名题，当然是有必要改一改的。

本文会介绍卡牌的两种做法：容斥和 FWT。下文将默认读者已经清晰地阅读了题目，没有漏过任何性质和条件。

容斥

这个做法应该是比较好想的。

一种可行的想法是拿所有方案，减去所有没有包含任意一个的方案，加上包含任意两个的方案，\(\ldots\)

朴素的考虑质数整除一个数的情况时间复杂度过高，不过，我们发现 \(2000\) 以内的数至多只会有一个超过 \(43\) 的质数为它的约数。这启示我们可以用类似根号分治的做法思考本题。

先考虑质数大于 \(43\) 的情况，我们可以记 \(c_i\) 表示有多少数被 \(i\) 整除。在询问集合中，如果询问集合包含某个质数，即这些数中至少选择一个，否则选不选都可以。

不超过 \(43\) 质数只有 \(14\) 个，我们可以暴力容斥，设 \(S\) 表示 被前 \(14\) 个数整除的状态（被整除为 \(0\)，否则为 \(1\)），\(f_{S,i}\) 表示在 \(S\) 的状态下，质数 \(i\) 整除的数的个数。

const int N = 1e6 + 5, M = 1005, V = 2005, P = 998244353;
int n, m, a[V], c[20000];
int Div[V];

vector<int> fac[V];

int pri[V], rnk[V], tot, v[V];
int f[1 << 14 | 9][305], ing[1 << 14 | 9];

il void init(int n = 2000) {
    for (int i = 2; i <= n; ++i) {
        if (!v[i]) { pri[++tot] = i; rnk[i] = tot; }
        for (int j = 2; i * j <= n; ++j) v[i * j] = 1;
    }
    
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= tot; ++j) {
            if (i % pri[j]) continue;
            if (j <= 14) Div[i] |= 1 << (j - 1);
            fac[i].eb(j);
        }
    }
}

il void add(int& x, int y) { x = x + y >= P ? x + y - P : x + y; }
il void sub(int& x, int y) { x = x - y < 0 ? x - y + P : x - y; }

il int qpow(int x, int y) {
    int sum = 1;
    for (; y; y >>= 1, x = 1ll * x * x % P) if (y & 1) sum = 1ll * sum * x % P;
    return sum;
}

vector<int> p;

int main() {
    init();
    cerr << tot << endl;
    read(n);
    for (int i = 1; i <= n; ++i) ++a[read()];
    
    for (int S = 0; S < (1 << 14); ++S) {
        for (int i = 2; i <= 2000; ++i) {
            if (Div[i] & S) continue;
            f[S][fac[i].back()] += a[i]; ing[S] += a[i];
        }
        ing[S] += a[1];
    }
    
    read(m);
    while (m--) {
        int c = read(); vector<int>().swap(p); p.resize(c);
        int bel = 0;
        for (int i = 0; i < c; ++i) {
            read(p[i]);
            if (rnk[p[i]] <= 14) bel |= 1 << (rnk[p[i]] - 1);
        }
        int Ans = 0;
        for (int S = 0; S < (1 << 14); ++S) {
            if ((S | bel) != bel) continue;
            int res = ing[S], ret = 1;
            for (int i = 0; i < c; ++i) {
                if (p[i] <= 43) continue;
                ret = 1ll * ret * (qpow(2, f[S][rnk[p[i]]]) - 1) % P;
                res -= f[S][rnk[p[i]]];
            }
            ret = 1ll * ret * qpow(2, res) % P;
            int ppt = __builtin_popcount(S);
            if (ppt & 1) sub(Ans, ret);
            else add(Ans, ret);
        }
        add(Ans, P);
        write(Ans);
    }
    return 0;
}

以下是笔者在思考是遇到的一些问题：

• 为什么 \(S\) 要是输入的质数集合的子集？

  笔者的理解是此时 \(S\) 能代表 所有的 不被 \(S\) 整除的数的个数，为了防止算重直接寻找最大的集合。

• 容斥的初值为什么是 \(0\)？

  当 \(S=0\) 时，答案对应的是全集。

FWT

这个坑可能等笔者学完 FWT 之后再来补。