题解：P16141 集合（set）

· · 题解

简单无脑做法！

套路地，以 \sqrt n 为界将质数分成小质数和大质数，此时小质数最多有 14 个，设其数量为 B。

然后把所有数按照其至多有一个的大质因数分组，因子里有第 i 个大质数就分在第 i 组。特殊地，没有大质因数的数分在第 0 组。

我们要计算这个形似 \text{mex} 的东西，考虑对于每个质数分别计算贡献为她的方案数。也就是对于 p，要求选出一些数，这些数的质因数中出现了小于 p 的所有质数，且未出现 p 的方案数。

把小质数是否出现状压到集合 S 里。

设 dpl_{i,S} 为第 0 组任意选数，1 \sim i 组每组至少选了 1 个数，其余均未选，此时选出的数的质因数中小质数出现了 S 的方案数。

设 dpr_{i,S} 为第 i \sim \pi(n) - B 组每组任意选数，其余均未选，此时选出的数的质因数中小质数出现了 S 的方案数。

大力转移。对于 dpl_i，先 dpl_{i,S} \gets dpl_{i-1,S}，然后枚举第 i 组内每个数，在当前 dpl_i 的基础上，将选她的方案加进去。如果倒序枚举就不需要新开数组了。因为 dpl 是强制每组必选，所以枚举完这个组之后应该 dpl_{i,S} \gets -dpl_{i-1,S}，去掉没选的。dpr 同理，只是不要求必选。第 0 组需要特判。

那么，对于第 i 个大质数，其作为贡献的方案数就是 dpl_{i-1} 和 dpr_{i+1} 或卷积卷起来之后的 dp_{2^B-1}，使用 FWT 即可。小质数就把 dpl_{0} 和 dpr_{1} 卷起来枚举每个状态。

时间复杂度 O(2^B(B\pi(n)+n))。注意预处理要筛到 2003。

:::info[代码] 代码实现是直接以 \sqrt{2000} 为界的。

#include<bits/stdc++.h>
#define i128 __int128
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define Pii pair<int,int>
#define fi first
#define se second
#define f(x,y) fixed<<setprecision(y)<<x
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,rp,stdin),p1==p2)?EOF:*p1++)

using namespace std;
const int N=2e3+10;
const int M=1<<14;
const int mod=998244353;
const int rp=1e6+10;

int n,sq,cnt,res,b[N],pr[N],p[N],dp[N];
int dpl[N][M],dpr[N][M],ans[M];
vector<int> vt[N];
bitset<N> isp;
char buf[rp],*p1=buf,*p2=buf;

inline int read()
{
    int x=0,f=1; char c=0;
    while(!isdigit(c)) {if(c=='-') f=-1; c=gc();}
    while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=gc();
    return x*f;
}

inline char read_ch()
{
    char c=0;
    while((!isalpha(c))&&(!isdigit(c))) c=gc();
    return c;
}

inline void shai(int n)//埃氏筛
{
    isp.set(); isp[0]=isp[1]=0;
    for(int i=2;i<=n;++i)
        if(isp[i])
        {
            pr[++cnt]=i; b[i]=cnt;
            for(int j=i+i;j<=n;j+=i) isp[j]=0;
        }
}

inline void fwt_or(int A[],int v)
{
    for(int i=1;i<M;i<<=1)
        for(int j=0;j<M;j+=i+i)
            for(int k=j;k<i+j;++k)
                A[i+k]=(A[i+k]+1ll*A[k]*v)%mod;
}

inline void add(int &x,ll y) {x=(x+y)%mod;}

signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin>>n; shai(2003); sq=14;
    for(int i=1;i<=n;++i) if(b[i]) b[i]-=sq; cnt-=sq;//从质数 cnt 变成大质数 cnt
    for(int i=1;i<=n;++i)
    {
        int nw=i;
        for(int j=1;j<=sq;++j)
            if(!(i%pr[j]))//分解质因数
            {
                p[i]|=1<<(j-1);
                while(!(nw%pr[j])) nw/=pr[j];
            }
        vt[b[nw]].push_back(i);//按剩下的大质数分组
    }
    dpl[0][0]=1;//初始化
    for(int i=0;i<=cnt;++i)
    {
        if(i) memcpy(dpl[i],dpl[i-1],sizeof dpl[i]);//注意判 i=0
        for(auto a:vt[i])
            for(int j=(1<<sq)-1;j>=0;--j)
                add(dpl[i][j|p[a]],dpl[i][j]);//倒着，选了 a 的转移
        if(i)//这个也是，注意判 i=0
            for(int j=0;j<(1<<sq);++j)
                add(dpl[i][j],-dpl[i-1][j]);
    }
    dpr[cnt+1][0]=1;//初始化
    for(int i=cnt;i>=0;--i)
    {
        memcpy(dpr[i],dpr[i+1],sizeof dpr[i]);
        for(auto a:vt[i])
            for(int j=(1<<sq)-1;j>=0;--j)
                add(dpr[i][j|p[a]],dpr[i][j]);//倒着，选了 a 的转移
    }
    for(int i=0;i<=cnt+1;++i) fwt_or(dpl[i],1),fwt_or(dpr[i],1);//fwt 过去
    for(int i=1;i<=cnt;++i)
    {
        for(int j=0;j<(1<<sq);++j)
            ans[j]=1ll*dpl[i-1][j]*dpr[i+1][j]%mod;
        fwt_or(ans,-1);//fwt 回来
        add(res,1ll*ans[(1<<sq)-1]*pr[i+sq]);//对大质数算贡献
    }
    for(int i=0;i<(1<<sq);++i)
        ans[i]=1ll*dpl[0][i]*dpr[1][i]%mod;
    fwt_or(ans,-1);//fwt 回来
    for(int i=0;i<(1<<sq);++i)
        for(int j=1;j<=sq;++j)
            if(!(i&(1<<(j-1))))
                {add(res,1ll*ans[i]*pr[j]); break;}//对小质数算贡献
    cout<<(res+mod)%mod;
    return 0;
}

:::