原文链接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;

}

巴特西

BZOJ4589 Hard Nim FWT 快速幂博弈

题目传送门 - BZOJ4589

题意

题解

代码

最新文章

热门文章

巴特西

BZOJ4589 Hard Nim FWT 快速幂 博弈

题目传送门 - BZOJ4589

题意

题解

代码

最新文章

热门文章

BZOJ4589 Hard Nim FWT 快速幂博弈