BZOJ-4589: Hard Nim

Description

n堆石子，每堆个数为不超过m的质数。询问玩Nim游戏先手必输的方案数。多组询问，T<=80 n<=10^9 m<=5*10^4

设dp[i]表示亦或和为i的方案数，转移。
FWT优化位运算亦或卷积，初始化一堆时的dp值，求出F'[i]=(-1)^count(j&i)*f[j]后快速幂即可。时间复杂度O(mlogm+mlogn)

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define M 51000 
const int mod=1000000007;
typedef long long ll;
int n,m,lim;
int pri[M],cnt,a[101000];
bool v[M<<1];
void initialize()
{
    int i,j;
    for(i=2;i<=100000;++i)
    {
        if(!v[i]) pri[++cnt]=i;
        for(j=1;i*pri[j]<=100000&&j<=cnt;++j)
        {
            v[i*pri[j]]=1;
            if(i%pri[j]==0) break;
        }
    }
}
void fwt(int len)
{
    int i,j,k;
    for(i=1;i<len;i<<=1)
        for(j=0;j<len;j+=(i<<1))
            for(k=j;k<j+i;++k)
                a[k]=a[k]+a[k+i],a[k+i]=a[k]-(a[k+i]<<1);
}
void ufwt(int len)
{
    int i,j,k;
    for(i=len>>1;i;i>>=1)
        for(j=0;j<len;j+=(i<<1))
            for(k=j;k<j+i;++k)
                a[k]=(500000004ll*(a[k]+a[k+i]))%mod,a[k+i]=(a[k]-a[k+i]+mod)%mod;
}
int Pow(ll x,int y)
{
    ll re=1; x=(x%mod+mod)%mod;
    while(y)
    {
        if(y&1) re=re*x%mod;
        x=x*x%mod; y>>=1;
    }
    return re;
}
int main()
{
    initialize();
    while(~scanf("%d%d",&n,&m))
    {
        memset(a,0,sizeof a);
        for(int i=1;pri[i]<=m;++i) a[pri[i]]=1;
        for(lim=1;lim<=m;lim<<=1);
        fwt(lim);
        for(int i=0;i<lim;++i) a[i]=Pow(a[i],n);
        ufwt(lim);
        printf("%d\n",(a[0]%mod+mod)%mod);
    }
    return 0;
}