非弹跳数

若一个自然数中的每一位数字都大于等于其左边的数字，比如134468，则称这样的数被称为上升数。

同样地，若一个自然数中的每一位数字都小于等于其左边的数字，比如66420，则称这样的数被称为下降数。

若一个自然数既不是上升数也不是下降数，比如155349，则称这样的数为弹跳数。

随着上界的增加，弹跳数将变得越来越普遍，例如在小于一百万的数中，只有12951个非弹跳数，而小于$10^{10}$的数中有277032个非弹跳数。

小于一googol（即$10^{100}$）的数中有多少个非弹跳数？

本题难度:

解答

与第112题解法完全相同，结果是$51161058134250$。

b=[list(range(10))]
c=[[min(10-k,9) for k in range(10)]]
s=99
i=2
while i < 100:
    b.append([sum(b[-1][j] for j in range(k+1)) for k in range(10)])
    c.append([sum(c[-1][j] for j in range(k,10)) for k in range(10)])
    s=s+sum(b[-1])+sum(c[-1])-9
    i+=1
    
print s