题解：AT_abc236_h [ABC236Ex] Distinct Multiples

· · 题解

Solution

安徽省集考了一个类似的题。

如果不加上 A 互不相同的限制，那么方案显然为 \prod_{i=1}^n \lfloor \frac{M}{D_i} \rfloor。

如果 A_i=A_j，就在 i 和 j 之间连边。我们希望边数 =0，所以考虑容斥，钦定若干条边。

直接钦定边是不好做的，但是考虑钦定的边的效果——一定是将 n 个点合并成若干连通块。

考虑枚举效果，对每个连通块，计算他的容斥系数。一个大小为 k 的连通块的容斥系数意思是：对于所有使得图连通的边集，计算 (-1)^{|E|} 并求和。

设容斥系数为 f_n。

如果不要求连通，发现容斥系数的和为 [n=1]。

使用图计数的常见套路，有：

f_n = [n=1]-\sum_{i=1}^{n-1} \binom{n-1}{i-1} f_i [i=n-1]

容易得到 f_n = (-1)^{n-1} (n-1)!。

跑一个集合幂级数 exp 即可做到 O(n^2 2^n)。

#include<bits/stdc++.h>
#define int long long 
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=(1<<16)+10,MOD=998244353;
int n,m,frac[MAXN],a[MAXN],f[17][MAXN],g[17][MAXN];
void fwt(int *f,int l,int r) {
    if(l==r) return ;
    int mid=(l+r)>>1;
    fwt(f,l,mid),fwt(f,mid+1,r);
    ffor(i,l,mid) {
        int j=i-l+mid+1;
        int x=f[i],y=f[j];
        f[i]=(x+y)%MOD,f[j]=(x-y)%MOD;
    }
    return ;
}
int inv[MAXN];
int qpow(int base,int p) {
    int ans=1;
    while(p) {
        if(p&1) ans=ans*base%MOD;
        base=base*base%MOD,p>>=1;
    }
    return ans;
}
void exp(int *f,int *g) {
    g[0]=1;
    ffor(i,1,n) {
        ffor(j,1,i) g[i]=(g[i]+g[i-j]*f[j]%MOD*j)%MOD;
        g[i]=g[i]*inv[i]%MOD;   
    }
    return ;
}
int zzz[MAXN];
signed main() {
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>m,frac[0]=1;
    ffor(i,1,n) frac[i]=frac[i-1]*(-i)%MOD;
    ffor(i,1,n) cin>>a[i];
    memset(zzz,-1,sizeof(zzz));
    zzz[0]=1;
    ffor(i,1,(1<<n)-1) {
        int lb=(i&-i),lid=log2(lb)+1;
        if(zzz[i-lb]!=-1) {
            __int128 val=((__int128)1)*zzz[i-lb]*a[lid]/__gcd(zzz[i-lb],a[lid]);
            if(val<=m) zzz[i]=val;
        }
    }
    memset(a,0,sizeof(a));
    ffor(i,1,(1<<n)-1) if(zzz[i]!=-1) a[i]=(m/zzz[i])%MOD*frac[__builtin_popcount(i)-1]%MOD;
    ffor(i,0,(1<<n)-1) f[__builtin_popcount(i)][i]=a[i];
    ffor(i,1,n) inv[i]=qpow(i,MOD-2);
    ffor(i,0,n) fwt(f[i],0,(1<<n)-1);
    ffor(i,0,(1<<n)-1) {
        int F[21],G[21];
        memset(F,0,sizeof(F)),memset(G,0,sizeof(G));
        ffor(j,0,n) F[j]=f[j][i];
        exp(F,G);
        ffor(j,0,n) g[j][i]=G[j]; 
    }
    ffor(i,0,n) fwt(g[i],0,(1<<n)-1);
    int div=qpow(1<<n,MOD-2);
    cout<<(g[n][(1<<n)-1]*div%MOD+MOD)%MOD;
    return 0;
}