BZOJ1042 HAOI2008硬币购物（任意模数NTT+多项式求逆+生成函数/容斥原理+动态规划）

　　第一眼生成函数。四个等比数列形式的多项式相乘，可以化成四个分式。其中分母部分是固定的，可以多项式求逆预处理出来。而分子部分由于项数很少，询问时2^4算一下贡献就好了。这个思路比较直观。只是常数巨大，以及需要敲一发类似任意模数ntt的东西来避免爆精度。成功以这种做法拿下luogu倒数rank1，至于bzoj不指望能过了。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<iomanip>

using namespace std;

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

#define N 550000

#define T 100000

#define P1 998244353

#define P2 1004535809

int r[N],c1,c2,c3,c4,tot,d1,d2,d3,d4,s,t;

int a[N],b[N],c[N],e[][N];

long long f[N];

void inc(int &x,int P){x++;if (x>=P) x-=P;}

void dec(int &x,int P){x--;if (x<) x+=P;}

int ksm(int a,int k,int P)

{

    if (a==) return ;

    if (k==) return ;

    int tmp=ksm(a,k>>,P);

    if (k&) return 1ll*tmp*tmp%P*a%P;

    else return 1ll*tmp*tmp%P;

}

long long ksc(long long a,long long b,long long P)

{

    long long t=a*b-(long long)((long double)a*b/P+0.5)*P;

    return t<?t+P:t;

}

void DFT(int n,int *a,int p,int P)

{

    for (int i=;i<n;i++) if (i<r[i]) swap(a[i],a[r[i]]);

    for (register int i=;i<=n;i<<=)

    {

        int wn=ksm(p,(P-)/i,P);

        for (register int j=;j<n;j+=i)

        {

            int w=;

            for (register int k=j;k<j+(i>>);k++,w=1ll*w*wn%P)

            {

                int x=a[k],y=1ll*w*a[k+(i>>)]%P;

                a[k]=(x+y)%P,a[k+(i>>)]=(x-y+P)%P;

            }

        }

    }

}

void mul(int n,int *a,int *b,int P,int inv3)

{

    DFT(n,a,,P),DFT(n,b,,P);

    for (int i=;i<n;i++) a[i]=1ll*a[i]*(P+-1ll*a[i]*b[i]%P)%P;

    DFT(n,a,inv3,P);

    int inv=ksm(n,P-,P);

    for (int i=;i<n;i++) a[i]=1ll*a[i]*inv%P;

}

void solve(int P,int inv3,int op)

{

    memset(a,,sizeof(a));

    memset(b,,sizeof(b));

    memset(c,,sizeof(c));

    if (c1+c2+c3+c4<=T) inc(a[c1+c2+c3+c4],P);

    if (c1+c2+c3<=T) dec(a[c1+c2+c3],P);

    if (c1+c2+c4<=T) dec(a[c1+c2+c4],P);

    if (c4+c2+c3<=T) dec(a[c4+c2+c3],P);

    if (c1+c4+c3<=T) dec(a[c1+c4+c3],P);

    if (c1+c2<=T) inc(a[c1+c2],P);

    if (c1+c3<=T) inc(a[c1+c3],P);

    if (c1+c4<=T) inc(a[c1+c4],P);

    if (c2+c3<=T) inc(a[c2+c3],P);

    if (c4+c2<=T) inc(a[c4+c2],P);

    if (c3+c4<=T) inc(a[c3+c4],P);

    dec(a[c1],P);dec(a[c2],P);dec(a[c3],P);dec(a[c4],P);

    inc(a[],P);

    t=;b[]=;

    while (t<=T)

    {

        t<<=;

        for (int i=;i<t;i++) c[i]=a[i];

        for (int i=;i<(t<<);i++) r[i]=(r[i>>]>>)|(i&)*t;

        mul(t<<,b,c,P,inv3);

        for (int i=t;i<(t<<);i++) b[i]=;

    }

    memcpy(e[op],b,sizeof(e[op]));

}

void crt()

{

    long long P=1ll*P1*P2,inv1=ksm(P2%P1,P1-,P1),inv2=ksm(P1%P2,P2-,P2);

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

    f[i]=(ksc(1ll*e[][i]*P2%P,inv1,P)+ksc(1ll*e[][i]*P1%P,inv2,P))%P;

}

int main()

{

#ifndef ONLINE_JUDGE

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

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

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    c1=read(),c2=read(),c3=read(),c4=read(),tot=read();

    solve(P1,,);

    solve(P2,,);

    crt();

    while (tot--)

    {

        d1=read(),d2=read(),d3=read(),d4=read(),s=read();

        d1=min(1ll*s+,1ll*(d1+)*c1);

        d2=min(1ll*s+,1ll*(d2+)*c2);

        d3=min(1ll*s+,1ll*(d3+)*c3);

        d4=min(1ll*s+,1ll*(d4+)*c4);

        long long ans=f[s];

        if (d1+d2+d3+d4<=s) ans+=f[s-(d1+d2+d3+d4)];

        if (d1+d2+d3<=s) ans-=f[s-(d1+d2+d3)];

        if (d1+d2+d4<=s) ans-=f[s-(d1+d2+d4)];

        if (d4+d2+d3<=s) ans-=f[s-(d4+d2+d3)];

        if (d1+d4+d3<=s) ans-=f[s-(d1+d4+d3)];

        if (d1+d2<=s) ans+=f[s-(d1+d2)];

        if (d1+d3<=s) ans+=f[s-(d1+d3)];

        if (d1+d4<=s) ans+=f[s-(d1+d4)];

        if (d2+d3<=s) ans+=f[s-(d2+d3)];

        if (d4+d2<=s) ans+=f[s-(d4+d2)];

        if (d3+d4<=s) ans+=f[s-(d3+d4)];

        if (d1<=s) ans-=f[s-d1];

        if (d2<=s) ans-=f[s-d2];

        if (d3<=s) ans-=f[s-d3];

        if (d4<=s) ans-=f[s-d4];

        printf(LL,ans);

    }

    return ;

}

　　还有一种更优秀的做法。考虑如果硬币没有个数限制的话，就是一个完全背包。添加限制可以想到容斥。我们枚举有哪几种硬币超过了个数限制，就可以容斥斥斥容容容斥把多重背包转化成完全背包了。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<iomanip>

using namespace std;

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

#define N 100010

#define ll long long

int c[],t,d[],s;

ll f[N],ans;

int calc(int k,int x){if (k<x) return ;else return f[k-x];}

void dfs(int k,int sum,ll tot)

{

    if (tot>s) return;

    if (k==) {ans+=((sum&)?-:)*f[s-tot];return;}

    dfs(k+,sum+,tot+1ll*(d[k]+)*c[k]);

    dfs(k+,sum,tot);

}

int main()

{

#ifndef ONLINE_JUDGE

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

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

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    for (int i=;i<;i++) c[i]=read();

    t=read();

    f[]=;

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

        for (int j=c[i];j<=N-;j++)

        f[j]+=f[j-c[i]];

    while (t--)

    {

        for (int i=;i<;i++) d[i]=read();

        s=read();

        ans=;

        dfs(,,);

        printf(LL,ans);

    }

    return ;

}

　　仔细考虑一下会发现两个做法本质上其实是一样的。分子部分所乘的多项式就是一个容斥的过程，而求逆所得的结果就是完全背包。

巴特西

BZOJ1042 HAOI2008硬币购物（任意模数NTT+多项式求逆+生成函数/容斥原理+动态规划）

最新文章

热门文章