[bzoj4589]Hard Nim(FWT快速沃尔什变化+快速幂)

左手的ㄟ右手 2021-12-03 07:53 303阅读 0赞

题面：[https://www.lydsy.com/JudgeOnline/problem.php?id=4589][https_www.lydsy.com_JudgeOnline_problem.php_id_4589]

# 题意 #

求选恰好n个数，满足每个数都是不大于m的质数，且它们的异或和为0的方案数。

# 解法 #

设f(i,j)为选了i个数，异或和为j的方案数，转移如下：  
\\\[ f(i,j)=\\sum\_\{k\\bigoplus\{p\}=j\}\{f(i-1,k)\*\[p\\quad is\\quad prime\]\} \\\]  
我们发现这是一个异或卷积的形式，状态向量一开始只有0的地方是1，它与一个只有质数下标处值为1的向量卷积n次，然后下标为0处的值就是答案。  
但我们又发现n是1e9级别的，所以考虑用快速幂求出质数向量自卷n次的结果，最后再卷上状态向量就行。  
总时间复杂度O(m*log2(n)*log2(m)).

#include<bits/stdc++.h>
    using namespace std;
    #define re register
    #define il inline
    #define rep(i,a,b) for(re int i=(a);i<=(b);++i)
    const int N =105005;
    int p[N],cnt,n,m;
    bool vis[N];
    il int read(){
        int x=0,f=1;char ch=getchar();
        while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
        while(ch<='9'&&ch>='0')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
        return x*f;
    }
    const int mod =1e9+7;
    typedef long long ll;
    const ll inv =500000004;
    int g[N],f[N];
    ll ksm1(ll x,ll y){
        ll aa=1ll;
        for(;y;y>>=1,x=(x*x)%mod)if(y&1)aa=(aa*x)%mod;
        return aa;
    }
    void fwt(int *a,int l,int f){
        re int i,j,k,x,y;
        for(j=1;j<l;j<<=1){
            for(i=0;i<l;i+=(j<<1)){
                for(k=i;k<i+j;++k){
                    x=a[k],y=a[k+j];
                    a[k]=(x+y)%mod,a[k+j]=(x-y+mod)%mod;
                    if(f==-1)a[k]=1ll*a[k]*inv%mod,a[k+j]=1ll*a[k+j]*inv%mod;
                }
            }
        }
    }
    void ksm(int l,int y){
        fwt(g,l,1),fwt(f,l,1);
        for(;y;y>>=1){
            if(y&1){
                rep(i,0,l-1)f[i]=1ll*f[i]*g[i]%mod;
            }
            rep(i,0,l-1)g[i]=1ll*g[i]*g[i]%mod;
        }
    }
    int main(){
        rep(i,2,50003){
            if(!vis[i])p[++cnt]=i;
            rep(j,1,cnt){
                if(i*p[j]>50000)break;
                vis[i*p[j]]=1;
                if(i%p[j]==0)break;
            }
        }
        while(~scanf("%d%d",&n,&m)){
            memset(g,0,sizeof(g)),memset(f,0,sizeof(f));
            rep(i,1,cnt){
                if(p[i]>m)break;
                g[p[i]]=f[p[i]]=1;
            }
            int l=1;
            for(;l<=m;l<<=1);
            ksm(l,n-1);//从1次幂开始乘方，f[0]初值为0是为了强制取恰好n堆
            fwt(f,l,-1);
            printf("%d\n",f[0]);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/Sinuok/p/11099515.html

[https_www.lydsy.com_JudgeOnline_problem.php_id_4589]: https://www.lydsy.com/JudgeOnline/problem.php?id=4589