bzoj3462: DZY Loves Math II

状态很差脑子不清醒了，柿子一直在推错。。。。

。。。

不难发现这个题实际上是一个完全背包

问题在于n太大了，相应的有质数的数量不会超过7个

假设要求sigema(1~plen)i pi*ci=n 的方案数

令xi=ci/(S*pi),yi=ci%(S/pi),注意yi<S/pi

则等价于sigema(1~plen)i S*xi+yi*pi=n

若令sigema(1~plen)i xi=m，则sigema(1~plen)yi*pi=n-m*S

n-m*S=sigema(1~plen)yi*pi<plen*S，可推出n/S-plen<m<=n/S

此时plen有用了，我们可以枚举m，那么对于x的方案用插板法得C(m+plen-1,plen-1),对于y直接背包plen*S，朴素的做法是O(plen*(plen*S)*S/pi)的，随便优化下就可以把S/pi去掉了，不过要稍微注意yi的限制。

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

using namespace std;

typedef long long LL;

const int _=1e2;

const int maxn=**1e6+_;

const LL mod=1e9+;

int plen,p[];

bool divi(int n)

{

    plen=;

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

        if(n%i==)

        {

            p[]+=i;p[++plen]=i;n/=i;

            if(n%i==)return false;

        }

    if(n!=)p[]+=n,p[++plen]=n;

    return true;

}

LL inv[];

void yu(){inv[]=;for(int i=;i<=plen;i++)inv[i]=inv[mod%i]*(mod-mod/i)%mod;}

LL C(LL n,LL m)

{

    LL ret=;

    for(int i=;i<=m;i++)

    {

        ret=ret*(n%mod)%mod*inv[i]%mod; n--;

    }

    return ret;

}

LL f[][maxn]; int now;

void DP(int S)

{

    int li=S*plen;

    now=,f[now][]=;

    for(int i=;i<=plen;i++)

    {

        now^=;

        for(int j=;j<li;j++)

        {

            f[now][j]=;

            if(j-p[i]>=)f[now][j]=(f[now][j]+f[now][j-p[i]])%mod;

            f[now][j]=(f[now][j]+f[now^][j])%mod;

            if(j>=S/p[i]*p[i])f[now][j]=(f[now][j]-f[now^][j-S/p[i]*p[i]]+mod)%mod;

        }

    }

}

int main()

{

    freopen("3.in","r",stdin);

    freopen("a.out","w",stdout);

    int S,Q;

    scanf("%d%d",&S,&Q);

    if(!divi(S)){while(Q--)puts("");return ;}

    yu();DP(S);

    while(Q--)

    {

        LL n;

        scanf("%lld",&n);n-=p[];

        if(n<){puts("");continue;}

        LL ans=;

        for(LL m=max(0LL,n/S-plen+);m<=n/S;m++)

        {

            ans=(ans+C(m+plen-,plen-)*f[now][n-m*S])%mod;

        }

        printf("%lld\n",ans);

    }

    return ;

}