[HAOI2018] 奇怪的背包

背包的参数 (P) 表示背包的重量是物品总体积对 (P) 取模的结果。给定 (n) 种物品，第 (i) 种的体积占用为 (V_i)，每种物品有无限个。进行 (q) 次询问，每次询问给定重量 (w_i)，问有多少种选择物品种类的方案（显然一共有 (2^n) 种），使得被选择的这些物品每种放入若干个后能使得背包的总重量是 (w_i)。(n,q leq 10^6)

Solution

设当前选择的物品的体积分别是 (a_1,a_2,dots,a_k)，则可以凑出 (w_i) 的条件是 (gcd(P,a_1,a_2,dots,a_k)|w_i)

一个显然的暴力是，设 (f[i][j]) 表示考虑前 (i) 个物品，当前物品集合与 (P) 的 (gcd) 为 (j)，转移时考虑选或不选，暴力主动转移即可，复杂度 (O(nP^{1/3}))

考虑到 ((v_i,P)) 相同的这些 (v_i) 没有本质区别，我们可以将 ((v_i,P)) 相同的都压在一起，假设有 (t) 个那么贡献方案数就是 (2^t-1)，时间复杂度 (O(nlog V + P^{2/3}))

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1000005;
const int M = 5005;
const int mod = 1e+9 + 7;
int n,p,q,v[N],w[N],f[M][M],fac[N],pw[N],c[N],top,ans[M];

signed main() {
    ios::sync_with_stdio(false);
    cin>>n>>q>>p;
    for(int i=1;i<=n;i++) cin>>v[i];
    for(int i=1;i<=q;i++) cin>>w[i];
    for(int i=1;i*i<p;i++) if(p%i==0) fac[++top]=i;
    for(int i=sqrt(p);i;--i) if(p%i==0) fac[++top]=p/i;
    pw[0]=1;
    for(int i=1;i<=n;i++) pw[i]=pw[i-1]*2%mod;
    for(int i=1;i<=n;i++) {
        int tmp=__gcd(v[i],p);
        c[lower_bound(fac+1,fac+top+1,tmp)-fac]++;
    }
    f[0][top]=1;
    for(int i=1;i<=top;i++) {
        for(int j=1;j<=top;j++) {
            (f[i][j]+=f[i-1][j])%=mod;
            (f[i][lower_bound(fac+1,fac+top+1,__gcd(fac[i],fac[j]))-fac]+=f[i-1][j]*(pw[c[i]]-1))%=mod;
        }
    }
    for(int i=1;i<=top;i++) {
        for(int j=1;j<=i;j++) {
            if(fac[i]%fac[j]==0) (ans[i]+=f[top][j])%=mod;
        }
    }
    for(int i=1;i<=q;i++) {
        w[i]=__gcd(w[i],p);
        cout<<ans[lower_bound(fac+1,fac+top+1,w[i])-fac]<<endl;
    }
}