P4495 [HAOI2018]奇怪的背包

题目描述

小\(C\)非常擅长背包问题，他有一个奇怪的背包，这个背包有一个参数\(P\)，当他 向这个背包内放入若干个物品后，背包的重量是物品总体积对\(P\)取模后的结果． 现在小\(C\)有\(n\)种体积不同的物品，第\(i\)种占用体积为\(V_i\)，每种物品都有无限个． 他会进行\(q\)次询问，每次询问给出重量\(w_i\)，你需要回答有多少种放入物品的方案，能将一个初始为空的背包的重量变为\(w_i\)．注意，两种方案被认为是不同的， 当且仅当放入物品的种类不同，而与每种物品放入的个数无关．不难发现总的方案数为\(2^n\). 由于答案可能很大，你只需要输出答案对\(1e9+7\)取模的结果．

输入输出格式

输入格式

第一行三个整数\(n,q,P\)，含义见问题描述. 接下来一行\(n\)个整数表示\(V_i\). 接下来一行\(q\)个整数表示\(w_i\).

输出格式：

输出\(q\)行，每行一个整数表示答案．

说明

对于所有数据，有\(1\le n,q\le 10^6,3 \le P \le 10^9,0 < V_i,w_i < P\),保证\(V_i\)两两不同。

是什么限制了我做题的想象力。。

我们要求

有多少个解，换成方程，即

有裴蜀定理可以猜到，有解的要求是\(gcd(x_1,x_2,\dots,x_n,p)|w_i\)

于是我们可以做\(DP\)，令\(dp_{i,j}\)表示前\(i\)个数选择的数的\(gcd\)和\(p\)做\(gcd\)后的结果为\(j\)

发现这样的状态是\(O(nd(p))\)的，\(d(p)\)表示\(p\)的约数个数

我们可以把\(V_i\)与\(p\)的\(gcd\)相同的放在一起做，这样状态就优化到了\(O(d^2(p))\)了

转移的时候要求\(gcd\)，那么\(dp\)的总复杂度就是\(O(d^2(p)\log p)\)的

最后对每个\(w_i\)统计答案是\(\sum_{i|w_i}dp_{n,i}\)，不可以暴力统计，注意到是可以实现预处理的。

总复杂度\(O(\sqrt p+d^2(p)\log p+n\log p+q)\)的

Code:

#include <cstdio>

#include <algorithm>

#define ll long long

const int N=1e6+10;

const int M=2010;

const ll mod=1e9+7;

int n_,n,q,p,v[N],siz[N],cnt;

ll dp[M][M],f[M],d[M],po[N];

int gcd(int a,int b){return b?gcd(b,a%b):a;}

int Find(int x){return std::lower_bound(d+1,d+1+cnt,x)-d;}

int main()

{

    scanf("%d%d%d",&n_,&q,&p);

    po[0]=1;

    for(int i=1;i<=n_;i++)

    {

        scanf("%d",v+i);

        v[i]=gcd(v[i],p);

        po[i]=(po[i-1]<<1ll)%mod;

    }

    std::sort(v+1,v+1+n_);

    for(int i=1;i<=n_;i++)

    {

        if(v[i]==v[n])

            ++siz[n];

        else

            v[++n]=v[i],siz[n]=1;

    }

    for(int i=1;i*i<=p;i++)

        if(p%i==0)

            d[++cnt]=p/i,d[++cnt]=i;

    std::sort(d+1,d+1+cnt);

    cnt=std::unique(d+1,d+1+cnt)-d-1;

    for(int i=0;i<n;i++)

    {

        for(int j=1;j<=cnt;j++)

        {

            int pos=Find(gcd(v[i+1],d[j]));

            (dp[i+1][pos]+=dp[i][j]*(po[siz[i+1]]-1)%mod)%=mod;

            (dp[i+1][j]+=dp[i][j])%=mod;

        }

        (dp[i+1][Find(gcd(v[i+1],p))]+=po[siz[i+1]]-1)%=mod;

    }

    for(int i=1;i<=cnt;i++)

        for(int j=1;j<=i;j++)

            if(d[i]%d[j]==0)

                (f[i]+=dp[n][j])%=mod;

    for(int w,i=1;i<=q;i++)

    {

        scanf("%d",&w);

        printf("%lld\n",f[Find(gcd(w,p))]);

    }

    return 0;

}

2018.10.31