我决定不整什么写过的题的集合了，写不过来。
想到啥题好就写啥。
这题是个很好的套路。
考虑到值域不怎么大，想到根号分治。也就是小于根号的质数不超过 \(14\) 个，大于根号的质数只有一个。
考虑寿司晚宴的做法，对小质数和大质数分开做。如果是小质数，那么 \(14\) 个可以状态压缩。然后考虑容斥，直接找全包括肯定不好做，考虑做一个都没有的。
\(ans=\sum\limits_{S\in target} (-1)^{|S|} f_{S}\)，\(f_S\) 表示这个状态下每个数字都包括这个状态，选择数字的方案数。
然后考虑怎样做大质数的。就是统计下每个 \(S\) 下不同的大质数的个数，假设当前询问包大质数 \(g\)，当前的状态包含这个数字的数量为 \(cnt\)，那么这个状态下的 \(f\) 就要乘 \(2^{cnt}-1\)，因为至少要选一个，反之，如果询问不包含这个 \(g\)，那么方案数乘 \(2^{cnt}\)。
然后就能求出带大质数时的 \(f_S\)。然后正常容斥一下就行。
我是把一个大质数都不算的设为 \(1\)。
然后被卡常了，可以预处理一些 \(2^k\) 之类的。
我说的不清楚喵，看代码喵。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2003;
const int mod=998244353;
ll ksm(ll x,ll y)
{
ll ret=1;
while(y)
{
if(y&1) ret=ret*x%mod;
x=x*x%mod; y>>=1;
}
return ret;
}
int n,m;
int s[1000052];
int prime[maxn],cnt_tot;bool vis[maxn];
int f[9002][2003];ll val[9005],ss[9002][2003],inv[9002][2003]; vector<int> que;
int mp[3002],pos[2003],q[2003],lst[maxn],a[maxn];
bitset<5> S;int B=8191;
void init()
{
for(int i=2;i<=2000;i++)
{
if(vis[i]) continue;
cnt_tot++; prime[cnt_tot]=i; pos[i]=cnt_tot;
for(int j=i+i;j<=2000;j+=i) vis[j]=1;
}
for(int i=1;i<=2000;i++)
{
lst[i]=1;
for(int j=1;j<=cnt_tot;j++)
{
if(i%prime[j]) continue;
if(j<=13) q[i]|=(1<<(j-1));
else lst[i]=j;
}
//S=q[i]; cout<<i<<" "<<S<<endl;
}
for(int i=0;i<(1<<13);i++)
{
for(int j=1;j<=2000;j++)
{
if(((B^q[j])&i)!=i) continue;
f[i][lst[j]]=(f[i][lst[j]]+a[j])%mod;
}
}
for(int i=0;i<(1<<13);i++)
{
val[i]=1ll;
for(int j=1;j<=cnt_tot;j++)
{
if(j>=2&&j<=13) continue;
val[i]=val[i]*ksm(2,f[i][j])%mod;
ss[i][j]=ksm(2,f[i][j]);
inv[i][j]=ksm(ss[i][j],mod-2);
}
}
/*for(int i=0;i<(1<<4);i++)
{
for(int j=1;j<=2000;j++)
{
if(f[i][j])
{
S=i; cout<<"f["<<S<<"]["<<j<<"]="<<f[i][j]<<endl;
}
}
}*/
}
namespace IO
{
#define gc()(xS==xTT&&(xTT=(xS=xB)+fread(xB,1,1<<20,stdin),xS==xTT)?0:*xS++)
#define pc(x)(p3-obuf<1000000)?(*p3++=x):(fwrite(obuf,p3-obuf,1,stdout),p3=obuf,*p3++=x)
char xch,xB[1<<20],*xS=xB,*xTT=xB,obuf[1000000],*p3=obuf;
inline ll read(){char ch=gc();ll x=0,f=1;while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=gc();}while('0'<=ch&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}return x*f;}
static char cc[20];template<typename item>
inline void pt( item x){ int len=0;if(!x)pc('0');if(x<0)x=-x,pc('-');while(x)cc[len++]=x%10+'0',x/=10;while(len--)pc(cc[len]);}
inline void pS(string s){for(int i=0;i<s.length();i++)pc(s[i]);}
inline ll read2(){char ch=gc();ll x=0,f=1;while(ch<'0'||ch>'1'){if(ch=='-')f=-1;ch=gc();}while('0'<=ch&&ch<='9'){x=(x<<1)+(ch^48);ch=gc();}return x*f;}
}
vector<int> big;
int main()
{
//freopen("card.in","r",stdin);
//freopen("card.out","w",stdout);
n=IO::read();
for(int i=1;i<=n;i++) s[i]=IO::read(),a[s[i]]++;
m=IO::read();
init();
while(m--)
{
int c,tmp; big.resize(0); que.resize(0);
c=IO::read();
for(int i=0;i<=2000;i++) mp[i]=0;
int bak=0;
for(int i=1;i<=c;i++)
{
tmp=IO::read();que.push_back(tmp),mp[tmp]=1;
if(pos[tmp]<=13) bak|=(1<<(pos[tmp]-1));
else big.push_back(pos[tmp]);
}
ll ans=0;
for(int i=bak;i>=0;i=bak&(i-1))
{
ll ret=val[i];
for(auto j:big)
{
ret=ret*(ss[i][j]-1)%mod*inv[i][j]%mod;
}
if(!i)
{
ans=(ans+ret)%mod;
//S=i; cout<<S<<" "<<ret<<endl;
break;
}
else
{
int cnt=__builtin_popcount((i&bak));
if(cnt&1) ans=(ans-ret+mod)%mod;
else ans=(ans+ret)%mod;
//S=i; cout<<S<<" "<<ret*((cnt&1)?-1:1)<<endl;
}
}
printf("%lld\n",ans);
}
fprintf(stderr,"%.4lf\n",1.0*clock()/CLOCKS_PER_SEC);
}