C++ 解法, 执行用时: 151ms, 内存消耗: 1400K, 提交时间: 2022-03-22 18:36:09

#include<bits/stdc++.h>
#define ll long long
#define PII pair<int,int>
using namespace std;
template<class T> 
inline void read(T &x){ 
	x=0; char c; int sign=1; 
	do{ c=getchar(); if(c=='-') sign=-1;}while(!isdigit(c)); 
	do{ x=x*10+c-'0',c=getchar();}while(isdigit(c)); 
	x*=sign; 
} 
const int N=5e5+50,mod=998244353;
ll gcd(ll a,ll b){
	return b?gcd(b,a%b):a;
}
int n,m,bin[N],h[N],dp[N];
ll M,d[30],lc[N];
int main(){
	read(n),read(M);
	m=1<<n;
	h[1]=1;
	for(int i=0;i<n;++i) read(d[i]),lc[1<<i]=d[i];
	for(int i=1;i<m;++i) bin[i]=bin[i>>1]+(i&1);
	for(int i=2;i<=n;++i) h[i]=1LL*(mod-i+1)*h[i-1]%mod;
	for(int i=1;i<m;++i){
		if(bin[i]==1) continue;
		int j=i&-i;
		if(lc[i-j]==-1) lc[i]=-1;
		else{
			ll t=gcd(lc[i-j],lc[j]);
			ll t1=lc[j]/t;
			if(lc[i-j]>M/t1) lc[i]=-1;
			else lc[i]=lc[i-j]*t1;
		}
	}
	for(int i=1;i<m;++i){
		if(lc[i]==-1) lc[i]=0;
		else lc[i]=M/lc[i]%mod;
		lc[i]=lc[i]*h[bin[i]]%mod;
		//cout<<lc[i]<<endl;
	}
	
	dp[0]=1;
	for(int i=1;i<m;++i){
		int k=i&-i;
		for(int j=i;j>0;j=(j-1)&i) if(j&k)
		dp[i]=(dp[i]+ lc[j]*dp[i^j]%mod )%mod;
	}
	cout<<dp[m-1];
	return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 384ms, 内存消耗: 1188K, 提交时间: 2022-08-19 17:37:16

#include<bits/stdc++.h>
using namespace std ;
#define ll long long
const int mod = 998244353 ;
const int N = 150000 ;
int n ;
ll m,d[N] ;
int f[N],g[N],h[N],b[N] ;
ll gcd(ll a,ll b)
{
	return b?gcd(b,a%b):a ;
}
ll LCM(ll a,ll b)
{
	ll d=gcd(a,b) ;
	if((__int128)a*b/d>m) return m+1 ;
	else return (__int128)a*b/d ;
}
int main()
{
	scanf("%d%lld",&n,&m) ;
	for(int i=0;i<n;++i) scanf("%lld",&d[i]) ;
	b[0]=0 ;
	for(int i=1;i<(1<<n);++i) b[i]=b[i>>1]+(i&1) ;
	h[1]=1 ;
	for(int i=2;i<=n;++i) h[i]=(mod-i+1ll)*h[i-1]%mod ;
	g[0]=m ;
	for(int i=1;i<(1<<n);++i)
	{
		ll lcm=1 ;
		for(int j=0;j<n;j++) if(i>>j&1)
		{
			lcm=LCM(lcm,d[j]) ;
			g[i]=m/lcm ;
		}
	}
	f[0]=1 ;
	for(int i=1;i<(1<<n);++i)
	{
		int x=i&-i ;
		for(int j=i;j;j=(j-1)&i) if(j&x)
			f[i]=(f[i]+(ll)f[i^j]*g[j]%mod*h[b[j]]%mod)%mod ;
	}
	printf("%d\n",f[(1<<n)-1]) ;
	return 0 ;
}