当$n=5^k$时$T_5(n)$形成OEIS A180168中的序列，即
$$T_5(5^k)=2T_5(5^{k-1})+5T_5(5^{k-2}).$$
随后把$5^k$分解为五个大小为$5^{k-1}$的块分别递归处理即可，最终结果是$22173624649806$。
import math
def T5(k):
if k <= 2:
return [0,1,3][k]
return 2*T5(k-1)+5*T5(k-2)
def T(n):
if n < 5:return 0
k=int(math.log(n,5))
r=n//5**k
if n <= 2*5**k:
return r*T5(k)+T((n-r*5**k))
elif n < 3*5**k:
return 2*T5(k)+T((n-2*5**k)) if n < 2*5**k+3*5**(k-1) else T(2*5**k+3*5**(k-1)-5)
else:
return 2*T5(k)+3*T5(k-1)+T((n-3*5**k)//5)
print T(10**18)
|
