PRojectEuler 560
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
---------------------------------------------------
第一次在前50做出一道题啊
好高兴啊
---------------------------------------------------
题意是说定义了一种新的nim游戏，和原来差不多，只不过每次拿的石子数必须和这一堆的石子数互质
，一共有n堆，每堆石子数小于k,问对于n=k=10^7，有多少种先手必败的开局
也就是要问sg为0的开局
因为nim游戏是只有1堆的nim游戏的和
所以把只有一堆的sg算出来再说
然后发现不会了...
打表找规律发现
sg[1]=1
sg[2]=0
sg[i]=sg[ms[i]](i不是质数)
sg[i]=max{sg[k]|1<=k<=i-1}+1(i是奇质数)
然后就可以把只有一堆的sg值算出来啦
然后问题就变成了现在每个位置都可以选a[1]~a[k]的值，问xor和为0的选法的方案数
设f[i][j]表示长度为i,xor和为j的方案数
显然不需要把整个f都求出来不然爆炸了
倍增就行了
现在考虑怎么合并两个长度
显然是f[a+b][c]=∑(i=0,max)∑(j=0,max)f[a][i]*f[b][j]*[a xor b = c]
然后在dundundun的指点下，我知道了这是个裸的fwt...
---------------------------------------------------
评论 (0)
