本题即斐波那契树上的删边游戏（称为Green Hackenbush），这与第301题及之后一系列取石头游戏一样，是一种Nim游戏。
用所谓的Colon原则，不断把子树替换为其左右子树Nim值的异或和，即可递归计算结果为$438505383468410633$。
注：为方便书写，代码中用到walrus算符等新特性，因此以下源码为Python 3。此外，本题需要数分钟运行，但并未输出进度。
m=10**18
n=10000
def next_counts(x,y,a,b):
z=[0]*(n+1)
z[a+1]=z[b+1]=1
for c in range(n+1):
if (d:=(b+1)^(c+1))<=n:
z[d]=(z[d]+x[c])%m
if (d:=(a+1)^(c+1))<=n:
z[d]=(z[d]+y[c])%m
return z
a,b=0,1
x,y=[0]*(n+1),[0]*(n+1)
y[0]=1
for i in range(3,n+1):
x,y=y,next_counts(x,y,a,b)
a,b=b,(a+1)^(b+1)
print(y[0])
|
