Topic

Answer key

This range can tell us a lot of information , For example, the number of prime numbers , namely , The square has the most prime numbers in the range 14 individual .

This reminds us of , After each number prime factor is decomposed Does not belong to the former 14 The prime factor of a prime number At most one .

and , We can compress this range again , because $43\times 47>2000$ , So each number Does not belong to the former 13 The prime factor of a prime number most A kind of , That is, there is either only one , Or $43^2$ , There is only one .

So we can put the front 13 Whether a prime number exists or not , Then make a similar knapsack DP The algorithm of . How to satisfy 13 The prime number after two ？ We can group according to the largest prime factor , When there is a 13 A prime number after $P$ The condition of existence , Just put the... Of each state Total number of schemes （ Consider 13 The number of schemes of all prime numbers after ） remove 【$P$ Number of group options 】, And ride on 【$P$ Number of schemes selected by at least one group 】. because 【$P$ Number of group options 】 yes 2 The power of , So there must be an inverse element .

This special Backpack DP The transfer of , It can be used FWT Convolution optimization . In particular , We can count the number of schemes first DP The array is preprocessed by positive transformation , Then the query is modified linearly , The last inverse transformation to find the answer .

Time complexity $O(2^{13}\sum c_i+m\cdot 2^{13}\cdot 13)$ .

CODE

#include<set>
#include<map>
#include<queue>
#include<cmath>
#include<vector>
#include<random>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 2005
#define LL long long
#define DB double
#define ENDL putchar('\n')
#define lowbit(x) (-(x) & (x))
#define FI first
#define SE second
inline int xchar() {
    
	static const int maxnn = 1000000;
	static char b[maxnn];
	static int pos = 0,len = 0;
	if(pos == len) pos = 0,len = fread(b,1,maxnn,stdin);
	if(pos == len) return -1;
	return b[pos ++];
}
//#define getchar() xchar()
inline LL read() {
    
	LL f=1,x=0;int s = getchar();
	while(s<'0'||s>'9') {
    if(s<0)return -1;if(s=='-')f=-f;s=getchar();}
	while(s>='0'&&s<='9') {
    x=(x<<3)+(x<<1)+(s^48);s = getchar();}
	return f * x;
}
void putpos(LL x) {
    
	if(!x) return ;
	putpos(x/10); putchar((x%10)^48);
}
void putnum(LL x) {
    
	if(!x) {
    putchar('0');return ;}
	if(x < 0) putchar('-'),x = -x;
	return putpos(x);
}
inline void AIput(LL x,int c) {
    putnum(x);putchar(c);}

const int MOD = 998244353;
const int iv2 = (MOD+1)/2;
int n,m,s,o,k;
int pw[1000005],ip[1000005];
int p[310],f[MAXN],cnt,id[MAXN];
void sieve(int n) {
    
	for(int i = 2;i <= n;i ++) {
    
		if(!f[i]) p[++ cnt] = i,id[i] = cnt;
		for(int j = 1;j <= cnt && i*p[j] <= n;j ++) {
    
			f[i*p[j]] = 1; if(i % p[j] == 0) break;
		}
	}return ;
}
int ct[MAXN];
int s0[310][1<<13|5],s1[310][1<<13|5];
inline void MD(int &x) {
    if(x>=MOD)x-=MOD;}
void DWTOR(int *s,int n) {
    
	for(int k = 2;k <= n;k <<= 1) {
    
		for(int j = 0;j < n;j += k) {
    
			for(int i = j;i < j+(k>>1);i ++) {
    
				MD(s[i+(k>>1)] += s[i]);
			}
		}
	} return ;
}
void IDWTOR(int *s,int n) {
    
	for(int k = n;k > 1;k >>= 1) {
    
		for(int j = 0;j < n;j += k) {
    
			for(int i = j;i < j+(k>>1);i ++) {
    
				MD(s[i+(k>>1)] += MOD-s[i]);
			}
		}
	} return ;
}
int tmp[1<<13|5];
int A[1<<13|5];
int main() {
    

// freopen(...

	sieve(2000);
	n = read();
	pw[0] = 1; ip[0] = 1;
	for(int i = 1;i <= n;i ++) {
    
		MD(pw[i] = (pw[i-1]<<1));
		ip[i] = ip[i-1] *1ll* iv2 % MOD;
		ct[read()] ++;
	}
	int tp = 1<<13;
	for(int i = 0;i < tp;i ++) tmp[i] = 1;
	for(int i = 0;i <= cnt;i ++) {
    
		for(int j = 0;j < tp;j ++) s0[i][j] = 1,s1[i][j] = 1;
	}
	for(int i = 1;i <= 2000;i ++) {
    
		int nn = i;
		int ls = 0,S = 0;
		for(int j = 1;j <= cnt && p[j] <= nn;j ++) {
    
			if(nn % p[j] == 0) {
    
				if(j <= 13) S |= (1<<(j-1));
				ls = j; while(nn % p[j] == 0) nn /= p[j];
			}
		}
		int nm = pw[ct[i]],nm2 = ip[ct[i]];
		for(int j = 0;j < tp;j ++) {
    
			if((j&S) == S) {
    
				s0[ls][j] = s0[ls][j] *1ll* nm2 % MOD;
				s1[ls][j] = s1[ls][j] *1ll* nm % MOD;
			}
		}
	}
	for(int i = 0;i <= cnt;i ++) {
    
		for(int j = 0;j < tp;j ++) {
    
			tmp[j] = tmp[j] *1ll* s1[i][j] % MOD;
			MD(s1[i][j] += MOD-1);
		}
	}
	m = read();
	for(int i = 1;i <= m;i ++) {
    
		k = read();
		for(int j = 0;j < tp;j ++) A[j] = tmp[j];
		for(int j = 1;j <= cnt;j ++) f[j] = 0;
		int S = 0;
		while(k --) {
    
			int x = id[read()];
			if(x <= 13) S |= (1<<(x-1));
			else f[x] = 1;
		}
		for(int j = 14;j <= cnt;j ++) {
    
			if(f[j]) {
    
				for(int k = 0;k < tp;k ++) {
    
					A[k] = A[k] *1ll* s0[j][k] % MOD * s1[j][k] % MOD;
				}
			}
		}
		IDWTOR(A,tp);
		int ans = 0;
		for(int j = 0;j < tp;j ++) {
    
			if((j&S) == S) {
    
				MD(ans += A[j]);
			}
		}
		AIput(ans,'\n');
	}
	return 0;
}