bzoj 5019: [Snoi2017]遗失的答案【dp+FWT】

满足GL的组合一定包含GL每个质因数最大次幂个最小次幂，并且能做限制这些数不会超过600个

然后质因数最多8个，所以可以状压f[s1][s2]为选s1集合满足最大限制选s2集合满足最小限制

dfs一下预处理出质因数只选一个质因数的初始状态

然后dp，做一个前缀一个后缀，设f[i][j]为前i个质因数选成集合j的方案数，g[i][j]为后i个质因数选成集合j的方案数，然后转移很好想，就是f[i][va[i]|j]+=f[i-1][j]*rs[i]，其中rs是满足第i个质因数的方案数，g同理

然后我们需要合并出来一个“空出一个数”这样的东西来回答询问，合并的时候用orFWT即可

包含集合s的方案数也加到s的方案数里，就是andFWT的正变换部分，这样统计答案的时候就不用跑一遍了

然后回答的时候就是统计一下x极大极小质因数次幂的贡献然后直接查空出来这个集合的部分，最后乘上这个集合的选区方案数即可

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

const int N=100005,mod=1000000007,inv2=500000004;

int n,G,L,q,lm,p[N],tot,si[N],s[N],rs[N],va[N],con,f[605][70005],g[605][70005];

bool v[N];

int read()

{

    int r=0,f=1;

    char p=getchar();

    while(p>'9'||p<'0')

    {

        if(p=='-')

            f=-1;

        p=getchar();

    }

    while(p>='0'&&p<='9')

    {

        r=r*10+p-48;

        p=getchar();

    }

    return r*f;

}

void jia(int &x,int y)

{

    x+=y;

    (x>=mod)?x-=mod:0;

}

void jian(int &x,int y)

{

    x-=y;

    (x<0)?x+=mod:0;

}

void dfs(int w,long long v,int s1,int s2)

{

    if(w==tot+1)

    {

        s[s1|(s2<<tot)]++;

        return;

    }

    for(int i=0;i<=si[w];i++)

    {

        dfs(w+1,v,s1|((i==0)<<(w-1)),s2|((i==si[w])<<(w-1)));

        v*=p[w];

        if(v>n)

            break;

    }

}

int ksm(int a,int b)

{

    int r=1;

    while(b)

    {

        if(b&1)

            r=1ll*r*a%mod;

        a=1ll*a*a%mod;

        b>>=1;

    }

    return r;

}

void fwtor(int a[],int f)

{

    for(int i=1;i<lm;i<<=1)

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

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

            {

                if(f==1)

                    jia(a[i+j+k],a[j+k]);

                else

                    jian(a[i+j+k],a[j+k]);

            }

}

void fwtand(int a[],int f)

{

    for(int i=1;i<lm;i<<=1)

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

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

            {

                if(f==1)

                    jia(a[j+k],a[i+j+k]);

                else

                    jian(a[j+k],a[i+j+k]);

            }

}

int main()

{

    n=read(),G=read(),L=read(),q=read();

    if(L%G)

    {

        while(q--)

            puts("0");

        return 0;

    }

    L/=G,n/=G;

    int x=L;

    for(int i=2;i*i<=L;i++)

        if(x%i==0)

        {

            p[++tot]=i;

            while(x%i==0)

                si[tot]++,x/=i;

        }

    if(x>1)

        p[++tot]=x,si[tot]=1;

    dfs(1,1,0,0);

    int ss=(1<<(tot*2));

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

        if(s[i])

            va[++con]=i,rs[con]=ksm(2,s[i])-1;

    f[0][0]=1;

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

    {

        for(int j=0;j<ss;j++)

            jia(f[i][va[i]|j],1ll*f[i-1][j]*rs[i]%mod);

        for(int j=0;j<ss;j++)

            jia(f[i][j],f[i-1][j]);

    }

    g[con+1][0]=1;

    for(int i=con;i>=1;i--)

    {

        for(int j=0;j<ss;j++)

            jia(g[i][va[i]|j],1ll*g[i+1][j]*rs[i]%mod);

        for(int j=0;j<ss;j++)

            jia(g[i][j],g[i+1][j]);

    }

    lm=ss;

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

        fwtor(f[i],1);

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

        fwtor(g[i],1);

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

        for(int j=0;j<ss;j++)

            f[i][j]=1ll*f[i][j]*g[i+2][j]%mod;

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

        fwtor(f[i],-1),fwtand(f[i],1);

    // for(int i=0;i<=con;i++)

    // {

        // for(int j=0;j<ss;j++)

            // cerr<<f[i][j]<<" ";

        // cerr<<endl;

    // }

    while(q--)

    {

        int x=read(),s=0;

        if(x%G||L%(x/G)||(x/G)>n)

        {

            puts("0");

            continue;

        }

        x/=G;

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

        {

            int sm=0;

            while(x%p[i]==0)

                x/=p[i],sm++;

            if(sm==0)

                s|=(1<<(i-1));

            if(sm==si[i])

                s|=(1<<(i-1+tot));

        }

        int w=lower_bound(&va[1],&va[con+1],s)-va-1;//cerr<<w<<endl;

        printf("%lld\n",((1ll*f[w][(ss-1)^s]*(rs[w+1]+1)%mod*inv2%mod)+mod)%mod);

    }

    return 0;

}

巴特西

bzoj 5019: [Snoi2017]遗失的答案【dp+FWT】

最新文章

热门文章