本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-04-25 10:29:25
做法介绍
本题解与题解区所有题解做法都不相同，不需要 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;
}
接下俩的操作，均按照默认就可以。
鲁ICP备2025150228号