记总长度为$n$且不含长度不小于$5$的回文子串的所有二进制数串的集合为$S_n$。
考虑在$d_1\ldots d_{n-1}\in S_{n-1}$后添加一位$d_n$所得新数串$d_1\ldots d_{n-1}d_n$，显然$sd_n$是否在$S_n$中仅由原串的最后五位$d_{n-5}\ldots d_{n-1}$所决定。
令$a=001011, b=110100$，简单计算即可发现只有$a$和$b$的自重复能生成符合要求的数串，即$S_n$中元素必定都是$aaaa\ldots$或$bbbb\ldots$的子串，且
$$|S_n|=[34,32,32,32,34,36][n\bmod 6], $$
从而
$$F_5(n)-F_5(n-1)=2^n-|S_n|, \quad n\ge 7.$$
即
$$F_5(n)=2(2^n-100\lfloor\frac{n}{6}\rfloor+[57,41,25,9,-8,-26][n\bmod 6])$$
直接计算即得结果$8907904768686152599$。
注：因使用sympy求乘法逆，以下代码为Python 3。
import math,sympy
N=10**18
mod=87654321
phi=58394976
inv=sympy.mod_inverse(phi//6*200,mod)
m=phi*mod
d=[34,32,32,32,34,36]
f=42
p=64
res=0
for n in range(7,7+phi):
p=(2*p)%mod
f+=p-d[n%6]
sol=(f*inv)%mod
if N>=phi*sol:
res+=math.ceil((N-phi*sol)/m)
print(res)
|
