计算一些$M(n)$并观察其分布可以发现其由一系列连续的整数片段组成。
记$a_n$为初值是$a_0=a_1=1$的斐波那契数列，则可以不完全归纳出：
$$M(a_i+t)=\begin{cases}t & 0\le t\le\lfloor\frac{a_i-1}{2}\rfloor, \\ M(t) & \lfloor\frac{a_i-1}{2}\rfloor < t < a_{i-1}.\end{cases}$$
从而可得
$$S(a_{i+1}-1)-S(a_i-1)=\frac{m_i(m_i+1)}{2}+S(a_{i-1}-1)-S(m_i),$$
其中
$$m_i=\lfloor\frac{a_i-1}{2}\rfloor.$$
直接计算即得结果$88351299$。
注：因使用cache装饰器作记忆化搜索，以下代码为Python 3。
from functools import *
@cache
def S(n):
if n<4:return 0
s,a,b,c=0,1,1,2
while b<=n:
s+=m*(m+1)//2+S(a-1)-S(m) if (m:=(b-1)>>1)<=n-b else (n-b)*(n-b+1)//2
a,b,c=b,c,b+c
return s
print(S(10**18)%(10**8))
|
