【BZOJ5302】奇怪的背包（HAOI2018）-裴蜀定理+DP

测试地址：奇怪的背包
做法：本题需要用到裴蜀定理+DP。
首先考虑一件物品 $a$ ，我们发现 $a x \mod P$ 实际上相当于 $a x - P y$ ，根据裴蜀定理，我们可以通过这种形式配出所有是 $gcd (a, P)$ 倍数的数。扩展到多件物品也相同，我们可以得到所有是这些物品和 $P$ 的 $gcd$ 的倍数的数。因为任何数和 $P$ 的 $gcd$ 肯定只能是 $P$ 的因数，而我们打表发现在 $10^{9}$ 之内拥有最多因数的数因数个数也只是在 $10^{3}$ 这个数量级，所以我们考虑 $O (\sqrt{P})$ 找到 $P$ 的所有因数，设因数的数量为 $f$ ，那么我们可以把原来每件物品的体积 $a$ 变成 $gcd (a, P)$ ，也就是 $P$ 的因数之一，然后就在这些数里面取。
对于每个询问 $w$ ，实际上就是问，有多少种物品组合使得它们和 $P$ 的 $gcd$ 是 $w$ 的因数，显然我们可以把 $w$ 变成 $gcd (w, P)$ ，这对答案没有任何影响，那么我们现在就是要求询问 $P$ 的每种因数的答案。
我们可以先考虑求出有多少种物品组合使得它们和 $P$ 的 $gcd$ 是 $i$ ，设 $d p (i, j)$ 为在前 $i$ 种因数中取， $gcd$ 为第 $j$ 种因数的方案数，这显然就能 $O (f^{2})$ 转移了，求出之后再 $O (f^{2})$ 求出每种询问的答案，即可 $O (1)$ 回答每个询问。
这题在洛谷上时限卡得有点紧，可以不用map之类的东西尽量就不要用，详见代码。
我傻逼的地方：先是数组开小，然后是边界写挂，接着是 $2$ 的次幂没处理够（原先我是想处理完 $2$ 的次幂再在DP中用的，挂了之后就换了一种写法，即直接处理每种数有多少种取的方式），我怎么这么菜啊……
以下是本人代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1000000007;
int n,q,tot=0,d[40010];
ll P,fac[40010],num[40010]={0},dp[2][40010]={0},ans[40010]={0};

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

int find(ll a)
{
    if (a*a<=P) return d[a];
    else return d[P/a]+1;
}

int main()
{
    scanf("%d%d%lld",&n,&q,&P);
    for(ll i=1;i*i<=P;i++)
        if (P%i==0)
        {
            fac[++tot]=i;
            d[i]=tot;
            if (i*i!=P) fac[++tot]=P/i;
        }

    for(int i=1;i<=n;i++)
    {
        ll x;
        scanf("%lld",&x);
        x=find(gcd(x,P));
        if (!num[x]) num[x]=2;
        else num[x]=(num[x]<<1)%mod;
    }

    int now=0,past=1;
    dp[past][find(P)]=1;
    for(int i=1;i<=tot;i++)
    {
        memset(dp[now],0,sizeof(dp[now]));
        if (!num[i]) num[i]=1;
        for(int j=1;j<=tot;j++)
        {
            int x=find(gcd(fac[j],fac[i]));
            dp[now][j]=(dp[now][j]+dp[past][j])%mod;
            dp[now][x]=((dp[now][x]+dp[past][j]*(num[i]-1))%mod+mod)%mod;
        }
        swap(now,past);
    }
    for(int i=1;i<=tot;i++)
        for(int j=1;j<=tot;j++)
            if (fac[i]%fac[j]==0) ans[i]=(ans[i]+dp[past][j])%mod;

    for(int i=1;i<=q;i++)
    {
        ll x;
        scanf("%lld",&x);
        x=gcd(x,P);
        if (x!=P) printf("%lld
",ans[find(x)]);
        else printf("%lld
",(ans[find(x)]-1+mod)%mod);
    }

    return 0;
}