BZOJ4589 Hard Nim

FWT

題目傳送門

首先後手必勝的條件是石子數異或和為0。

因為石子數隻能是質數個，那麼我們構造一個向量，維數為質數的打上1，其它的都是0，那麼方案數就是n個向量的異或卷積。FWT後快速幂一下再FWT回來就好了。

代碼：

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 1<<16
#define M 50000
#define F inline
using namespace std;
typedef long long LL;
const LL P=+,iv=P+>>;
int n,m,p[N]; bool f[N];
LL a[N];
F void Make(){
    f[]=f[]=true;
    for (int i=;i<=M;i++){
        if (!f[i]) p[++p[]]=i;
        for (int j=;j<=p[]&&p[j]*i<=M;j++){
            f[i*p[j]]=true;
            if (i%p[j]==) break;
        }
    }
}
F LL ksm(LL a,LL b){
    LL ret=;
    for (;b;a=a*a%P,b>>=)
        if (b&) ret=ret*a%P;
    return ret;
}
F void FWT(LL *a,int n,int f){
    for (int k=;k<n;k<<=)
        for (int i=;i<n;i+=k<<)
            for (int j=;j<k;j++){
                LL x=a[i+j],y=a[i+j+k];
                a[i+j]=(x+y)%P,a[i+j+k]=((x-y)%P+P)%P;
                if (f==-) (a[i+j]*=iv)%=P,(a[i+j+k]*=iv)%=P;
            }
}
int main(){
    for (Make();~scanf("%d%d",&n,&m);){
        memset(a,,sizeof(a)); int l;
        for (int i=;i<=p[]&&p[i]<=m;i++) a[p[i]]=;
        for (l=;l<=m;l<<=); FWT(a,l,);
        for (int i=;i<l;i++) a[i]=ksm(a[i],n);
        FWT(a,l,-),printf("%lld\n",a[]);
    }
    return ;
}