P8292 [省选联考 2022] 卡牌
lg_zhou
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$）的数有多少。这个数组是可以预处理的。对于每个询问来说，大力容斥，这道题就做完了。
代码：
```cpp
#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;
}
```