← 完整题目索引

PROJECT EULER · #1006

斐波那契子词

Fibonacci Subwords

仅题目 · 待解原题 ↗

从两个字符串 S0=0 和 S1=01 开始,我们将 Sn 定义为 Sn−1Sn−2 for n≥2 的串联。
例如,S2=010、S3=01001 和 S4=01001010。
如果一个字符串是某个 Sn 的子字符串连续子序列,则该字符串称为斐波那契子字。

有趣的是,对于每个正整数 k,只有 k+1 个长度为 k 的不同斐波那契子字。我们将它们解释为十进制数(忽略前导零)并令 Ψ(k) 为它们的平方和。

例如,长度为 3 的四个不同的斐波那契子字是 001,010,100,101。因此 Ψ(3)=12+102+1002+1012=20302。
您还将获得 Ψ(10)≡10699667(mod101001001)。

求 Ψ(1018)mod101001001。

题解待补充

这道题的题目已收录,解题思路、代码和答案将在后续补充。