题解 P4495 【[HAOI2018]奇怪的背包】

Bruteforces · 2018-07-09 14:33:26 · 题解

题解

我们首先考虑 n=1 的情况，通过打表可以发现，对于体积为 v 的物品，在可以取无限次的条件下，能够取到的体积对 P 取膜的值可以为

所以我们可以把这个物品的体积看做 gcd(v,P)，这对答案不会有任何影响。

由此我们得到启发，O(\sqrt{P}) 预处理出 P 的每个约数，存储每个约数出现的次数。由于同一个约数多次选取对答案没有任何影响，容易得出，如果 P 的一个约数出现次数为 x，则有 2^x-1 种方案选取这个约数。

继续打表我们又可以发现，如果选取了 P 的两个约数 a_{1},a_{2}，能够取到的值膜 P 的值可以为

我们可以口胡证明，当选取约数个数大于 2 时，上式依然成立。

由此我们可以写出DP方程，设 F[i][j] 表示选到 P 的第 i 个约数，选出的数的 gcd 值为 P 的第 j 个约数的方案数，则转移方程为：

其中 a[i] 表示 P 的第 i 个约数，s[i] 表示第 i 个约数的出现次数。

该部分时间复杂度为 O(M^2logM)，空间复杂度为 O(M^2) 或 O(2M) （滚动数组），其中 M 为 P 的约数个数。

这个时候，对于每一个询问 w_{i}，我们容易得出答案就是

但是询问数量可以达到 10^6 ，M 最大可以达到 10^3 以上，O(qM) 的暴力统计依然会TLE。

事实上我们可以发现，如果一个数既是 P 的约数，又是 w_{i} 的约数，那么它一定是 gcd(P,w_{i}) 的约数，因此我们只需要统计

而这可以在DP之后就预处理出来：

因此我们可以 O(1) 回答询问，这样总复杂度就是 O(\sqrt{P}+M^2logM+q)，这道题就可以AC啦

代码如下：

#include<bits/stdc++.h>
using namespace std;

const int N=1000010,M=10050,mod=1000000007;
int n,q,P,v[N],num[M],tot[M],cnt=0,f[2][M],g[M],now=0,sum[N];

inline void init(){
    sum[1]=2;
    for(register int i=2;i<=n;i++)sum[i]=sum[i-1]*2%mod;
    for(register int i=1;i<=n;i++)sum[i]=(sum[i]+mod-1)%mod;

    for(register int i=1;i<=sqrt(P);i++)if(P%i==0)num[++cnt]=i;
    for(register int i=cnt;i>1;i--)if(P/num[i]!=num[i])num[++cnt]=P/num[i];
    for(register int i=1;i<=n;i++){
        int pos=lower_bound(num+1,num+cnt+1,v[i])-num;
        tot[pos]++;
    }

    for(register int i=1;i<=cnt;i++)if(tot[i]){
        now^=1;
        for(register int j=1;j<=cnt;j++)f[now][j]=f[now^1][j];
        for(register int j=1;j<=cnt;j++)if(f[now^1][j]){
            int nxt=__gcd(num[j],num[i]);
            int pos=lower_bound(num+1,num+cnt+1,nxt)-num;
            (f[now][pos]+=1LL*f[now^1][j]*sum[tot[i]]%mod)%=mod;
        }
        (f[now][i]+=sum[tot[i]])%=mod;
    }
    for(register int i=1;i<=cnt;i++){
        for(register int j=1;j<=i;j++)if(num[i]%num[j]==0){
            (g[i]+=f[now][j])%=mod;
        }
    }
}

int main(){
    scanf("%d%d%d",&n,&q,&P);
    for(register int i=1;i<=n;i++)scanf("%d",&v[i]),v[i]=__gcd(v[i],P);
    init();
    for(register int i=1;i<=q;i++){
        int x,ans=0;scanf("%d",&x);x=__gcd(x,P);
        int pos=lower_bound(num+1,num+cnt+1,x)-num;
        printf("%d\n",g[pos]);
    }
    return 0;
}