题解：AT_abc349_f [ABC349F] Subsequence LCM

· · 题解

Part 1 题意

给定一个长度为 n 的序列，求出 \operatorname{lcm} 为 m 的子序列个数，数据范围 n\le 2\times10^5，m\le 10^{16}，a_i\le10^{16}。

Part 2 主要思路

做法：一点点数论内容 + 状压 dp。

首先，我们可以从另一个角度来考虑 \operatorname{lcm}：

对于两个正整数数 a,b，设 a=\sum_{i=1}^{k} p_{i}^{c_{p_i}}，b=\sum_{i=1}^{l} q_{i}^{d_{q_i}}，设集合 S\in p \cup q，那么 \operatorname{lcm}(a,b)=\sum_{i\in S}S_i^{\max(c_{S_i},d_{S_i})}，如此做我们可以通过维护 S,c,d 三个集合来处理这个问题。

我们不难发现，c,d 集合的大小取决于不同质因数的个数，而可以组成 10^{16} 以下的数的不同质因数不超过 13 个。因为我们可以使用状压。

第一步：

排除一定不可能产生任何贡献的数，也就是排除所有无法整除 m 的数。

第二步：

将 m 质因数分解，求出 m 的质因数集合。

第三步：

求出数组 A 中每个元素的初始贡献。

我们回到原来那个式子。如果两个数的 \operatorname{lcm} 可能 为 m，那么其中一个数至少有一个质因子个数与 m 是相同的。所以对于每个元素，我们枚举每个 m 中出现的质因数（因为排除之后的数可以整除 m，所以这些数中的质因数一定在 m 中也出现过），然后判断当前元素对于当前枚举的质因数个数与 m 是否相同，如果相同，则加上对应的贡献。

由于我们使用了状压 dp，所以对于第 i 个质因数，令这个数在 m 中出现次数为 cnt_i，如果它对于 A_j 产生了贡献，那么我们令初始贡献数组 f_j 加上 2^{cnt_i-1}，即令 f_j 的二进制表示中从右到左第 cnt_i 位为 1。

第四步：

进行状压 dp。

定义 bxf 为 dp 数组 bxf_i 表示第 i 位产生的贡献，那么首先有 bxf_0=1 用于初始化。

我们令 bxf_i 的二进制表示从右到左第 k 位为 1，当且仅当加入 A_i 时的贡献中第 k 个质因数个数与 m 中第 k 个质因数个数相同。

因此当加入一个数 A_i，我们可以枚举每个状态，设当前状态为 j ，对于二进制下每一位表示的质因数，对于 A_i 和 j 最小公倍数的状态，如果 A_i 和 j 二进制下的每一位中有至少有一个为 1，那么 \operatorname{lcm}(A_i,j) 的第 i 位也为 1。

我们可以发现，这种转移形式可以转化为按位或运算。

那么有如下转移方案：bxf_{f_i \mid j}=bxf_{f_i \mid j}+bxf_j ，即若 j 向 A_i 做了贡献，那么我们令 A_i 与状态 j 的最大公约数所表示的状态加上 j 的贡献。

特别注意：

假设 m 分解质因数之后不同质因子个数为 k，则有 k \le 13，时间复杂度 O(2^kn) ，可以通过本题。

Part 3 代码

#include<bits/stdc++.h>
#define mod 998244353
#define int long long
using namespace std;

int b[200005],f[200005],bxf[1<<15],xf,n,m;
struct zys{
    int num;
    int cnt;
};
vector<zys> x;

signed main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int x;cin>>x;
        if(m%x==0)b[++xf]=x;
    }
    int m2=m;
    for(int i=2;i*i<=m2;i++){
        if(m2%i==0)x.push_back({i,0}); 
        while(m2%i==0){
            x[x.size()-1].cnt++;
            m2/=i;
        }
    }
    if(m2>1){
        x.push_back({m2,1});
    }
    //cout<<1;
    //for(auto i:x)cout<<i.num<<" "<<i.cnt<<endl; 
    int cnt1,j2,cnt2;
    for(int i=1;i<=xf;i++){
        cnt2=0;
        for(auto j:x){
            cnt2++;
            cnt1=0,j2=b[i],m2=m;
            while(j2%j.num==0){
                j2/=j.num;cnt1++;
            }
            if(cnt1==j.cnt)f[i]+=(1<<(cnt2-1));
        }
    }
    bxf[0]=1;
    for(int i=1;i<=xf;i++){
        for(int j=(1<<x.size())-1;j>=0;j--){
            bxf[f[i]|j]+=bxf[j];
            if(bxf[f[i]|j]>=mod)bxf[f[i]|j]-=mod;
        }
    }
    if(m==1)cout<<bxf[(1<<x.size())-1]-1;
    else cout<<bxf[(1<<x.size())-1];
}