PRojectEuler 560

---------------------------------------------------
第一次在前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...
---------------------------------------------------