684. 数字和的逆函数(Inverse Digit Sum)

\(s(n)\)为最小的数字和为\(n\)的数,例如\(s(10)=19\),记\(\displaystyle S(k) = \sum_{n=1}^k s(n)\),已知\(S(20) = 1074\)。另记\(f_i\)为斐波那契数列,其中\(f_0=0,f_1=1\),则对任意\(i\ge2\)\(f_i=f_{i-2}+f_{i-1}\)

\(\displaystyle \sum_{i=2}^{90} S(f_i)\),并将你的答案对\(1\ 000\ 000\ 007\)取余。

分析:首先我们来分析一下\(s(n)\),假设\(s(n)=d\),则\(d\)各位数加起来等于\(n\),这样的\(d\)有很多个,我们要求的是其中最小的一个。为了让\(d\)最小,则应该让\(d\)的第一位数足够小,而之后的位数足够大,每位数最大只能为九,所以\(d\)除第一位外都为九,而第一位则为\(n\)除以九的余数。比如对于\(s(10)\),因为\(10\%9=1\),则这个数字的第一位为一,则第二位数为\(10-1=9\),所以我们有\(s(10)=19\)。同理,我们有\(s(11)=29,s(12)=39\)等等,即:

$$ s(n)=(r+1)\times10^k-1,where\ n=9k+r,k\ge0,0\le r<9 $$

可以看到\(s(n)\)实际上关于\(k,r\)的函数,则可以绘制一个二维表格如下:

微信图片_20210311084129

从表格中可以明显的看出\(r\)决定了数字的首位,而\(k\)决定了数字中\(9\)的个数。对于表格中每一行其\(k\)都是固定的,我们可以计算每一行数字的和,即为\(45\times10^k-9\)。为了计算前\(n\)\(s(n)\)的和\(S(n)\),则我们可以用\(n\)除以九,得到相应的除数\(K\)和余数\(R\),则\(S(n)\)应该等于前\((K-1)\)行的和以及第\(K\)行的前\(R\)个数字的和,即:

$$ \begin{aligned} S( n) & =\sum ^{K-1}_{k=0}\left( 45\times 10^{k} -9\right) +\sum ^{R}_{r=0}\left\{( r+1) \times 10^{K} -1\right\}\\ & =45\sum ^{K-1}_{k=0} 10^{k} -\sum ^{K-1}_{k=0} 9+10^{K}\sum ^{R}_{r=0}( r+1) -\sum ^{R}_{r=0} 1\\ & =45\times \frac{1-10^{K}}{1-10} -9K+10^{K} \times \frac{( R+1)( R+2)}{2} -R-1\\ & =5\times 10^{K} -5-9K+10^{K} \times \frac{( R+1)( R+2)}{2} -R-1\\ & =10^{K}\left( 5+\frac{( R+1)( R+2)}{2}\right) -9K-R-6 \end{aligned} $$

我们实际上得到了一个\(S(n)\)的封闭公式,题目要求计算\(\sum_{i=2}^{90}f_i\),并对\(m=10^9+7\)取余,有:

$$ \left(\sum ^{90}_{i=2} S( f_{i})\right) \ \%\ m=\left(\sum ^{90}_{i=1}( S( f_{i}) \%m)\right) \%m $$

则有:

$$ \begin{aligned} S( f_{i}) \%m & =\left( 10^{K}\left( 6+\frac{R( R+3)}{2}\right) -9K-R-6\right) \%m\\ & =\left( 10^{K}\left( 6+\frac{R( R+3)}{2}\right)\right) \%m-9K-R-6 \end{aligned} $$

通过以上公式,我们可以快速计算出题目的结果。代码如下:

# time cost = 271 µs ± 3.42 µs

def s(k,r,m=10**9+7):
    res = ((r+1)*(r+2)//2+5)*pow(10,k,m)-9*k-6-r
    return res

def main(n=90):
    fib = [0,1]
    for _ in range(n-1):
        fib.append(sum(fib[-2:]))
    res = [s(*divmod(fib[i],9)) for i in range(2,n+1)]
    return sum(res)%(10**9+7)