BZOJ4589 Hard Nim

题目传送门

只要知道NIM游戏是什么,就会发现这道题其实就是要求n个数异或和为0的方案数,其中这n个数能且只能取小于等于m的质数。

构造向量a[i]=[i为质数],将n个a做异或卷积得到的向量b,b[0]即为答案。

所以只要快速幂求异或卷积就行了。要注意的是,快速幂中求异或卷积的时候不用每次都FWT和UFWT,这样是两个log的,会TLE(观察代码会发现每次UFWT后就会紧接着做一次FWT……没有任何意义)。其实只要FWT一次,对a的每一位都求快速幂就行了,最后再UFWT。

 

code

#include<cstdio> 
#include<cstring>
using namespace std;
const int p=1000000007,inv2=500000004;
int mo(int x){
    if(x>=p)
        return x-p;
    if(x<0)
        return x+p;
    return x;
}
int n,m,primenum,prime[50005],N,a[100005];
bool noprime[50005];
int power(int a,int b){
    int ans=1;
    for(;b;b>>=1,a=(long long)a*a%p)
        if(b&1)
            ans=(long long)ans*a%p;
    return ans;
}
void getprime(){
    for(int i=2;i<=50000;i++){
        if(!noprime[i])
            prime[++primenum]=i;
        for(int j=1;j<=primenum&&i*prime[j]<=50000;j++){
            noprime[i*prime[j]]=true;
            if(i%prime[j]==0)
                break;
        }
    }
}
void FWT(int *a,int n){
    for(int m=1;m<n;m<<=1)
        for(int i=0;i<n;i+=m+m)
            for(int j=0;j<m;j++){
                int x=a[i+j],y=a[i+j+m];
                a[i+j]=mo(x+y);
                a[i+j+m]=mo(x-y+p);
            }
}
void UFWT(int *a,int n){
    for(int m=1;m<n;m<<=1)
        for(int i=0;i<n;i+=m+m)
            for(int j=0;j<m;j++){
                int x=a[i+j],y=a[i+j+m];
                a[i+j]=(long long)mo(x+y)*inv2%p;
                a[i+j+m]=(long long)mo(x-y)*inv2%p;
            }
}
int main(){
    getprime();
    while(scanf("%d%d",&n,&m)!=EOF){
        memset(a,0,sizeof(a));
        for(int i=2;i<=m;i++)
            if(!noprime[i])
                a[i]=1;
        N=1;
        while(N<=m)
            N<<=1;
        FWT(a,N);
        for(int i=0;i<N;i++)
            a[i]=power(a[i],n);
        UFWT(a,N);
        printf("%d\n",a[0]);
    }
    return 0;
}

一条评论

  1. BZOJ4589 Hard Nim
    avatar
    1楼

    也就我这种蒟蒻会写递归版的FWT了

    发表评论