原文链接https://www.cnblogs.com/zhouzhendong/p/BZOJ4589.html
题目传送门 - BZOJ4589
题意
有 $n$ 堆石子，每一堆石子的取值为 $2$ ~ $m$ 之间的素数。
问在所有不同的取值中，先手必败的方案总数。
答案对 $10^9+7$ 取模。
$n\leq 10^9,m\leq 50000$
题解
第一次写 FWT 。
感觉 FWT 比 FFT 简单多了。
下面进入正题。
首先，我们再回顾一下 Nim游戏 中先手必败的情况：所有数的异或和为 $0$ 。具体证明自行百度，这里不加赘述。
我们构造一个多项式 $A$ ，如果 $i$ 为素数，那么 $A(i)=1$ ，否则 $A(i)=0$ 。
定义卷积如下形式：
$$C(k)=\sum_{i\ XOR\ j=k} A(i)B(j)$$
于是我们看到，如果 $n=2$ ，那么答案为 $A^2(0)$ 。
类似地，原题答案为 $A^n(0)$ 。
注意一下上面的那个卷积式可以用 FWT 来做。
我们先 FWT 一下，类似于多项式点值相乘，异或卷积的“点值”也可以自己相乘，于是每一个值都直接取其 $n$ 次方，然后再 IFWT 一下就可以得到目标多项式了。
代码
#include <bits/stdc++.h>
using namespace std;
const int N=1<<16,mod=1e9+7,inv2=(mod+1)/2;
int Pow(int x,int y){
if (!y)
return 1;
int xx=Pow(x,y/2);
xx=1LL*xx*xx%mod;
if (y&1)
xx=1LL*xx*x%mod;
return xx;
}
bool check(int x){
for (int i=2;i*i<=x;i++)
if (x%i==0)
return 0;
return x>1;
}
int n,m,k,A[N];
void FWT(int a[],int n,int flag){
for (int d=1;d<n;d<<=1)
for (int i=0;i<n;i+=(d<<1))
for (int j=0;j<d;j++){
int x=a[i+j],y=a[i+j+d];
a[i+j]=(x+y)%mod;
a[i+j+d]=(x-y+mod)%mod;
if (flag<0){
a[i+j]=1LL*a[i+j]*inv2%mod;
a[i+j+d]=1LL*a[i+j+d]*inv2%mod;
}
}
}
int main(){
while (~scanf("%d%d",&k,&m)){
for (n=1;n<=m;n<<=1);
for (int i=0;i<n;i++)
A[i]=(check(i)&&i<=m)?1:0;
FWT(A,n,1);
for (int i=0;i<n;i++)
A[i]=Pow(A[i],k);
FWT(A,n,-1);
printf("%d\n",A[0]);
}
return 0;
}