题目
题目描述
小C非常擅长背包问题，他有一个奇怪的背包，这个背包有一个参数 $P$ ，当他向这个背包内放入若干个物品后，背包的重量是物品总体积对 $P$ 取模后的结果．
现在小C有 $n$ 种体积不同的物品，第 $i$ 种占用体积为 $V_i$ ，每种物品都有无限个．他会进行 $q$ 次询问，每次询问给出重量 $w_i$ ，你需要回答有多少种放入物品的方案，能将一个初始为空的背包的重量变为 $w_i$ ．注意，两种方案被认为是不同的，当且仅当放入物品的种类不同，而与每种物品放入的个数无关．不难发现总的方案数为 $2^n$ .
由于答案可能很大，你只需要输出答案对 $10^9 + 7$ 取模的结果．
输入格式
第一行三个整数 $n, q, P$ ，含义见问题描述.
接下来一行 $n$n 个整数表示 $V_i$ .
接下来一行 $q$q 个整数表示 $w_i$ .
输出格式
输出 $q$ 行，每行一个整数表示答案．
样例
样例输入
3 3 6
1 3 4
5 2 3
样例输出
5
6
6
样例解释
对于第一个询问 $5$ ，选择$ {1}, {1, 3}, {1, 4}, {3, 4}, {1, 3, 4}$ 都是合法的方案．
数据范围与提示
对于所有数据，有 $1 \le n, q \le 10^6, 3 \le P \le 10^9, 0 < V_i, w_i < P$ .
保证 $V_i$ 两两不同.
题解
首先考虑对于$n=1$的情况，有$kv\equiv w(\mod P)$，即$kv+k_1P=w$，由贝祖定理得，$\gcd(k,P)\vert w$
所以可以用$\gcd(V_i,P)$代替$V_i$了，考虑两个数的情况，即$aV_x+bV_y=w$，还是贝祖定理，$\gcd(V_x,V_y)\vert w$，进而能推广到更多数的情况：$\gcd(V_{a_1},V_{a_2},V_{a_3},…,V_{a_k})\vert w$
这样似乎就可以$dp$了，设$f_{i,j}$表示从$P$前$i$个约数中选择，现在的$\gcd$为第$j$个约数的方案数，设$d_i$表示$P$的第$i$个约数，$t_i$表示第$i$个约数的出现次数（指$V$数组中），则第$i$个约数能贡献的方案数为$2^{t_i}-1$种，有方程
$f_{i,j}=f_{i-1,j}+(1+\sum_{\gcd(d_i,d_k)==d_j}f_{i-1,k})\times (2^{t_i}-1)$
因为有一个$P$很大的时候约数个数不会超过$P^{\frac{1}{3}}$的结论，所以这个式子可以暴力$O(N^2)$转移（$N$为约数个数）
现在要回答询问，显然能产生贡献的为$w$的约数（即$\gcd(w,P)$的约数），处理一个类似前缀和的东西然后二分找约数位置即可
本地TLE但$OJ$上跑的还挺快emmmm
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<cmath>
# include<map>
# include<algorithm>
using namespace std;
const int N=2e3+5,MAX=1e6+5,mod=1e9+7;
int n,q,P,cnt;
int v[MAX],A[N],num[N],qwq[MAX],sum[N];
int f[N][N];
map<int,int> mp;
int read()
{
int x(0);
char ch=getchar();
for(;!isdigit(ch);ch=getchar());
for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
return x;
}
int look(int x)
{
int l=1,r=cnt,ans=cnt;
while(l<=r)
{
int mid(l+r>>1);
if(A[mid]<=x) ans=mid,l=mid+1;
else r=mid-1;
}
return ans;
}
int gcd(int a,int b) {return b?gcd(b,a%b):a;}
int main()
{
n=read(),q=read(),P=read(),qwq[0]=1;
for(int i=1;i<=n;++i)
v[i]=gcd(read(),P),qwq[i]=(qwq[i-1]<<1ll)%mod;
int N=sqrt(P);
for(int i=1;i<=N;++i)
if(P%i==0)
{
A[++cnt]=i;
if(i!=P/i) A[++cnt]=P/i;
}
sort(A+1,A+1+cnt),sort(v+1,v+1+n);
for(int i=1,L=1;i<=cnt;++i)
{
mp[A[i]]=i;
while(v[L]==A[i]&&L<=n) ++num[i],++L;
}
for(int i=1;i<=cnt;++i)
{
for(int j=1,x;j<=cnt;++j)
x=mp[gcd(A[i],A[j])],(f[i][x]+=f[i-1][j])%=mod;
for(int j=1;j<=cnt;++j)
f[i][j]=(1ll*f[i][j]*(qwq[num[i]]-1+mod)%mod+f[i-1][j])%mod;
(f[i][i]+=(qwq[num[i]]-1+mod)%mod)%=mod;
}
for(int i=1;i<=cnt;++i)
for(int j=1;j<=i;++j)
if(A[i]%A[j]==0) (sum[i]+=f[cnt][j])%=mod;
for(int i=1;i<=q;++i)
printf("%d\n",sum[look(gcd(read(),P))]);
return 0;
}
