ABC349F 题解

· · 题解

做法介绍

本题解与题解区所有题解做法都不相同，不需要 FWT 或 bitset。

令 m 的质因数数量为 c，那么本做法复杂度为 O(\sqrt m + (2^{c}+n)c)。

一些前置思考

考虑 lcm 的性质。

一些数的 lcm，本质上是这些数的每个质因数的次数取最大值，然后乘起来。

首先，如果一个数不是 m 的因数，那么这个数一定不会出现在最终的答案集合，先将这个数从输入的数组删除，接下来的分析均只考虑剩下的数。

现在，一种选择方案是合法的，当且仅当，对于 m 的每个质因数 p，本选择方案里面存在一个数，使得这个数里面 p 的次数等于 m 里面 p 的次数。

容易发现，m 的质因数个数小于等于 14，这就提示我们使用状态压缩。

现在，根据上述方案，可以计算出输入数组中的每个数可以搞定 m 的哪些质因数。

现在，问题转化为：

给定一个整数数组 a，\forall 1 \le i \le n,0 \le a_i \lt 2^{14}。
给定一个正整数 m \lt 2^{14}，求 a 的子序列个数，使得子序列内部所有数的或值等于 m，子序列不同当且仅当选择的位置集合不同。

转化后的处理

考虑容斥。

可以限制一下哪些位可以是 1，枚举这些位。

令 g(msk) 代表只有 msk 集合的位可以是 1，此时选择位置集合的方案数。

显然，令 x 代表只有 msk 集合的位可能是 1 的数的个数，那么 g(msk) = 2^{x}-1。

问题是，如何快速对于每个 msk，求出对应的 x。

这个很经典，是 SOSDP 的板子。

令 popcount(msk) 为 msk 集合的大小，all 代表全集。

那么如果 popcount(all)-popcount(msk) 是偶数，那么答案加上 g(msk)，否则减去 g(msk)。

对 m 质因数分解的复杂度为 O(\sqrt m)，预处理每个输入的数对应的状态的复杂度为 O(nc)，SOSDP 的复杂度为 O(2^cc)，容斥的复杂度为 O(2^c)。

故复杂度 O(\sqrt m + (n+2^c)c)。 

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(auto i=(a);i<=(b);i++)
#define REP(i,a,b) for(auto i=(a);i>=(b);i--)
#define FORK(i,a,b,k) for(auto i=(a);i<=(b);i+=(k))
#define REPK(i,a,b,k) for(auto i=(a);i>=(b);i-=(k))
#define pb push_back
#define mkpr make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
template<class T>
void ckmx(T& a,T b){
    a=max(a,b);
}
template<class T>
void ckmn(T& a,T b){
    a=min(a,b);
}
template<class T>
T gcd(T a,T b){
    return !b?a:gcd(b,a%b);
}
template<class T>
T lcm(T a,T b){
    return a/gcd(a,b)*b;
}
#define gc getchar()
#define eb emplace_back
#define pc putchar
#define ep empty()
#define fi first
#define se second
#define pln pc('\n');
#define islower(ch) (ch>='a'&&ch<='z')
#define isupper(ch) (ch>='A'&&ch<='Z')
#define isalpha(ch) (islower(ch)||isupper(ch))
template<class T>
void wrint(T x){
    if(x<0){
        x=-x;
        pc('-');
    }
    if(x>=10){
        wrint(x/10);
    }
    pc(x%10^48);
}
template<class T>
void wrintln(T x){
    wrint(x);
    pln
}
template<class T>
void read(T& x){
    x=0;
    int f=1;
    char ch=gc;
    while(!isdigit(ch)){
        if(ch=='-')f=-1;
        ch=gc;
    }
    while(isdigit(ch)){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=gc;
    }
    x*=f;
}
const ll mod=998244353;
const int maxn=2e5+5;
ll qpow(ll a,ll b){
    ll ret=1;
    for(;b;a=a*a%mod,b>>=1){
        if(b&1){
            ret=ret*a%mod;
        }
    }
    return ret;
}
ll inv(ll a){
    return qpow(a,mod-2);
}
ll fact[maxn],factinv[maxn];
ll C(int n,int m){
    return n<m?0:fact[n]*factinv[m]%mod*factinv[n-m]%mod;
}
int n;
ll m,a[maxn];
int psgdivs[maxn];
ll pdivs[maxn];
int pdcnt;
void split(){
    ll _=m;
    for(ll i=2;i*i<=_;i++){
        if(_%i==0){
            pdivs[++pdcnt]=1;
            psgdivs[pdcnt]=i;
            while(_%i==0)_/=i,pdivs[pdcnt]*=i;
        }
    }
    if(_>=2)pdivs[++pdcnt]=_,psgdivs[pdcnt]=_;
}
int pre[1<<14];
ll pw2[maxn];
void solve(int id_of_test){
    read(n);
    read(m);
    FOR(i,1,n){
        read(a[i]);
    }
    split();
    FOR(i,1,n){
        int msk=0;
        FOR(j,1,pdcnt){
            if(a[i]%pdivs[j]==0&&(a[i]/pdivs[j])%psgdivs[j]!=0){
                msk|=(1<<j-1);
            }
        }
        if(m%a[i]==0)pre[msk]++;
    }
    int all=(1<<pdcnt)-1;
    FOR(bit,0,pdcnt-1){
        FOR(msk,0,all){
            if(msk&(1<<bit)){
                pre[msk]+=pre[msk^(1<<bit)];
            }
        }
    }
    ll ans=0;
    FOR(msk,0,all){
        ll mul=1;
        if(__builtin_parity(all^msk)){
            mul*=-1;
        }
        (ans+=(pw2[pre[msk]]-1)*mul)%=mod;
    }
    printf("%lld\n",(ans+mod)%mod);
}
int main()
{
    pw2[0]=1;
    FOR(i,1,maxn-1)pw2[i]=pw2[i-1]*2%mod;
    fact[0]=1;
    FOR(i,1,maxn-1)fact[i]=fact[i-1]*i%mod;
    factinv[maxn-1]=inv(fact[maxn-1]);
    REP(i,maxn-1,1){
        factinv[i-1]=factinv[i]*i%mod;
    }
    int T;
    T=1;
    FOR(_,1,T){
        solve(_);
    }
    return 0;
}