自动搬运

查看原文

来自洛谷，原作者为

	lg_zhou 落月摇情满江树

搬运于2025-08-24 22:37:44，当前版本为作者最后更新于2022-04-20 13:12:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

赛时想到容斥，想到正难则反，不知道哪根筋搭错了，最后喜提 $25pts$ 。看到好多大佬写的 FWT，然而并不会，也并不需要。

update on 4.27 修改了 $s[i] = 1$ 的情况

选法题，要么动规，要么数学，这道题一眼看去就是容斥题。直接容斥不是特别好做，样例给了充足的提示，考虑正难则反。就是全部的方案数减去不合法的即可。

首先 $n$ 并没有用，因为我们只关心同一类的数有多少个，而最多有两千个不一样的数。

这样 $s[i]\le30$ 的部分分解法就呼之欲出了。答案即为 $2^n$ 减去选排列中不含 $p[j](j \in [1,c_i])$ 的方案数，这样不含两个质数的方案数被减去两遍，要加上，再减去含不含三个质数的...... 由于 $s[i]$ 很小，$30$ 以内的质数只有十一个，暴力枚举即可。

如果 $s[i] \le 2000$，考虑根号分治。已知 $43*47>2000$。所以每个数最多只有一个大于等于 $43$ 的质因数。假设我们并不关心小于 $43$ 的质数，那就很简单了，枚举每一个大于等于 $43$ 的质数，统计数列中有多少数被它整除，记为 $f[i]$。如果询问集合中包含这个质数，那么就至少选一个，答案 $*=2^{f[i]}-1$，否则选不选都行，答案 $*=2^{f[i]}$

如果把前十三个质数（$\le 43$）加进来，依旧可以暴力容斥，而且这样我们只用枚举前十三个质数的情况即可。

具体的，记 $f[i][j]$ 为 $i$ 代表不含前十三个质数枚举的情况（状压），$j$ 代表是第 $j$ 个质数倍数（$j>13$）的数有多少。这个数组是可以预处理的。对于每个询问来说，大力容斥，这道题就做完了。

代码：

#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#define int long long
using namespace std;
const int maxn = 2005;
const int mod = 998244353;
int is_p[maxn], p[maxn], hsp[maxn],cnt;
vector<int> v[maxn];
long long n,m,c;
int q[2005];
int a[maxn],ans;
long long edans;

int f[(1<<13)+5][305];
int ksm(int a, int b){
	int mul = 1;
	while(b){
		if (b&1){
			mul = mul*a%mod;
		}
		a = a*a%mod;
		b >>= 1;
	}
	return mul;
}
void init(){
	for (int i = 2; i <= 2000; i++){ // 埃筛 
		if (!is_p[i]){
			p[++cnt] = i;
			hsp[i] = cnt;
		}
		for (int j = 2; j*i <= 2000; j++){
			is_p[i*j] = 1;
		}
	}
	for (int i = 2; i <= 2000; i++){
		for (int j = 1; j <= cnt; j++){
			if (i%p[j] == 0){
				if (j <= 13) q[i] |= (1<<j-1); //查看每个数的前13个质数的包含情况 
				v[i].push_back(j); //所有数的质因子 
			} 
		}
	}
}


vector<int> hvp;

int tt[(1<<13)+5];//不含当前状态的数一共有多少 
signed main(){
	//freopen("a.in","r",stdin);
	//freopen("card.out","w",stdout);
	cin >> n;
	init();
	for (int i = 1; i <= n; i++){
		long long val;
		cin >> val;
		a[val]++;
	}

	cin >> m;
	for (int i = 0; i < (1<<13); i++){//枚举不含哪些质数 
		for (int j = 2; j <= 2000; j++){
			if ( (q[j]&i) ) continue; //说明含了，continue 
			f[i][v[j][v[j].size()-1]] += a[j]; //个数加上这个数有多少 
			f[i][v[j][v[j].size()-1]] %= mod;
			tt[i] += a[j];
		}
		tt[i] += a[1];
	}
	
	
	for (int i = 1; i <= m; i++){
		
		edans = 0;
		hvp.clear();
		
		int less = 0;//询问序列与前十三个质数的交集 
		cin >> c;
		for (int j = 1; j <= c; j++){
			long long t;
			cin >> t;
			hvp.push_back(t);
			if (hsp[t] <= 13){
				less |= (1<<hsp[t]-1);
			}
		}
		sort(hvp.begin(),hvp.end());
		
		for (int j = 0; j < (1<<13); j++){
			if ( (j|less) != less) continue;
			int ct = tt[j];//一共有这么多数 
			ans = 1;
			for (int k = 0; k < c; k++){
				if (hvp[k] <= 41) continue;
				(ans *= (ksm(2,f[j][hsp[hvp[k]]])-1)) %= mod;//必须选 
				ct -= f[j][hsp[hvp[k]]];
			}
			(ans *= ksm(2,ct)) %= mod;//剩下的选不选都行 
			
			int cnt1 = 0;
			for (int k = 0; k <= 13; k++) cnt1 += (j>>k&1);//看看容斥是加还是减 
			if (cnt1&1) (edans -= ans)%=mod;
			else (edans+=ans)%=mod;
		}
		cout << (edans%mod+mod)%mod << endl;
	}
	
	return 0;
}