正题

题目大意

求有多少个长度为\(n\)的数列满足它们都是不大于\(m\)的质数且异或和为\(0\)。

解题思路

两个初始多项式\(F[0]=1\)，\(G[prime\leq m]=1\)，然后答案就是\(F\ xor\ G^n\)。然后\(\text{FWT}\)之后点值快速幂就好了。

时间复杂度\(O(n\log n)\)

\(\color{white}{写水题有助于背板}\)

code

#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

using namespace std;

const ll N=(1<<16)+10,P=1e9+7,inv2=(P+1)/2;

ll n,k,m,f[N],g[N];

bool v[N];

void FWT(ll *f,ll op){

    if(op==-1)op=inv2;

    for(ll p=2;p<=n;p<<=1)

        for(ll k=0,len=p>>1;k<n;k+=p)

            for(ll i=k;i<k+len;i++){

                ll x=f[i],y=f[i+len];

                f[i]=(x+y)*op%P;

                f[i+len]=(x-y+P)*op%P;

            }

    return;

}

signed main()

{

    while(scanf("%lld%lld",&k,&m)!=EOF){

        memset(f,0,sizeof(f));

        memset(g,0,sizeof(g));

        memset(v,0,sizeof(v));

        n=1;

        while(n<=m)n<<=1;

        for(ll i=2;i<=m;i++){

            if(!v[i]){

                f[i]=1;

                for(ll j=i;j<=m;j+=i)

                    v[j]=1;

            }

        }

        g[0]=1;

        FWT(g,1);FWT(f,1);

        while(k){

            if(k&1){

                for(ll i=0;i<n;i++)

                    g[i]=g[i]*f[i]%P;

            }

            for(ll i=0;i<n;i++)

                f[i]=f[i]*f[i]%P;

            k>>=1;

        }

        FWT(g,-1);

        printf("%lld\n",g[0]);

    }

    return 0;

}

巴特西

bzoj4589-Hard Nim【FWT】

正题

题目大意

解题思路

code

最新文章

热门文章