bzoj 5019 遗失的答案

Posted on | Edited on | Views:

状压 $dp$ + $FWT$ .

若将每个数分解质因数,则 $\rm gcd,lcm$ 的限制等价于给出了每个质因子次数的 $\min,\max$ .

注意到 $n$ 的不同质因子个数 $\omega(n)\le 8$ ,比较少.

用一个 $16$ 位的二进制数 $S$ 表示各个质因子的 $\min,\max$ 是否被取到.

只有那些既是 $\rm gcd$ 倍数,又是 $\rm lcm$ 约数的数才有用,把它们全部爆搜出来,记这样的数共有 $m​$ 个.

记 $f(i,S)​$ 表示考虑了第 $1\sim i​$ 个数,是否被取到的状态为 $S​$ 的方案数.

记 $g(i,S)$ 表示考虑了第 $i\sim m$ 个数,是否被取到的状态为 $S$ 的方案数.

那么强制要求选第 $i$ 个数时,就把 $f(i-1)$ 和 $g(i+1)$ 用 $FWT​$ 做个或卷积.

将那些与第 $i$ 个数的状态 $S_i$ 或起来后为全集 $U$ 的位置上的值加起来,就是答案.

$m$ 并不会太大,可以将每次询问的答案记忆化下来,时间复杂度 $O(Q+m\cdot 4^{\omega(n)} \omega(n))$ .

实测发现 $m< 800$ . 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
//%std
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int P=1e9+7;
int add(int a,int b)
{
	return (a+b>=P)?(a+b-P):(a+b);
}
void inc(int &a,int b)
{
	a=add(a,b);
}
int mul(int a,int b)
{
	return 1LL * a * b % P;
}
void FWT(int *a,int n)
{
	for(int l=2;l<=n;l<<=1)
	{
		int m=l>>1;
		for(int *p=a;p!=a+n;p+=l)
			for(int i=0;i<m;++i)
				inc(p[i+m],p[i]);
	}
}
void IFWT(int *a,int n)
{
	for(int l=2;l<=n;l<<=1)
	{
		int m=l>>1;
		for(int *p=a;p!=a+n;p+=l)
			for(int i=0;i<m;++i)
				inc(p[i+m],P-p[i]);
	}
}
const int N=800,M=1<<16;
int tot=0,factor[N],l[N],r[N];
int n,Gcd,Lcm,m=0;
struct info
{
	int a,s;
	info(int a=0,int s=0):a(a),s(s) {}
	bool operator < (const info &rhs) const
	{
		return a<rhs.a;
	}
}p[N];
void dfs(int k,int prod,int st)
{
	if(k==tot)
	{
		++m;
		p[m].a=prod;
		p[m].s=st;
		return;
	}
	for(int i=1;i<=l[k];++i)
		prod*=factor[k];
	for(int i=l[k];i<=r[k];++i)
	{
		int t=st;
		if(i==l[k])
			t|=1<<k;
		if(i==r[k])
			t|=1<<(k+tot);
		dfs(k+1,prod,t);
		if(n/prod<factor[k])
			return;
		prod*=factor[k];
	}
}
int f[N][M],g[N][M],ans[N],tmp[M];
int main()
{
	n=read(),Gcd=read(),Lcm=read();
	if(Lcm%Gcd)
	{
		int Q=read();
		while(Q--)
			puts("0");
		return 0;
	}
	for(int i=2;i*i<=Lcm;++i)
		if(Lcm%i==0)
		{
			factor[tot]=i;
			while(Gcd%i==0)
				++l[tot],Gcd/=i;
			while(Lcm%i==0)
				++r[tot],Lcm/=i;
			tot++;
		}
	if(Lcm>1)
	{
		factor[tot]=Lcm;
		r[tot]=1;
		if(Gcd==Lcm)
			l[tot]=1;
		tot++;
	}
	int N=(1<<(2*tot));
	dfs(0,1,0);
	sort(p+1,p+m+1);
	f[0][0]=1;
	for(int i=0;i<m;++i)
		for(int S=0;S<N;++S)
			if(f[i][S])
			{
				inc(f[i+1][S],f[i][S]);
				inc(f[i+1][S|p[i+1].s],f[i][S]);
			}
	g[m+1][0]=1;
	for(int i=m+1;i>1;--i)
		for(int S=0;S<N;++S)
			if(g[i][S])
			{
				inc(g[i-1][S],g[i][S]);
				inc(g[i-1][S|p[i-1].s],g[i][S]);
			}
	memset(ans,-1,sizeof ans);
	int Q=read();
	while(Q--)
	{
		int c=read();
		int x=lower_bound(p+1,p+1+m,info(c,0))-p;
		if(c!=p[x].a)
		{
			puts("0");
			continue;
		}
		if(ans[x]!=-1)
		{
			printf("%d\n",ans[x]);
			continue;
		}
		ans[x]=0;
		FWT(f[x-1],N);
		FWT(g[x+1],N);
		for(int i=0;i<N;++i)
			tmp[i]=mul(f[x-1][i],g[x+1][i]);
		IFWT(tmp,N);
		IFWT(f[x-1],N);
		IFWT(g[x+1],N);
		for(int S=0;S<N;++S)
			if((S|p[x].s)==(N-1))
				inc(ans[x],tmp[S]);
		printf("%d\n",ans[x]);
	}
	return 0;
}