C++11(clang++ 3.9) 解法, 执行用时: 1287ms, 内存消耗: 1556K, 提交时间: 2019-11-20 18:02:57

#include<bits/stdc++.h>
using namespace std;
const int N=100005,P=998244353,iv2=(P+1)/2,iv6=(P+1)/6; 
int n,k,s,mx,sq,cc,ans,vis[N],phi[N],pr[N],c[N],b[N],num[N];
inline int rd()
{
	int x=0;char c=getchar();while(!isdigit(c))c=getchar();
	while(isdigit(c))x=x*10+c-48,c=getchar();return x;
}
inline int pw(int a,int b){int r=1;for(;b;b>>=1,a=1ll*a*a%P)if(b&1)r=1ll*r*a%P;return r;}
inline void init(int n)
{
	vis[1]=1;phi[1]=1;
	for(int i=2;i<=n;i++)
	{
		if(!vis[i])pr[++cc]=i,phi[i]=i-1;
		for(int j=1;j<=cc&&i*pr[j]<=n;j++)
		{
			vis[i*pr[j]]=1;
			if(i%pr[j])phi[i*pr[j]]=phi[i]*(pr[j]-1);else{phi[i*pr[j]]=phi[i]*pr[j];break;}
		}
	}
}
void fwt(int n,int*a)
{
	for(int i=1;i<n;i<<=1)for(int j=0;j<n;j+=i+i)for(int k=0;k<i;k++)
	{
		int x=a[j+k],y=a[j+k+i];
		a[j+k]=(x+y)%P;a[j+k+i]=(x-y+P)%P;
	}
}
void ifwt(int n,int*a)
{
	for(int i=1;i<n;i<<=1)for(int j=0;j<n;j+=i+i)for(int k=0;k<i;k++)
	{
		int x=a[j+k],y=a[j+k+i];
		a[j+k]=1ll*(x+y)*iv2%P;a[j+k+i]=1ll*(x-y+P)*iv2%P;
	}
}
inline int gtf(int x,int k)
{
	int l=1;while(l<=mx)l<<=1;
	for(int i=0;i<l;i++)b[i]=0;
	for(int i=x;i<=mx;i+=x)b[i]=c[i];fwt(l,b);
	for(int i=0;i<l;i++)b[i]=pw(b[i],k);ifwt(l,b);
	return b[s];
} 
inline int sol(int x,int k)
{
	if(k==1)return s%x?0:c[s]; 
	if(k==2)
	{
		int res=0;
		for(int i=x,j;i<=mx;i+=x)if((j=s^i)%x==0)res=(res+1ll*c[i]*c[j])%P;
		return 1ll*res*iv2%P;
	}
	int tt=0;for(int i=x;i<=mx;i+=x)tt+=c[i];
	if(k==3)
	{
		int res=0;
		if(x<=sq)res=gtf(x,3);
		else
		{
			for(int i=x;i<=mx;i+=x)
			{
				num[0]=(num[0]+1ll*c[i]*c[i])%P;
				for(int j=i+x;j<=mx;j+=x)num[i^j]=(num[i^j]+2ll*c[i]*c[j])%P;
			}
			for(int i=x;i<=mx;i+=x)res=(res+1ll*c[i]*num[s^i])%P;
			for(int i=x;i<=mx;i+=x)for(int j=i;j<=mx;j+=x)num[i^j]=0;
		}
		int t=s%x?0:c[s];res=(res+P-t)%P;
		res=(res+P-3ll*t*(tt-1)%P)%P;return 1ll*res*iv6%P;
	}
	int res=0;
	if(x<=sq)res=gtf(x,4);
	else
	{
		for(int i=x;i<=mx;i+=x)
		{
			num[0]=(num[0]+1ll*c[i]*c[i])%P;
			for(int j=i+x;j<=mx;j+=x)num[i^j]=(num[i^j]+2ll*c[i]*c[j])%P;
		}
		for(int i=x;i<=mx;i+=x)
		{
			res=(res+1ll*c[i]*c[i]%P*num[s])%P;
			for(int j=i+x;j<=mx;j+=x)res=(res+2ll*c[i]*c[j]%P*num[s^i^j])%P;
		}
		for(int i=x;i<=mx;i+=x)for(int j=i;j<=mx;j+=x)num[i^j]=0;
	}
	int t=sol(x,2);res=(res-8ll*t%P+P)%P;
	res=(res-12ll*t%P*(tt-2)%P+P)%P;
	return 1ll*res*iv6%P*iv2%P*iv2%P;
}
int main()
{
	n=rd();k=rd();s=rd();mx=0;
	for(int i=1,x;i<=n;i++)x=rd(),c[x]++,mx=max(mx,x);
	sq=sqrt(mx)+1;init(mx);
	for(int i=1;i<=mx;i++)ans=(ans+1ll*phi[i]*sol(i,k))%P;
	printf("%d\n",ans);return 0;
}