P8292 [省选联考 2022] 卡牌

· · 题解

*VII. P8292 [省选联考 2022] 卡牌

套路见少了，省选考场上被打爆咧。

首先我们尝试抽象题意：给出 n 个集合 S_i（表示每个数的质因子集合），m 次询问每次给出 T，求从 n 个集合中选出若干个集合的方案数，使得这些集合的并覆盖 T。

虽然不知道计数能否归约到最优化上，但对于上述问题的变种 “求最少选出多少个集合覆盖 T” 是广为人知的 NP-hard：最小集合覆盖问题。就连决定性问题 “求是否能选出不超过 k 个集合覆盖 T” 也是 NPC 问题。

自然，思考本题的 \rm polylog 做法简直是在做无用功。考虑指数级做法，再观察到 s_i\leq 2000 的数据范围，并联想到 NOI2015 寿司晚宴，不难想到根号分治。

根号分治的核心要素在于，不存在一个数，使得它含有两个以上大于 \sqrt {2000} 的不同的质因子。更具体地，由于 43 \times 47 > 2000，所以这个界的精确值是 43。这也意味着，对于 x, y\in T 且 x\neq y，若 x, y 均不小于 43，那么覆盖 x, y 的决策是 相对独立的。即不存在一个集合能同时覆盖 x 和 y。这使得我们可以对不小于 43 的质数 单独考虑。

对于小于 43 的那些质数呢？总共有 13 个这样的质数，设为 P。不难想到将它们是否被覆盖的状态压缩成一个二进制数，也就是状态压缩。有了这个初步思路，我们尝试解决原问题。

首先，将只含有 P 当中的质数作为质因子的数先拎出来，记做 X。我们可以预处理 X 当中所有数的贡献，即求出 f_i 表示在 X 中有多少种选数的方式使得 P 被覆盖的状态为 i。这个正确性基于 X 所有数不含 P 以外的质因子，我们自然不需要记录 P 以外的质因数被覆盖的情况。

求 f_i 是非常容易的。可以直接 DP 算，但有一个更好的方法。对 x\in X，设 S_x 表示它覆盖了哪些 P 中的质数。注意到 DP 之间的转移形如 f_i\to f'_i 以及 f_i \times (2 ^ {c_x} - 1) \to f'_{i | S_x}，其中 c_x 是 x 在 n 个数中出现次数。这相当于 f_i 和一个在第 0 位有值 1，在第 S_x 位有值 2 ^ {c_x} - 1 的集合幂级数 F_x 做或卷积。注意到 F_x 在进行 FWT（下文均指 FWT-OR）之后，每一位上的值均为 2 的幂（对于不包含 S_x 的位是 1，对于包含的则是 2 ^ {c_x}），所以我们可以存 2 的幂次而非其真实值，这样 f 就是点值，即真实值高维前缀和之后的结果。

对于剩下来的 290 个质数而言，到每次询问再考虑的话，时间复杂度 \mathcal{O}(m \times \pi(s_i) \times 2 ^ {|P|})，时间复杂度显然无法接受。注意到对于没有出现在 T 和 P 中的质数 p 而言，一个 p 的倍数除掉 p 之后不会产生任何影响，同时题目保证了 \sum c_i 的数量级，即 \sum c_i \times 2 ^ {|P|} 是可以接受的，所以我们不妨先设 T\subseteq P，每次询问时再依次考虑那些 \in T 但 \notin P 的质数。这样一来，对于 y\notin X，我们也求出其覆盖了哪些 P 中的质数 S_y，并且类似 S_x 那样对 f 进行转移。

注意，这里实际上我们扩展了 f 的定义，即将原来定义为只考虑 X 以内的数变成了考虑所有数，但核心没有变，均为 P 被覆盖的情况对应的方案数。

考虑一个 \in T 但 \notin P 的质数 p 带来的影响。由于 p 必须要被覆盖，所以我们只需减去 p 没有被覆盖的情况。如何处理这一步呢？设 G_p = \prod\limits_{p\mid k} F_k，其中 F 的定义见上文，且乘积的形式为或卷积。质数 p 对 f 的贡献是 G_p，这是因为每个 p 的倍数 k 对 f 的贡献是 F_k，而这些贡献以或卷积的形式累计。注意到我们只需减去 所有 p 的倍数均不选 的情况。对于该种情况，由于一个数都没有选，所以自然也不会覆盖任何一个 P 当中的质数，这意味着覆盖情况为 0，说明我们只需将 f 除掉 G_p，再乘以 G_p - x ^ 0 即可。由于 G_p 的每个位置的系数均存储的是 2 的幂次，所以不需要担心不存在逆元。

