hdoj1850——关于nim博弈

nim和:a^b^c=0时为必败态(奇异局势)
有m堆石子,若先手可胜,则先手第一次取有几种方案
1。首先一点,因为是第一次取,取得时候可以保证有m堆(这是废话。。),因此最多有m种取石子方案(也就是说最多的情况下,每堆石子取一些石子可以构成一种方案)
为什么不可能一堆石子取出x个达到必败态,取出y个也达到必败态呢?(x!=y)
这个问题其实很好回答。假设3堆石子分别为11,12,14,那么
11d=(1011)b
12d=(1100)b
14d=(1110)b
因为只能取不能加,所以只能把1改成0(即把数变小),可见,如果我们从第一堆取石子使达到必败态,那么就需要改动含有奇数个1的列,也就是第1列和第4列,变成
2d=(0010)b
12d=(1100)b
14d=(1110)b
即第一堆取出11-2=9个石子,显然有奇数个1的列都要改,所以如果某一堆石子取出x个石子后可以达到必败态,则x唯一
2。a^a=0,0^a=a
上述公式应当是学计算机的同学都十分熟悉的,这是基本功(否则就只能算计算机爱好者了。。)
那么很容易得出a^b^c=(a^b^c^d)^d;意即一个数被异或在sum内,那么只要sum再异或一次该数,效果相当于该数从sum中踢了出去(表达不好,自己理解==!。。。)
3。(a^b)^(a^b)=0(就是上面公式a^a=0),假设3堆石子a,b,c。c>(a^b),那么显然如果从c堆取出x个石子使之达到必败态,只需要把c变为a^b。这样得:x=c-a^b。
综合以上几点,文章开始的问题也就解出来了。。
下面是代码