BZOJ 4589 Hard Nim

题目大意

给你一个游戏：N堆石子，两个人轮流操作，每次从任意一堆里拿走任意个数的石子，取走最后一个者胜利。你是后手，你想赢。

求合法的N堆石子，每堆石子个数为不超过M的质数的必赢合法方案个数。

这题很有趣……

首先如果可以这么做的话那么一定有所有堆石子异或和为0.具体原理不做证明，用到了SG函数。

之后就变成求异或和为0的所有方案个数和。

之后DP一下就好了。

设$F_{i,j}$表示已经处理i堆，异或和为j的方案个数。之后枚举新一堆放置多少就可以了。

发现可以FWT优化那就优化一下就可以了。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const long long inv=500000004,MO=1000000007;
int n,m,len;
long long res[100010];
int prm[50010],cnt;
bool v[50010];
void init()
{
	for(int i=2;i<=50000;++i)
	{
		if(!v[i]) prm[++cnt]=i;
		for(int j=1;j<=cnt&&i*prm[j]<=50000;++j)
		{
			v[i*prm[j]]=true;
			if(!(i%prm[j])) break;
		}
	}
}
void fwt()
{
	int tmp,i,j,k;
	for(i=1;i<=len;i<<=1)
		for(j=0;j<len;j+=i)
			for(k=j;k<j+(i>>1);++k)
			{
				tmp=res[k];
				res[k]=(res[k]+res[k+(i>>1)])%MO;
				res[k+(i>>1)]=(tmp-res[k+(i>>1)]+MO)%MO;
			}
}
void ifwt()
{
	int tmp,i,j,k;
	for(i=1;i<=len;i<<=1)
		for(j=0;j<len;j+=i)
			for(k=j;k<(j+(i>>1));++k)
			{
				tmp=res[k];
				res[k]=((res[k]+res[k+(i>>1)])*inv)%MO;
				res[k+(i>>1)]=((tmp-res[k+(i>>1)])*inv)%MO;
			}
}
long long qpow(long long X,long long Y)
{
	long long ret=1;
	while(Y)
	{
		if(Y&1) ret=(ret*X)%MO;
		Y>>=1,X=(X*X)%MO;
	}
	return ret;
}
int main()
{
	init();
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		memset(res,0,sizeof res);
		for(int i=1;i<=cnt&&prm[i]<=m;++i) res[prm[i]]=1;
		for(len=1;len<=m;len<<=1);
		fwt();
		for(int i=0;i<len;++i) res[i]=qpow(res[i],n);
		ifwt();
		printf("%lld\n",res[0]);
	}
	return 0;
}