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 ;
}