题目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

1. from math import factorial as f
   
2. 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

1. #include<iostream>
   
2. using ulong = unsigned long long;
   
3. 
   
4. 
   
5. template<size_t size>
   
6. constexpr ulong sum(ulong(&array)[size])noexcept {
   
7.     ulong result = 0;
   
8. 
   
9.     for (ulong i : array) {
   
10.         result += i;
    
11.     }
    
12. 
    
13.     return result;
    
14. }
    
15. 
    
16. 
    
17. template<size_t size>
    
18. constexpr void accumulate(ulong(&array)[size]) noexcept { //累加函数，参考 Python 的 itertools.accumulate
    
19.     for (size_t index = 1; index < size; index++) {
    
20.         array[index] += array[index - 1];
    
21.     }
    
22. }
    
23. 
    
24. 
    
25. constexpr ulong non_bouncy(size_t digits)noexcept {
    
26.     switch (digits) {
    
27.     case 0:
    
28.     case 1:
    
29.         return 0;
    
30.     }
    
31. 
    
32.     ulong array[]{ 1,2,3,4,5,6,7,8,9,9 };
    
33.     ulong result =
    
34.         9 //1位数既不是递增数也不是递减数
    
35.         + sum(array) * 2 - array[9] //递增数和递减数的和
    
36.         - --digits * 9 //每位都相同的数字，既属于递增数又属于递减数
    
37.         ;
    
38. 
    
39.     while (--digits) {
    
40.         accumulate(array);
    
41.         result += sum(array) * 2 - array[9];//递增数和递减数的和
    
42.     }
    
43. 
    
44.     return result;
    
45. }
    
46. 
    
47. 
    
48. int main() {
    
49.     using namespace std;
    
50.     ios::sync_with_stdio(false);
    
51.     cout << non_bouncy(100) << endl;
    
52.     return 0;
    
53. }

复制代码

guosl

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

1. /*
   
2. 答案：51161058134250
   
3. 耗时：0.000191秒
   
4. */
   
5. #include <iostream>
   
6. #include <mpir.h>
   
7. #include <omp.h>
   
8. using namespace std;
   
9. 
   
10. int f[10][10];//f[i][j]为长度是i且最后一个数的值是j的严格递增序列的个数
    
11. int g[11][10];//g[i][j]为长度是i且最后一个数的值是j的严格递减序列的个数
    
12. 
    
13. int main(void)
    
14. {
    
15.   double d = omp_get_wtime();
    
16.   for (int i = 1; i < 10; ++i)
    
17.   {
    
18.     f[1][i] = 1;//长度为1的序列只有一个
    
19.     g[1][i] = 1;//长度为1的序列只有一个
    
20.   }
    
21.   for (int i = 2; i < 10; ++i)
    
22.   {
    
23.     for (int j = 1; j < 10; ++j)
    
24.     {
    
25.       for (int k = 1; k < j; ++k)
    
26.         f[i][j] += f[i - 1][j - k];
    
27.     }
    
28.   }
    
29.   for (int i = 2; i <= 10; ++i)
    
30.   {
    
31.     for (int j = 1; j < 10; ++j)
    
32.     {
    
33.       for (int k = 1; k <= j; ++k)
    
34.         g[i][j - k] += g[i - 1][j];
    
35.     }
    
36.   }
    
37.   mpz_t zSum, t;
    
38.   mpz_inits(zSum, t, 0);
    
39.   mpz_set_ui(zSum, 99);
    
40.   for (int w = 3; w <= 100; ++w)//对数字位数进行枚举
    
41.   {
    
42.     //计算递增数的个数
    
43.     for (int k = 1; k < 9; ++k)//枚举跳跃点的个数
    
44.     {
    
45.       if (k > w - 1)
    
46.         break;
    
47.       mpz_bin_uiui(t, w - 1, k);//跳跃点的选取方式数
    
48.       int s = 0;
    
49.       //此时跳跃数组的长度为k+1
    
50.       for (int a = 1; a < 10; ++a)//计算具体的递增数组的选取方式数
    
51.         s += f[k + 1][a];
    
52.       mpz_mul_si(t, t, s);
    
53.       mpz_add(zSum, zSum, t);
    
54.     }
    
55.     //计算递减数的个数
    
56.     for (int k = 1; k <= 9; ++k)//枚举跳跃点的个数
    
57.     {
    
58.       if (k > w - 1)
    
59.         break;
    
60.       mpz_bin_uiui(t, w - 1, k);//跳跃点的选取方式数
    
61.       int s = 0;
    
62.       //此时跳跃数组的长度为k+1
    
63.       for (int a = 0; a < 10; ++a)//计算具体的递减数组的选取方式数
    
64.         s += g[k + 1][a];
    
65.       mpz_mul_si(t, t, s);
    
66.       mpz_add(zSum, zSum, t);
    
67.     }
    
68.     mpz_add_ui(zSum, zSum, 9);//加上跳跃数为0的数的个数
    
69.   }
    
70.   d = omp_get_wtime() - d;
    
71.   gmp_printf("%Zd\n%lf\n", zSum, d);
    
72.   mpz_clears(zSum, t, 0);
    
73.   return 0;
    
74. }

复制代码