本题与第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)
|