【BZOJ5019】[SNOI2017]遗失的答案（FWT，动态规划）
题面
题解
发现\(10^8\)最多分解为不超过\(8\)个本质不同质数的乘积。
而\(gcd\)和\(lcm\)分别就是每个质因子的最大次幂和最小次幂的乘积。
那么考虑一个状压\(dp\)，设\(f[S1][S2]\)表示最小/最大次幂是否被取到的方案数。
而能够被统计入答案的数一定是在\(gcd\)和\(lcm\)之间的数，并且是\(gcd\)的倍数，\(lcm\)的因数。
直接爆搜，这样的数不会太多。然后可以把他们归类，按照他们能够取到最大最小次幂归类，这样子的状态不会超过\(600\)。
然后考虑\(dp\)的转移，十分显然，现在的问题在于有一个必定选，这个如何考虑。
那么我们存下前缀后缀的\(dp\)结果，那么合并的答案显然是两者做或卷积，直接\(FWT\)实现即可。
那么考虑这个数的贡献，也就是全集异或上这个数最大最小次幂状态的超集。那么把预处理的前后或卷积再做一个超集和，这样子就是可以做到单次\(O(1)\)回答。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
#define ll long long
#define MOD 1000000007
#define inv2 500000004
void add(int &x,int y){x+=y;if(x>MOD)x-=MOD;}
inline int read()
{
int x=0;bool t=false;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
const int MP=10000;
int pri[MP+10],tot;
bool zs[MP+10];
void Pre(int n)
{
for(int i=2;i<=n;++i)
{
if(!zs[i])pri[++tot]=i;
for(int j=1;j<=tot&&i*pri[j]<=n;++j)
{
zs[i*pri[j]]=true;
if(i%pri[j]==0)break;
}
}
}
int n,G,L,Q,ans;
int p[50],mx[50],mn[50],num,qwq=1;
void fj(int x)
{
for(int i=1;i<=tot&&pri[i]*pri[i]<=x;++i)
if(x%pri[i]==0)
{
p[++num]=pri[i];
while(x%pri[i]==0)x/=pri[i],++mx[num];
}
if(x>1)p[++num]=x,mx[num]=1;
}
int cnt[1<<16];
void dfs(int x,int s,int S1,int S2)
{
if(x==num+1){cnt[S1|(S2<<num)]+=1;return;}
for(int i=0;i<=mx[x];++i)
{
dfs(x+1,s,S1|((i==0)<<(x-1)),S2|((i==mx[x])<<(x-1)));
if(1ll*s*p[x]>n)return;
s*=p[x];
}
}
int fpow(int a,int b)
{
int s=1;
while(b){if(b&1)s=1ll*s*a%MOD;a=1ll*a*a%MOD;b>>=1;}
return s;
}
int get(int x)
{
int S=0;
for(int i=1;i<=num;++i)
{
int cnt=0;
while(x%p[i]==0)x/=p[i],++cnt;
if(cnt==0)S|=1<<(i-1);
if(cnt==mx[i])S|=1<<(i-1+num);
}
return S;
}
int f[1<<16],tmp[1<<16],gnt[1<<16];
int zt[1<<16],T;
int pre[600][1<<16],suf[600][1<<16];
void FWT(int *a,int N,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)
if(opt==1)a[i+j+k]=(a[j+k]+a[i+j+k])%MOD;
else a[i+j+k]=(a[i+j+k]+MOD-a[j+k])%MOD;
}
void FWT_and(int *a,int N,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)
if(opt==1)a[j+k]=(a[j+k]+a[i+j+k])%MOD;
else a[j+k]=(a[j+k]+MOD-a[i+j+k])%MOD;
}
int main()
{
n=read();G=read();L=read();Q=read();Pre(10000);
if(L%G){while(Q--)puts("0");return 0;}
L/=G;n/=G;fj(L);dfs(1,1,0,0);int SS=1<<(num+num);
for(int i=0;i<SS;++i)
if(cnt[i])zt[++T]=i,gnt[T]=fpow(2,cnt[i])-1;
for(int i=1;i<=T;++i)cnt[i]=gnt[i];
f[0]=1;pre[0][0]=1;
for(int x=1;x<=T;++x)
{
int i=zt[x];
for(int j=0;j<SS;++j)
add(tmp[j|i],1ll*f[j]*cnt[x]%MOD);
for(int j=0;j<SS;++j)add(f[j],tmp[j]),tmp[j]=0;
for(int j=0;j<SS;++j)pre[x][j]=f[j];
}
memset(f,0,sizeof(f));
f[0]=1;suf[T+1][0]=1;
for(int x=T;x;--x)
{
int i=zt[x];
for(int j=0;j<SS;++j)
add(tmp[j|i],1ll*f[j]*cnt[x]%MOD);
for(int j=0;j<SS;++j)add(f[j],tmp[j]),tmp[j]=0;
for(int j=0;j<SS;++j)suf[x][j]=f[j];
}
for(int i=0;i<=T;++i)FWT(pre[i],SS,1);
for(int i=1;i<=T+1;++i)FWT(suf[i],SS,1);
for(int i=0;i<=T;++i)
for(int j=0;j<SS;++j)
pre[i][j]=1ll*pre[i][j]*suf[i+2][j]%MOD;
for(int i=0;i<=T;++i)FWT(pre[i],SS,-1),FWT_and(pre[i],SS,1);
while(Q--)
{
int x=read();
if(x%G){puts("0");continue;}x/=G;
if(L%x){puts("0");continue;}
if(x>n){puts("0");continue;}
int d=get(x),ans=0;
int p=lower_bound(&zt[1],&zt[T+1],d)-zt-1;
ans=pre[p][(SS-1)^d];
ans=1ll*ans*(cnt[p+1]+1)%MOD*inv2%MOD;
printf("%d\n",ans);
}
}