题目描述
Define $s(n)$ to be the smallest number that has a digit sum of $n$. For example $s(10)=19$.
Let $S(k)=\sum_{n=1}^k s(n)$. You are given $S(20)=1074$.
Further let $f_i$ be the Fibonacci sequence defined by $f_0=0,f_1=1$ and $f_i=f_{i−2}+f_{i−1}$ for all $i≥2$.
Find $\sum_{i=2}^{90} S(f_i)$. Give your answer modulo $1\ 000\ 000\ 007$.
题意
定义 $s(n)$ 表示最小的数位和为 $n$ 的整数,例如 $s(10) = 19$。
并定义 $S(k) = \sum_{n=1}^k s(n)$ ,例如 $S(20) = 1074$ 。
此外定义 $f_i$ 为fibonacci第 $n$ 项。
求 $\sum_{i=2}^{90} S(f_i) % 1\ 000\ 000\ 007$ 。
分析
首先我们有,$s(n)$ 的后缀显然是一串 $9$ ,前缀是某一个数字或者空。这样为最大。
然后一个简单的想法是,我们诸位统计答案,对于每一位来说,显然是存在 $1\rightarrow 9$ 。然后剩下的这个位置一定全是 $9$ 。这样可以统计出答案,但是我们发现,数据量太大了。$o(n)$ 的显然不太够。
我的做法是,我把每个数字都 $+1$ ,这样做的好处是,每一位一定是$1\rightarrow9$ 。然后后面的位数就是一个等比数列,然后稍微处理一下前面几位就可以了。
简单画个示意图,假设 $n = 20$。
老做法是这样:
百位 | 十位 | 个位 |
---|---|---|
$0$ | $0$ | $1\rightarrow9$ |
$0$ | $1\rightarrow 9$ | $9$ |
$1\rightarrow 2$ | $9$ | $9$ |
然后我们诸位统计,答案的计算表达式大概是这样:${\sum_{i=1}^9 1 + 9(n-9)} + {\sum_{i=1}^9 + 9(n-18)}10 + {\sum_{i=1}^2}*100$
新做法是每个数 $+1$ ,然后补一个 $1$ 然后总答案 $-(n+1)$ 。补 $1$ 后:
百位 | 十位 | 个位 |
---|---|---|
$0$ | $0$ | $1\rightarrow9$ |
$0$ | $1\rightarrow 9$ | $0$ |
$1\rightarrow 3$ | $0$ | $0$ |
然后对于后缀是一个公比为 $10$ 的等比数列。可以直接统计:
$45(1+10) + \sum_{i=1}^{3}100 - (20+1)$
代码
给大佬递上我奇丑无比的代码 (/ω\)
1 |
|