本题涉及的Nim游戏及其理论本人不了解，以下解答和代码摘译改编自官方论坛：
本题需要计算每个局面的Nim值，把每个局面理解成$n\times n$位的二进制数，则可以观察到两个不同局面的Nim值是它们的异或和，因此一个局面的异或值可以理解为是一系列只有单个白色圆盘的局面的异或和。
把$(x,y)$处有单个白圆盘的局面称为局面$(x,y)$，则可以进一步注意到其Nim值等于局面$(x,1)$和局面$(1,y)$的Nim积，如此就将问题归约到了边界上的一维问题，从而可以进一步用异或和计算。
最终结果是$3996390106631$。
注：因使用cache装饰器作记忆化搜索，以下代码为Python 3，递归实现难以打印进度，运行约需一小时。
import itertools
from functools import *
from collections import Counter
N=10**6
def mex(it):
s=set(it)
return next(i for i in itertools.count() if i not in s)
@cache
def nimProd(i,j):
if i&~-i: return nimProd(i&~-i,j)^nimProd(i&-i,j)
if j&~-j: return nimProd(i,j&~-j)^nimProd(i,j&-j)
return mex(nimProd(a,b)^nimProd(a,j)^nimProd(i,b) for a in range(i) for b in range(j))
def edge(f):
vals=lambda mx: itertools.takewhile(lambda v: v <= mx, map(f, itertools.count(1)))
s=[0]
s.extend(s[-1]^mex(s[-1]^s[x-w] for w in vals(x)) for x in range(1,N+1))
return s[-1],Counter(s[x]^s[x-w] for w in vals(N) for x in range(w,N+1))
A,As=edge(lambda w:w*w)
B,Bs=edge(lambda h:h*(h+1)//2)
target=nimProd(A,B)
print(sum(ac*bc for a,ac in As.items() for b,bc in Bs.items() if target==nimProd(a,b)))
|
