小皮球在计算出答案之后，买了一堆皮肤，他心里很开心，但是一不小心，就忘记自己买了哪些皮肤了。==|||万
幸的是，他还记得他把所有皮肤按照1～N来编号，他买来的那些皮肤的编号（他至少买了一款皮肤），最大公约数
是G，最小公倍数是L。现在，有Q组询问，每组询问输入一个数字X，请你告诉小皮球，有多少种合法的购买方案中
，购买了皮肤X？因为答案太大了，所以你只需要输出答案mod1000000007即可。
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#include<cstdio>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
const int mod=1000000007;
const int inv=500000004;
bool vis[10010];
int prime[10010];
int cnt;
int G,L,Q;
int n,x;
int num;
int sum;
int mask;
int mx[10];
int pr[10];
int f[1<<16];
int g[1<<16];
int tmp[1<<16];
int p[1<<16];
int res[1<<16];
int pre[600][1<<16];
int suf[600][1<<16];
void find()
{
for(int i=2;i<=10000;i++)
{
if(!vis[i])
{
prime[++cnt]=i;
}
for(int j=1;j<=cnt&&prime[j]*i<=10000;j++)
{
vis[i*prime[j]]=1;
if(i%prime[j]==0)
{
break;
}
}
}
}
void FWT_OR(int *a,int len,int opt)
{
for(int k=2;k<=len;k<<=1)
{
int t=k>>1;
for(int i=0;i<len;i+=k)
{
for(int j=i;j<i+t;j++)
{
if(opt==1)
{
a[j+t]=(a[j+t]+a[j])%mod;
}
else
{
a[j+t]=(a[j+t]-a[j]+mod)%mod;
}
}
}
}
}
void FWT_AND(int *a,int len,int opt)
{
for(int k=2;k<=len;k<<=1)
{
int t=k>>1;
for(int i=0;i<len;i+=k)
{
for(int j=i;j<i+t;j++)
{
if(opt==1)
{
a[j]=(a[j]+a[j+t])%mod;
}
else
{
a[j]=(a[j]-a[j+t]+mod)%mod;
}
}
}
}
}
void take(int x)
{
for(int i=1;i<=cnt&&prime[i]*prime[i]<=x;i++)
{
if(x%prime[i]==0)
{
pr[++num]=prime[i];
while(x%prime[i]==0)
{
x/=prime[i];
mx[num]++;
}
}
}
if(x>1)
{
pr[++num]=x,mx[num]=1;
}
}
int quick(int x,int y)
{
int res=1;
while(y)
{
if(y&1)
{
res=1ll*res*x%mod;
}
y>>=1;
x=1ll*x*x%mod;
}
return res;
}
void dfs(int dep,int x,int S1,int S2)
{
if(dep>num)
{
res[S1|(S2<<num)]++;
return ;
}
for(int i=0;i<=mx[dep];i++)
{
dfs(dep+1,x,S1|((i==0)<<(dep-1)),S2|((i==mx[dep])<<(dep-1)));
if(1ll*x*pr[dep]>n)
{
return ;
}
x*=pr[dep];
}
}
void add(int &x,int y)
{
x+=y;
if(x>mod)
{
x-=mod;
}
}
int get(int x)
{
int S=0;
for(int i=1;i<=num;i++)
{
int ans=0;
while(x%pr[i]==0)
{
x/=pr[i],ans++;
}
if(!ans)
{
S|=1<<(i-1);
}
if(ans==mx[i])
{
S|=1<<(i-1+num);
}
}
return S;
}
int main()
{
scanf("%d%d%d%d",&n,&G,&L,&Q);
find();
if(L%G)
{
while(Q--)
{
puts("0");
}
return 0;
}
L/=G,n/=G;
take(L);
dfs(1,1,0,0);
mask=1<<(num+num);
for(int i=0;i<mask;i++)
{
if(res[i])
{
g[++sum]=i;
p[sum]=quick(2,res[i])-1;
}
}
f[0]=1,pre[0][0]=1;
for(int i=1;i<=sum;i++)
{
for(int j=0;j<mask;j++)
{
add(tmp[j|g[i]],1ll*f[j]*p[i]%mod);
}
for(int j=0;j<mask;j++)
{
add(f[j],tmp[j]),tmp[j]=0;
}
for(int j=0;j<mask;j++)
{
pre[i][j]=f[j];
}
}
memset(f,0,sizeof(f));
f[0]=1,suf[sum+1][0]=1;
for(int i=sum;i>=1;i--)
{
for(int j=0;j<mask;j++)
{
add(tmp[j|g[i]],1ll*f[j]*p[i]%mod);
}
for(int j=0;j<mask;j++)
{
add(f[j],tmp[j]),tmp[j]=0;
}
for(int j=0;j<mask;j++)
{
suf[i][j]=f[j];
}
}
for(int i=0;i<=sum;i++)
{
FWT_OR(pre[i],mask,1);
FWT_OR(suf[i+1],mask,1);
}
for(int i=0;i<sum;i++)
{
for(int j=0;j<mask;j++)
{
pre[i][j]=1ll*pre[i][j]*suf[i+2][j]%mod;
}
}
for(int i=0;i<sum;i++)
{
FWT_OR(pre[i],mask,-1);
FWT_AND(pre[i],mask,1);
}
while(Q--)
{
scanf("%d",&x);
if(x%G){puts("0");continue;}
x/=G;
if(L%x){puts("0");continue;}
if(x>n){puts("0");continue;}
int S=get(x);
int ans=0;
int y=lower_bound(g+1,g+1+sum,S)-g-1;
ans=pre[y][(mask-1)^S];
ans=1ll*ans*inv%mod*(p[y+1]+1)%mod;
printf("%d\n",ans);
}
}
BZOJ5019[Snoi2017]遗失的答案——FWT+状压DP
原文：https://www.cnblogs.com/Khada-Jhin/p/10736578.html