题目113：一个googol（10^100）以下有多少数字不是跳跃数？

欧拉计划

Non-bouncy numbers

Working from left-to-right if no digit is exceeded by the digit to its left it is called an increasing number; for example, 134468.

Similarly if no digit is exceeded by the digit to its right it is called a decreasing number; for example, 66420.

We shall call a positive integer that is neither increasing nor decreasing a "bouncy" number; for example, 155349.

As n increases, the proportion of bouncy numbers below n increases such that there are only 12951 numbers below one-million that are not bouncy and only 277032 non-bouncy numbers below .

How many numbers below a googol are not bouncy?

题目：

如果一个数的每一位都大于等于前一位，则称其为递增数，例如 134468。

类似的，如果一个数的每一位都小于等于前一位，则称其为递减数，例如 66420。

如果一个正整数既不是递增数也不是递减数，则称其为一个“跳跃数”，例如 155349。

随着 n 的增加，小于 n 的跳跃数的比例不断增加，以至于到了一百万以下的数中只有 12951 个不是跳跃数， 以下只有 277032 个数不是跳跃数。

一个googol 以下的数中有多少个不是跳跃数？

迷雾少年

googol是啥意思

jerryxjr1220

from math import factorial as f
print(sum([f(i+8)//f(i)//f(8) for i in range(1, 101)]) + sum([f(i+9)//f(i)//f(9) for i in range(1, 101)]) - 10*100)

51161058134250

永恒的蓝色梦想

C++ 2ms

#include<iostream>
using ulong = unsigned long long;


template<size_t size>
constexpr ulong sum(ulong(&array)[size])noexcept {
    ulong result = 0;

    for (ulong i : array) {
        result += i;
    }

    return result;
}


template<size_t size>
constexpr void accumulate(ulong(&array)[size]) noexcept { //累加函数，参考 Python 的 itertools.accumulate
    for (size_t index = 1; index < size; index++) {
        array[index] += array[index - 1];
    }
}


constexpr ulong non_bouncy(size_t digits)noexcept {
    switch (digits) {
    case 0:
    case 1:
        return 0;
    }

    ulong array[]{ 1,2,3,4,5,6,7,8,9,9 };
    ulong result =
        9 //1位数既不是递增数也不是递减数
        + sum(array) * 2 - array[9] //递增数和递减数的和
        - --digits * 9 //每位都相同的数字，既属于递增数又属于递减数
        ;

    while (--digits) {
        accumulate(array);
        result += sum(array) * 2 - array[9];//递增数和递减数的和
    }

    return result;
}


int main() {
    using namespace std;
    ios::sync_with_stdio(false);
    cout << non_bouncy(100) << endl;
    return 0;
}

guosl

本题所涉及的数比较大故在程序中用了大数库mpir。

/*
答案：51161058134250
耗时：0.000191秒
*/
#include <iostream>
#include <mpir.h>
#include <omp.h>
using namespace std;

int f[10][10];//f[i][j]为长度是i且最后一个数的值是j的严格递增序列的个数
int g[11][10];//g[i][j]为长度是i且最后一个数的值是j的严格递减序列的个数

int main(void)
{
  double d = omp_get_wtime();
  for (int i = 1; i < 10; ++i)
  {
    f[1][i] = 1;//长度为1的序列只有一个
    g[1][i] = 1;//长度为1的序列只有一个
  }
  for (int i = 2; i < 10; ++i)
  {
    for (int j = 1; j < 10; ++j)
    {
      for (int k = 1; k < j; ++k)
        f[i][j] += f[i - 1][j - k];
    }
  }
  for (int i = 2; i <= 10; ++i)
  {
    for (int j = 1; j < 10; ++j)
    {
      for (int k = 1; k <= j; ++k)
        g[i][j - k] += g[i - 1][j];
    }
  }
  mpz_t zSum, t;
  mpz_inits(zSum, t, 0);
  mpz_set_ui(zSum, 99);
  for (int w = 3; w <= 100; ++w)//对数字位数进行枚举
  {
    //计算递增数的个数
    for (int k = 1; k < 9; ++k)//枚举跳跃点的个数
    {
      if (k > w - 1)
        break;
      mpz_bin_uiui(t, w - 1, k);//跳跃点的选取方式数
      int s = 0;
      //此时跳跃数组的长度为k+1
      for (int a = 1; a < 10; ++a)//计算具体的递增数组的选取方式数
        s += f[k + 1][a];
      mpz_mul_si(t, t, s);
      mpz_add(zSum, zSum, t);
    }
    //计算递减数的个数
    for (int k = 1; k <= 9; ++k)//枚举跳跃点的个数
    {
      if (k > w - 1)
        break;
      mpz_bin_uiui(t, w - 1, k);//跳跃点的选取方式数
      int s = 0;
      //此时跳跃数组的长度为k+1
      for (int a = 0; a < 10; ++a)//计算具体的递减数组的选取方式数
        s += g[k + 1][a];
      mpz_mul_si(t, t, s);
      mpz_add(zSum, zSum, t);
    }
    mpz_add_ui(zSum, zSum, 9);//加上跳跃数为0的数的个数
  }
  d = omp_get_wtime() - d;
  gmp_printf("%Zd\n%lf\n", zSum, d);
  mpz_clears(zSum, t, 0);
  return 0;
}