更具体地，我们枚举所有 p\in T 且 p\notin P，除掉所有 G_p，再乘上所有 G_p - x ^ 0。那么答案即所有覆盖了 T' = T\cap P 的位置的和，即 \sum\limits_{T'\subseteq i} f_i。由于每次询问最后要将点值逆回来，所以时间复杂度为 \mathcal{O}((s_i +\sum c_i + m|P|) 2 ^ {|P|})。

总结一下，我们首先求出 f = \prod F_x 表示只考虑 P 以内的质数时，这些质数被覆盖情况对应的方案数，再对每次询问，对每个 p\in T 且 p\notin P，除掉 \prod F_k 其中 k 是 p 的倍数，再乘上 (\prod F_k) - x ^ 0，这一步是为了去掉没有覆盖 p 的情况。所有乘积均为或卷积，在点值意义下运算，最后再逆回来即可。对于这些 p 能单独搞的原因是它们之间相互独立。43 \times 47 > 2 \times 10 ^ 3。

注意对给出的 T 去重。如果不懂题解可以看代码，注释很详细。

#include <bits/stdc++.h>
using namespace std;
const int N = 2e3 + 2;
const int V = 1 << 13;
const int mod = 998244353;
const int P[13] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41};
void add(int &x, int y) {x += y, x >= mod && (x -= mod);}
void sub(int &x, int y) {x -= y, x < 0 && (x += mod);}
int n, m, pw[N * N], buc[N], f[V], g[N][V];
void init() {
    for(int i = pw[0] = 1; i <= n; i++) pw[i] = (pw[i - 1] << 1) % mod;
    for(int i = 1; i < N; i++) {
        int tmp = i, msk = 0;
        if(!buc[i]) continue; // 1 = 2 ^ 0，所以加 0 就直接忽略了
        for(int j = 0; j < 13; j++) while(tmp % P[j] == 0) tmp /= P[j], msk |= 1 << j; // 求出每个 i 覆盖 P 中质数的情况
        for(int j = 0; j < V; j++) if((j & msk) == msk) f[j] += buc[i]; // 对于包含 msk 的位置，系数要乘以 2 ^ {c_i} 次方，因此 2 的幂次加上 buc[i]
        if(tmp == 43 * 43) tmp = 43; // 注意这里有个小特判，43 ^ 2 <= 2e3
        if(tmp > 1) for(int j = 0; j < V; j++) if((j & msk) == msk) g[tmp][j] += buc[i]; // 这里是求每个 G_p
    }
}
int main() {
    freopen("card.in", "r", stdin);
    freopen("card.out", "w", stdout);
    cin >> n;
    for(int i = 1, s; i <= n; i++) scanf("%d", &s), buc[s]++;
    cin >> m, init();
    while(m--) {
        int c, p[V << 1], h[V], msk = 0, ans = 0;
        cin >> c, memcpy(h, f, sizeof(h));
        for(int i = 1; i <= c; i++) cin >> p[i];
        sort(p + 1, p + c + 1), c = unique(p + 1, p + c + 1) - p - 1; // 对所有质数去重
        for(int i = 1; i <= c; i++) for(int j = 0; j < 13; j++) if(p[i] == P[j]) msk |= 1 << j; // 求出 T \cap P
        for(int i = 1; i <= c; i++) if(p[i] > 41) for(int j = 0; j < V; j++) h[j] -= g[p[i]][j]; // 对于 >= 43 且出现在 T 中的质数，先减去它们的贡献
        for(int j = 0; j < V; j++) h[j] = pw[h[j]]; // 注意乘以 G_p - x ^ 0 时系数不再是 2 的幂，所以提前将系数从幂次转化为真实值
        for(int i = 1; i <= c; i++) if(p[i] > 41) for(int j = 0; j < V; j++) h[j] = 1ll * h[j] * (pw[g[p[i]][j]] - 1) % mod; // 乘以 G_p - x ^ 0，注意 -x ^ 0 在点值意义下即每个位置上均为 -1，所以只需乘以每个位置原来的系数 -1 即可
        for(int k = 1; k < V; k <<= 1) for(int i = 0; i < V; i += k << 1) for(int j = 0; j < k; j++) sub(h[i | j | k], h[i | j]); // 将点值转化为真实值，高维差分 IFWT
        for(int j = 0; j < V; j++) if((msk & j) == msk) add(ans, h[j]); // 对能完全覆盖 T \cap P 的方案数求和
        cout << ans << endl;
    }
    return 0;
}
/*
2022/4/18
start coding : 10:52
finish debugging : 11:47
--- stupid mistakes ---
None. Good.
*/