[bzoj3462]DZY Loves Math II (美妙数学+背包dp)

Description

Input

第一行，两个正整数 S 和 q，q 表示询问数量。
接下来 q 行，每行一个正整数 n。

Output

输出共 q 行，分别为每个询问的答案。

Sample Input

30 3
9
29
1000000000000000000

Sample Output

0
9
450000036

HINT

感谢the Loser协助更正数据

对于100%的数据，2<=S<=2*10^6,1<=n<=10^18,1<=q<=10^5

这个题面让人很费解啊

其实题意还是挺简洁的

首先对S分解质因数

如果有相同的因数出现了多次，那么$lcm(p_1,p_2,p_3...p_k)=S$一定不能被满足

此时直接特判输出Q个0即可

(这10分这么好拿还想什么正解hhh)

接下来要做的，是取一定数量的每个$p_i$，使他们的和为$n$

假设$n=\sum{p_i*c_i}$,即$p_i$对应取$c_i$个

由$p_i$是S的因数，可得$p_i*c_i$一定可以表示成$X*S+Y*p_i$

将$p_i$除过去，得到$c_i=X*\frac{S}{p_i}+Y$

那么就可以把$c_i$分成+号前后两部分，不同的$X$和不同的$Y$都会导致方案不同

设前半部分为$a_i$,后半部分为$b_i$

将$c_i\ mod\ \frac{S}{p_i}$得到后半部分，这部分的方案数用多重背包解决

则背包大小不超过$k*S$(每个物品不超过$\frac{S}{p_i}$),

之后我们考虑$a_i$部分，分配每一个$X$等价于将$\frac{S}{p_i}$个物品放到k个盒子内(可空)，

利用隔板法得到方案数为$C_{\frac{S}{p_i}+k-1}^{k-1}$

直接打表求k范围内的阶乘逆元，暴力求排列再$*(m-1)$的阶乘逆元即可

$a_i\ b_i$的贡献是相对独立的，所以可以直接相乘

但这样可能包含了几倍的S，

而通过枚举一个倍数m( $p_1*b_1+p_2*b_2+...+p_k*b_k=n-m*S$ )即可得到结果

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cmath>

#include<vector>

using namespace std;

typedef long long ll;

const int N=;

const ll mod=1e9+;

int S,Q,tot=,sumf;

int fact[];

int sz,f[],g[],mu[],pr[];

bool v[];

ll n,side,inv[],fac[];

void dp()

{

    f[]=;

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

    {

        for(int j=;j<fact[i];j++)

        {

            ll tmp=;

            for(int k=j;k<=side;k+=fact[i])

            {

                tmp=(f[k]+tmp)%mod;

                if(k>=S)tmp=(tmp-f[k-S])%mod;

                g[k]=tmp;

            }

        }

        for(ll j=;j<=side;j++)f[j]=g[j];

    }

}

ll qpow(ll a,ll b)

{

    ll res=;

    for( ;b;b>>=,a=a*a%mod)

        if(b&)res=res*a%mod;

    return res;

}

ll C(ll x,ll y)

{

    ll res=;

    for(ll i=x;i>=x-y+;i--)res=res%mod*(i%mod)%mod;

    res=res%mod*(inv[y]%mod)%mod;

    return res;

}

void prime()

{

    mu[]=;int num=;

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

    {

        if(!v[i])pr[++num]=i,mu[i]=-;

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

        {

            if(i*pr[j]>S)break;

            v[i*pr[j]]=;

            if(i%pr[j])mu[i*pr[j]]=-mu[i];

            else

            {

                mu[i*pr[j]]=;

                break;

            }

        }

    }

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

        if(S%pr[i]==)fact[++sz]=pr[i],sumf+=pr[i];

}

int main()

{

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

    prime();

    if(!mu[S])

    {

        while(Q--)puts("");

        return ;

    }

    side=S*sz;

    inv[]=fac[]=;

    for(ll i=;i<=sz;i++)

        fac[i]=fac[i-]*i%mod;

    inv[sz]=qpow(fac[sz],mod-);

    for(int i=sz-;i;i--)

        inv[i]=inv[i+]*(i+)%mod;

    dp();

    while(Q--)

    {

        scanf("%lld",&n);

        if(n<sumf)

        {

            puts("");

            continue ;

        }

        n-=sumf;

        ll tm=n/S,ans=;

        for(ll i=;i<=sz;i++)

        {

            if(n-i*S<)break;

            ll now=i*S+n%S;

            if(now>side)continue;

            ans=(ans+(ll)f[now]*C(tm-i+sz-,sz-))%mod;

        }

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

    }

    return ;

}

巴特西