XXXIII.[HAOI2018]奇怪的背包
神题。
-
对于某个大小为\(v\)的物品，它所能表示出的位置的集合等于\(\gcd(v,P)\)所能表示的集合。
-
对于某些大小为\(v_1,\dots,v_k\)的物品，位置集合为\(\gcd\{v_1,\dots,v_k,P\}\)。
因此考虑DP。
我们找出所有\(P\)的约数，存入vector。（这个个数的级别设为\(L\)，则\(L\)最大只到\(768\)。）设\(P\)的第\(i\)个约数为\(p_i\)。
则对于所有的\(v_i\)，我们找出\(\gcd(P,v_i)\)。设新的\(v_i=\gcd(P,v_i)\)。
对于每个\(p_i\)，统计它在\(v_1,\dots,v_n\)中出现了多少次，设为\(s_i\)。
我们设\(f[i][j]\)表示：在\(P\)前\(i\)个约数中，选择一些数，使得他们的\(\gcd\)等于\(P\)的第\(j\)个约数的方案数。
则有
\(f[i][j]=f[i-1][j]+\Bigg(\small{\begin{cases}1(i=j)\\0(i\neq j)\end{cases}}+\sum\limits_{\gcd(p_k,p_i)=p_j}f[i-1][k]\Bigg)*(2^{s_i}-1)\)
释义：
首先，答案是可以从前一位继承来的。
然后，因为对于每个\(i\)，选任何数量的\(v_k=p_i\)的\(k\)都是等价的，因此共有\(2^{s_i}-1\)中选法；
当\(i=j\)时，可以之前一个数也不选，就选\(i\)一个数，因此要加上\(1\)。
然后，因为\(\gcd\)具有结合律和交换律，所有\(\gcd(p_k,p_i)=p_j\)的状态也是可继承的。
则\(f[n][j]\)的状态是最终状态。
对于每个\(w_i\)，答案为\(\sum\limits_{v_j|w_i}f[n][j]\)。这个可以通过一个\(L^2\)的预处理求出\(g[i]=\sum\limits_{v_j|v_i}f[n][j]\)算出。
复杂度\(O(\sqrt{P}+L^2\log L+q)\)。
代码：
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int n,m,p,s[1001000],f[2][1001000],g[1001000],two[1001000];
vector<int>v;
int main(){
scanf("%d%d%d",&n,&m,&p);
two[0]=1;
for(int i=1;i<=n;i++)two[i]=(two[i-1]<<1)%mod;
for(int i=0;i<=n;i++)two[i]=(two[i]-1+mod)%mod;
// for(int i=0;i<=n;i++)printf("%d ",two[i]);puts("");
for(int i=1;i*i<=p;i++){
if(p%i)continue;
v.push_back(i);
if(i*i!=p)v.push_back(p/i);
}
sort(v.begin(),v.end());
// for(auto i:v)printf("%d ",i);puts("");
for(int i=1,x;i<=n;i++)scanf("%d",&x),x=__gcd(x,p),s[lower_bound(v.begin(),v.end(),x)-v.begin()]++;
// for(int i=0;i<v.size();i++)printf("%d ",s[i]);puts("");puts("");
for(int i=0;i<v.size();i++){
for(int j=0;j<=i;j++)f[i&1][j]=0;
f[i&1][i]=1;
for(int j=0;j<i;j++){
int gcd=__gcd(v[i],v[j]);
gcd=lower_bound(v.begin(),v.end(),gcd)-v.begin();
(f[i&1][gcd]+=f[!(i&1)][j])%=mod;
}
for(int j=0;j<=i;j++)f[i&1][j]=(1ll*f[i&1][j]*two[s[i]]+f[!(i&1)][j])%mod;
// for(int j=0;j<=i;j++)printf("%d ",f[i&1][j]);puts("");
}
for(int i=0;i<v.size();i++)for(int j=0;j<=i;j++)if(!(v[i]%v[j]))(g[i]+=f[n&1][j])%=mod;
for(int i=1,w;i<=m;i++)scanf("%d",&w),w=__gcd(w,p),printf("%d\n",g[lower_bound(v.begin(),v.end(),w)-v.begin()]);
return 0;
}