牛客练习赛41 F.简单数学题(按位维护素因子集+集合异或FWT)

题目

链接：https://ac.nowcoder.com/acm/contest/373/F

来源：牛客网

这冗长的题目我已经叙述不了了

思路来源

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40376257

题解

首先，考虑f(x)，由于一个素因子出现两次及以上莫比乌斯函数值就会为0

所以f(x)是其所有素因子只出现一次的乘积的值(不出现的话不是最大)

预处理2到71的素数表，这样每个f(x)值在每一个素数那里的上标不是0就是1

然后是g(x)，β(x)的设定是相加对2取余，

1+1==0 1+0==1 0+0==0 0+1==1 也就是只有0和1条件下的异或

把输入的a[i]压成f[a[i]]，用mask按位压其质因子的集合，

比如f[a[i]]=30=2*3*5，而第0个质数为2，第1个质数为3，第2个质数为5

所以其mask就是右起第0位、第1位、第2位为1，即7

那么输入一个a[i]，就把它处理成f[a[i]]，再令a[mask]++，代表对这个素数集贡献1

然后处理素数集即集合与集合之间的异或，要用快速沃尔什变换(FWT)

下午就是这里没有学明白，学了一下午……

https://blog.csdn.net/Code92007/article/details/88077549

粘一下自己的总结

可以处理集合与集合的卷积，

如a数组只有第15位(1111(2))为2，b数组只有第3位(0011(2))为3，

异或下的FWT就会令结果数组c[1111(2)异或0011(2)]即c[1100(2)]+=2*3，

即c数组的第12位+6

三个集合的卷积也等于三个先FWT之后的乘积再UFWT

证明不会证，反正两个的成立也不难推广到n个的成立叭

这样处理好三个集合的卷积之后，最后的答案数组d

注意到之前的按位压出来的i，

i有哪些位为1，代表当前枚举的值有这些位对应的素因子，

其所代表的值z是这些素因子的乘积

而z出现的次数是d[i]，增序扫一遍i，把z*d[i]统计到答案里即可

心得

①FWT要把容量扩成大于n的最小的2的幂次

这里由于2到71是20个素因子，所以是1<<20

②之前CF补过一个按集合维护哪些素因子出现过的线段树的题

这样的操作还是很常见的，按位压素因子，要多多练习啊

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=(1<<20)+10;
const int MOD=1e9+7;
const int inv2=(MOD+1)/2;//2*inv2===1 mod(MOD) 
int n,N;
int a[maxn],b[maxn],c[maxn];
ll ans;
bool ok[75];
int prime[25],cnt;
void init()
{
	for(int i=2;i<72;++i)
	{
		if(!ok[i])prime[cnt++]=i;
		for(int j=0;j<cnt;++j)
		{
			int k=i*prime[j];
			if(k>72)break;
			ok[k]=1;
			if(i%prime[j]==0)break;
		}
	}
	N=(1<<cnt);
} 
void FWT_xor(int *a,int opt)
{
    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=a[j+k],Y=a[i+j+k];
                a[j+k]=(X+Y)%MOD;a[i+j+k]=(X+MOD-Y)%MOD;
                if(opt==-1)a[j+k]=1ll*a[j+k]*inv2%MOD,a[i+j+k]=1ll*a[i+j+k]*inv2%MOD;
            }
}
void solve(int q[],int n)
{
	for(int i=0;i<n;++i)
	{
		ll v;
	    scanf("%lld",&v);
		int mask=0;
		for(int j=0;j<cnt;++j)
		{
			if(v%prime[j]==0)
			{
				mask|=(1<<j);
				while(v%prime[j]==0)
				v/=prime[j];
			}
		}
		q[mask]++; 
	}
	FWT_xor(q,1);
}
int main()
{
	init();
	scanf("%d",&n);
	solve(a,n);solve(b,n);solve(c,n); 
	for(int i=0;i<N;++i)
    a[i]=1LL*a[i]*b[i]%MOD*c[i]%MOD;
	FWT_xor(a,-1);
	for(int i=0;i<N;++i)
	{
		ll z=1;
		for(int j=0;j<cnt;++j)
		{
			if(i>>j&1)z*=prime[j];
			if(z>=MOD)z%=MOD;
		}
		ans+=z*a[i]%MOD;
		if(ans>=MOD)ans%=MOD;
	}
	printf("%lld\n",ans);
	return 0;
}