提交记录

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10,M=998244353;
int n,m;
int a[N],k[N],idx;
int t[N],f[N];
int F(int x) {
	int res=1,k=2;
	while(x) {
		if(x&1)(res*=k)%=M;
		(k*=k)%=M;
		x>>=1;
	}
	return res;
}
int cnt=0;
signed main() {
	cin>>n>>m;
	if(m==1) {
		int x;
		while(n--) {
			cin>>x;
			if(x==1)cnt++;
		}
		cout<<F(cnt)-1<<endl;
		return 0;
	}
	for(int i=2;i*i<=m;i++) {
		if(m==1)break;
		if(m%i==0) {
			a[idx++]=i;
			while(m%i==0) {
				m/=i;
				k[idx-1]++;
			}
		}
	}
	if(m>1) {
		k[idx]=1;
		a[idx++]=m;
	}
//	cout<<idx<<endl; 
	for(int i=1;i<=n;i++) {
		int x;
		cin>>x;
		if(x==1)cnt++;
		int c;
		bool flag=1;
		for(int j=0;j<idx;j++) {
			c=0;
			while(x%a[j]==0) {
				x/=a[j];
				c++;
			}
			if(c>k[j]) {
				flag=0;
				break;
			}
			if(c==k[j])t[i]+=(1<<j);
		}
		if(!flag)t[i]=-1;
	}
	
	f[0]=1;
//	cout<<idx<<endl;
	for(int i=1;i<=n;i++) {
		int a=t[i];
		if(a==-1)continue;
//		cout<<a<<endl;
		for(int i=(1<<idx)-1;i>=0;i--)(f[a|i]+=f[i])%=M;
//		for(int i=0;i<(1<<idx);i++)cout<<f[i]<<" ";
//		cout<<endl;
	}
	cout<<f[(1<<idx)-1]%M<<endl;
	return 0;
}

用的这篇题解的方法

不知道哪里出了问题，求大佬赐教