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)

本站所有文章如非特别声明皆为原创，转载请与作者本人联系并注明出处(原文链接)。如对文章有任何疑问或需指出错误，可以此页面提出问题，我会尽量及时回复。

←返回主页