考察所有坐标为整数、绝对值不超过120，且长度不超过60（否则无法回到原点）的向量作为各边的候选，将这些向量按极角排序。
考虑一个从原点出发，按逆时针方向沿着各边前进的质点，用$f(x,y,d)$表示到达点$(x,y)$且总行进距离为d的走法总数。
枚举极角以及每个极角所对应的向量，就可以递推生成上述函数。最后汇总$\sum_df(0,0,d)$，再扣除向量总数的一半（同向量原路返回的情况）即得结果$3600060866$。
注：以下为Python 3代码，因math.isqrt为Python 3新增函数。此外，代码中打印了进度信息。
import math
target=120
f=[{} for i in range(2)]
v={}
for x in range(-target,target+1):
for y in range(-target,target+1):
d2=x*x+y*y
d=math.isqrt(d2)
if target*target>=4*d2>0 and d*d==d2:
t=math.atan2(y,x)
if t < 0:t+=2*math.pi
if t in v:
v[t].append((x,y,d))
else:
v[t]=[(x,y,d)]
t=sorted(v.keys())
m,p=len(t),0
f[0][(0,0,0)]=1
i=0
while i < m:
f[1-p]=f[p].copy()
for x,y,d in f[p]:
for dx,dy,dd in v[t[i]]:
x2,y2=x+dx,y+dy
if dd+d<=target:
f[1-p][(x2,y2,dd+d)]=f[1-p].get((x2,y2,dd+d),0)+f[p][(x,y,d)]
i+=1
p=1-p
print(i,"out of",m,"cases completed")
print(sum(f[p].get((0,0,d),0) for d in range(1,target+1))-sum(1 for theta in v for x,y,d in v[theta])//2)
|
