[省选联考 2022] 卡牌
这题放在场上应该也是比较有区分度的。基本功扎实应该能很快做出来,不过我卡了一会。
首先直接做肯定行不通,考虑容斥,然后发现容着容着就不会了。
最尖锐的矛盾在于,你肯定要记一下哪些数是还没选的,但是值域是很大的,然后就寄。
所以考虑数论里面的一个经典 trick:根号分治。注意到 \(\sqrt V = 43\),所以一个数中 \(>43\) 的质数都只会出现一次。考虑抽象一下问题,现在有很多堆数,每次询问相当于钦定某些堆至少选一个,然后选出来的数要满足前 \(13\) 个质数的限制。
这样就可以直接容斥了,直接枚举 \(S\) 表示没选的质数的集合,预处理出 \(g_{i, S}\) 表示 \(i\) 的倍数中不包含 \(S\) 的数的个数。这个东西可以直接通过高维前缀和处理出来。然后随便算一下就可以了。
const int P = 998244353;
void add(int &x, int y) {
(x += y) >= P ? x -= P : 0;
}
void sub(int &x, int y) {
(x -= y) < 0 ? x += P : 0;
}
int pw[1000010];
const int N = 2010;
const int V = 2000;
int n, cnt[N], m, c;
int p[N], vis[N], tot, r[N];
void Sieve(int n) {
for(int i = 2; i <= n; ++i) {
if(!vis[i]) p[++tot] = i, r[i] = tot;
for(int j = 1; j <= tot; ++j) {
if(i * p[j] > n) break;
vis[i * p[j]] = 1;
if(i % p[j] == 0) break;
}
}
}
int q[N];
int g[N][1 << 13];
int main() {
freopen("card.in","r",stdin);
freopen("card.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
Sieve(V);
cin >> n;
pw[0] = 1;
for(int i = 1; i <= n; ++i)
add(pw[i] = pw[i - 1], pw[i - 1]);
for(int i = 1, x; i <= n; ++i) {
cin >> x;
++cnt[x];
}
for(int i = 1; i <= 13; ++i)
for(int j = p[i]; j <= V; j += p[i])
q[j] |= (1 << (i - 1));
for(int i = 14; i <= tot; ++i) {
int tp = p[i], u = (1 << 13) - 1;
for(int j = tp; j <= V; j += tp)
g[i][u ^ q[j]] += cnt[j];
for(int j = 0; j < 13; ++j)
for(int p = 0; p < (1 << 13); ++p)
if(p >> j & 1) g[i][p ^ (1 << j)] += g[i][p];
}
int u = (1 << 13) - 1;
for(int j = 1; j <= V; ++j)
g[0][u ^ q[j]] += cnt[j];
for(int j = 0; j < 13; ++j)
for(int p = 0; p < (1 << 13); ++p)
if(p >> j & 1) g[0][p ^ (1 << j)] += g[0][p];
cin >> m;
while(m--) {
cin >> c;
vector<int> b;
int mask = 0;
for(int i = 1, x; i <= c; ++i) {
cin >> x;
if(r[x] <= 13) mask |= 1 << (r[x] - 1);
else b.eb(r[x]);
}
sort(b.begin(), b.end());
b.erase(unique(b.begin(), b.end()), b.end());
c = sz(b);
int ans = 0;
for(int s = 0; s < (1 << 13); ++s) {
if((mask & s) != s) continue;
int mul = 1, ns = 0;
for(int x : b) {
mul = 1ll * mul * (pw[g[x][s]] - 1) % P;
ns += g[x][s];
}
mul = 1ll * mul * pw[g[0][s] - ns] % P;
if(__builtin_popcount(s) & 1) sub(ans, mul);
else add(ans, mul);
}
cout << ans << '\n';
}
}