113. 非跳跃数(Non-bouncy numbers)

从左往右,如果每一位数字都大于等于其左边的数字,这样的数被称为上升数,比如134468。同样地,如果每一位数字都大于等于其右边的数字,这样的数被称为下降数,比如66420。如果一个正整数既不是上升数也不是下降数,我们就称之为跳跃数,比如155349。

随着\(n\)的增长,小于\(n\)的跳跃数的比例也随之增长;在小于一百万的数中,只有12951个非跳跃数,而小于\(10^{10}\)的数中有277032个非跳跃数。求在小于一古戈尔(\(10^{100}\))的数中有多少个非跳跃数?

分析:对于题目中给出的这个巨大的数据范围,显然我们无法用暴力方法解决这个问题。令人意外的是,这个问题的一个妙解竟然与我们在第十五题中涉及过的格子路径有关。我们可以与格子路径来表示特定的上升数与下降数,而格子路径的条数可以表示相应的上升数与下降数的个数。

img

上图分别绘制了总共三位数的上升数和下降数的格子路径,先来看左边的上升数。左边竖直的数字表示从0至9十个数字,而最下方横着数字表示数字的第几位,因为这们这里演示的三位数,所有有三个数字。假如我们以左下角标黄的数字0为起点,以右上方的标黄方格为终点,每次只允许向上或者向右移动一个方格,那么每一个这样的路径就可以表示一个上升数。在如图所示的绿色路径中,当向右移动时,我们就写下最左侧对应的数位,因此数字的第一位是0,第二位也是0,而第三位则是5,所以这条路径对应的上升数就是\('005'\)。从上图易知,为了从起点到达终点,我们需要向上移动9步,向右移动3步,总共移动12步,因此总的路径数就等于\(C_{12}^3=220\)种。这也就是说对于\(10^3\)以内的数字,其中有220个是上升数。需要注意的是,对于数字\('000'\)我们不认为它构成一个上升数,所以还需要减去一。同理,对于\(10^n\)以内的数字,其中上升数的个数\(inc=C_{n+9}^9-1\)

再来看下降数,与上升数不同的是,下降数的开头与结尾都可以是0,所以总的数位个数是10而不是9,所以总的步数应该是\(n+10\),其中向上走\(10\)步,向右走\(n\)步,因此总的路径数应该为\(C_{10+n}^{10}\)。需要注意的是,我们也需要排除全部数字为0的情况,如图所示的就是这样一条路径,易知这样的路径总共有\((n+1)\)条,因此\(10^n\)内的下降数个数\(dec=C_{10+n}^{10}-n-1\)

在以上两种计数中,我们都包含了数字大小完全不变的情况,比如\('55555'\)这类的数字,从上图容易看出,这样的路径共有\(9n\)条。所以,\(10^n\)以内的上升数与下降数共有:

$$ total=(C_{n+9}^9-1)+(C_{n+10}^{10}-n-1)-9n=C_{n+9}^9+C_{n+10}^{10}-10n-2 $$

根据以上公式,我们可以很容易的计算出\(10^{100}\)以内的非跳跃数的个数,这里不再赘述,代码如下:

# time cost = 8.51 µs ± 116 ns

from math import factorial as fac

def comb_num(n,k):
    num = fac(n)//(fac(n-k)*fac(k))
    return num

def main(d=100):
    res = comb_num(d+9,9)+comb_num(d+10,10)-10*d-2
    return res