759. A Squared Recurrence Relation

The function $f$$f$ is defined for all positive integers as follows:

It can be proven that $f(n)$$f(n)$ is integer for all values of $n$$n$.

The function $S(n)$$S(n)$ is defined as $S(n)={\displaystyle \sum _{i=1}^{n}f(i{)}^2}$$S(n) = \displaystyle \sum_{i=1}^n f(i) ^2$. For example, $S(10)=1530$$S(10)=1530$ and $S({10}^2)=4798445$$S(10^2)=4798445$.

Find $S({10}^{16})$$S(10^{16})$. Give your answer modulo $1000000007$$1\,000\,000\,007$.

759. 递推关系的平方和

一定义在全体正整数上的函数 $f$$f$ 满足下述递推：

可以证明，对诸正整数 $n$$n$，$f(n)$$f(n)$ 都是整数。

定义函数 $S(n)={\displaystyle \sum _{i=1}^{n}f(i{)}^2}$$S(n) = \displaystyle \sum_{i=1}^n f(i) ^2$。例如 $S(10)=1530$$S(10)=1530$、$S({10}^2)=4798445$$S(10^2)=4798445$。

求 $S({10}^{16})$$S(10^{16})$ 模 $1000000007$$1\,000\,000\,007$ 的值。

点 这个链接 回到源站。

点 这个链接 回到详细版题目目录。