返回首页 返回专题

【BZOJ4589】Hard Nim 题解

Nim游戏的先手必胜条件是所有石子异或和为0

定义卷积满足：

显然，我们定义的卷积满足交换律与结合律

设表示前t堆异或和为x的方案数

特别地，

定义当且仅当x是质数且x不超过m

可以推出：

进而推出：

最终答案就是

卷积可以用FWT完成，F的n次幂可以用快速幂解决，套起来时间复杂度是2个log

并不是非常优秀

仔细想一下会发现，快速幂中每次循环结束我们进行IDWT，下一次循环开始我们又进行DWT，二者互为逆运算，显然没有这个必要去转一个圈

因此可以一开始进行一次DWT，最后再进行IDWT，时间复杂度变成了1个log

#include<bits/stdc++.h>
#define Mod 1000000007
#define inv2 500000004
using namespace std;

const int N=200010;
int a[N],ans[N];
bool prm[3*N];

void FWT(int *a,int n,bool flag)
{
	for(int i=1;i<n;i<<=1)
		for(int j=0;j<n;j+=(i<<1))
			for(int k=0;k<i;k++)
			{
				int x=a[j+k],y=a[i+j+k];
				if(flag) a[j+k]=(x+y)%Mod,a[i+j+k]=(x-y+Mod)%Mod;
				else a[j+k]=1ll*(x+y)*inv2%Mod,a[i+j+k]=1ll*(x-y+Mod)*inv2%Mod;
			}
}

int main()
{
	for(int i=2;i<=500000;i++) prm[i]=1;
	for(int i=2;i<=500000;i++)
		for(int j=i+i;j<=500000;j+=i)
			prm[j]=0;
	int n,m;
	while(~scanf("%d%d",&n,&m))
	{
		memset(a,0,sizeof(a));
		int len;for(len=1;len<=m;len<<=1);
		for(int i=0;i<len;i++) a[i]=prm[i]&&i<=m;
		FWT(a,len,1);
		for(int i=0;i<len;i++) ans[i]=a[i];
		for(n--;n;n>>=1)
		{
			if(n&1) for(int i=0;i<len;i++) ans[i]=1ll*ans[i]*a[i]%Mod;
			for(int i=0;i<len;i++) a[i]=1ll*a[i]*a[i]%Mod;
		}
		FWT(ans,len,0);
		printf("%d\n",ans[0]);
	}
	return 0;
}