2022省选Day2T1解题报告

2022省选Day2T1解题报告

题目描述

给定\(n\)个数\(a_i\)，有\(m\)次询问，每次给定\(c_i\)个质数，你可以选出一些数满足选出的数的乘积可以被给定的\(c_i\)个质数整除，每次询问求有多少种选法

\(n\leq 1e6~~a_i\leq 2000~\sum c_i \leq 18000\)

题解

当我们拿到一个询问选法的题时，大概率不是数学就是\(dp\)

显然我们很容易看出需要容斥一手，但是发现如果直接容斥统计有点难

考虑正难则反，我们可以处理有多少种取法不满足条件

那么答案肯定就是\(2^n-res\) (\(res\)是不满足条件的选法数)

我们先考虑部分分怎么做

对于\(a_i<=30\)的情况，我们发现\(<30\)的质数只有10个

那么答案肯定就是\(2^n\)减去某一个质数不选的方案数，再加上某两个质数不选的方案数，再减去某三个质数不选的方案数……

然后考虑推广，我们发现对于一个数\(x\)最多只会有一个大于\(\sqrt x\)的质因数

所以我们可以把大于\(\sqrt{x}\)的数单独处理

而且对于两个大于\(\sqrt{x}\)的质数，是不可能同时不选也就是相对独立的

所以我们的容斥可以拿\(>43\)的质数必须有的方案数去减

这种做法可以当作套路去记一下，类似的题还有luogu2150 [NOI2015] 寿司晚宴

那么对于小于\(\sqrt{x}\)的质数总共最多\(13\)个(\(43*47>2000\))

所以我们考虑状压\(dp\)

我们可以求出\(f_{i,j}\)表示状态为\(i\)，且当前枚举的\(>43\)的质数为\(j\)的集合里的元素个数(\(i\)状态记录有哪几个质数不选)

然后枚举\(>43\)的质数，把这些质数从集合中剔除，并将状态为\(i\)的答案乘上\(2^{cnt}-1\)(\(cnt\)指能被当前枚举的质数整除的数的个数)

然后对于状态\(i\)中\(1\)的奇偶性判断加或减就行了

代码

#include 
#include 
#include 
#include 
#include 
#define int long long
#define file(a) freopen(#a".in","r",stdin),freopen(#a".out","w",stdout)
using namespace std;
const int maxn=1e6+5,Mod=998244353;
int n,a[maxn],m,cnt[2000+5],id[maxn],mp[2000+5];
int f[(1<<13)+5][350],cnt1[(1<<13)+5],ans;
bool is_prime[maxn];
vectorprime,s[2000+5];
void chkmax(int &x,int y) {if (xy) x=y;}
int read() {
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0' || ch>'9') {if (ch=='-') f=-1;ch=getchar();}
    while(ch<='9' && ch>='0') {x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x*f;
}
int lowbit(int x) {return x&(-x);}
int ksm(int a,int b) {
    int res=1;
    while(b) {
        if (b&1) (res*=a)%=Mod;
        b>>=1;(a*=a)%=Mod;
    }
    return res;
}
void init() {
    is_prime[1]=1;
    for (int i=2;i<=2000;i++) {
        if (!is_prime[i]) {
            id[i]=prime.size();
            prime.push_back(i);
        }
        for (size_t j=0;j