可以验证,黑格数量的消长在充分多(大约1万多步)的步数后呈现周期性的变化,周期是104。
因此先模拟充分多的步数,再利用周期性即可得最终结果$115384615384614952$。
target=10**18
bound=12000
T=104
d={}
dx,dy=[-1,0,1,0], [0,-1,0,1]
x=y=k=0
a=[]
for i in range(bound):
if d.get((x,y),0)==0:
d[(x,y)]=1
k=(k-1)%4
a.append(1)
else:
d[(x,y)]=0
k=(k+1)%4
a.append(-1)
x+=dx[k]
y+=dy[k]
print sum(a)+sum(a[-T:])*((target-bound)/T)+sum(a[-T:-T+(target-bound)%T])
|