P8292 [省选联考 2022] 卡牌

· · 题解

赛时想到容斥，想到正难则反，不知道哪根筋搭错了，最后喜提 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;
}