0310 取平方数石子
* * * *
拉格朗日计划
* * * *
取平方数石子

张三和李四正在玩取平方数石子的游戏。

该游戏是NIM游戏(见第301题)的变体,游戏中有三堆石块,数量分别用a,b,c表示。

玩家轮流从某一堆中取出石头,但每次取走的数量必须是完全平方数,最后无石可取的玩家输。

当$0\le a\le b\le c\le 29$,1160种情况先手输。

当$0\le a\le b\le c\le 100000$,先手输的情况共有几种?

本题难度:



解答

本题与第306题的分析方法相同,用到Sprague–Grundy定理

只需计算NIM值s(a), s(b), s(c),则游戏的胜负为$s(a)\oplus s(b)\oplus s(c)$(其中$\oplus$表示异或运算)该值为0时先手必败。

查OEIS A014586即得这些数字的NIM值,不过表中只有前10000个数的值,使用该页面PROG栏目中的代码即生成至100000。

直接三重循环a,b,c显然是不可取的,注意到NIM值的分布比较集中,因此用一个字典记录各NIM值出现的频率,并将s(a),s(b),s(c)从小到大排列分别记为$f_1\le f_2\le f_3$。

那么只需计算$f_1 < f_2 < f_3$,$0=f_1=f_2=f_3$,$0=f_1 < f_2=f_3$这三种情况并汇总即可,结果是$2586528661783$。

import math,itertools

target=100000

d=[]
for i in range(target+1):
    moves=sorted({d[i-r*r] for r in range(1,int(math.sqrt(i))+1)}) 
    mex=next((j for j in range(len(moves)) if moves[j]!=j),len(moves))
    d.append(mex)

s={}
for i,j in enumerate(d):
    s[j]=s.get(j,0)+1

print sum(s[a]*s[b]*s[c] for a,b,c in itertools.combinations(s.keys(),3) if a^b^c==0)+s[0]*(s[0]-1)*(s[0]-2)/6+s[0]*(s[0]-1)+s[0]+s[0]*sum(s[j]*(s[j]+1)/2 for j in s.keys() if j>0)