C++11(clang++ 3.9) 解法, 执行用时: 596ms, 内存消耗: 24712K, 提交时间: 2019-03-11 17:07:14

#include<cstdio>
#define mo 1000000007
#define chg(a,i) (a^=1<<i)
using namespace std;
using LL=long long;

const int pm[20]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71};

int a[1<<20],b[1<<20],c[1<<20],s,ans[1<<20],res,n,f[1<<20];

void FWT_xor(int *a, int n, int o=1)
{
	int x,y;
	for(int i=1;i<n;i<<=1)
		for(int j=0;j<n;j+=i<<1)
			for(int k=0;k<i;k++)
			{
				x=a[j+k],y=a[i+j+k];
				a[j+k]=(x+y)%mo,a[i+j+k]=(x-y+mo)%mo;
				if(o==-1)
					a[j+k]=(LL)a[j+k]*(mo+1)/2%mo,a[i+j+k]=(LL)a[i+j+k]*(mo+1)/2%mo;
			}
}

void init(int *a)
{
	LL x;
	for(int i=1,y,cnt;i<=n;i++)
	{
		scanf("%lld",&x);
        y=0;
		for(int j=0;j<20;j++)
		{
			cnt=0;
			while(x%pm[j]==0)
				x/=pm[j],cnt++;
			if(cnt)
				chg(y,j);
		}
		a[y]++;
	}
}

int main()
{
	scanf("%d",&n);
	init(a),init(b),init(c);
	FWT_xor(a,1<<20),FWT_xor(b,1<<20),FWT_xor(c,1<<20);
	for(int i=0;i<1<<20;i++)
		ans[i]=(LL)a[i]*b[i]%mo*c[i]%mo;
	FWT_xor(ans,1<<20,-1);
	f[0]=1;
	for(int i=1;i<1<<20;i++)
		f[i]=(LL)f[i-(i&-i)]*pm[__builtin_ctz(i)]%mo;
	for(int i=0;i<1<<20;i++)
		res=(res+(LL)ans[i]*f[i]%mo)%mo;
	printf("%d",res);
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 553ms, 内存消耗: 12096K, 提交时间: 2019-03-01 22:55:49

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1048576;
const int mod=1e9+7;
int p[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71};
int n,t[N],a[N],ans;
void fwt(int *P,int op){
	for(int i=1;i<N;i<<=1)
		for(int p=i<<1,j=0;j<N;j+=p)
			for(int k=0;k<i;++k){
				int x=P[j+k],y=P[j+k+i];
				P[j+k]=1ll*op*(x+y)%mod;P[j+k+i]=1ll*op*(x-y+mod)%mod;
			}
}
int main(){
	scanf("%d",&n);long long x;
	for(int i=0;i<N;++i)a[i]=1;
	for(int tt=0;tt<3;++tt){
		for(int i=0;i<N;++i)t[i]=0;
		for(int i=1;i<=n;++i){
			long long x=0;int s=0;scanf("%lld",&x);
			for(int j=0;j<20;++j)if(x%p[j]==0)s|=1<<j;
			++t[s];
		}
		fwt(t,1);
		for(int i=0;i<N;++i)a[i]=1ll*a[i]*t[i]%mod;
	}
	fwt(a,mod+1>>1);
	for(int i=0;i<N;++i){
		int mul=1;
		for(int j=0;j<20;++j)if(i>>j&1)mul=1ll*mul*p[j]%mod;
		ans=(ans+1ll*a[i]*mul)%mod;
	}
	printf("%d\n",ans);return 0;
}