欧拉项目 | 113题 | 单调数字

Problem 113

一个数如果左边的数字不会超过右边的数字，那么称为递增数，比如134468
反之，如果右边的数字不会超过左边的数字，那么称为递减数，比如66420
除了上述两种数之外的数称为跳跃数，比如155349
随着$n$的增加，跳跃数的比例在上升（非跳跃比例下降），比如一百万内有 12951 个非跳跃数，$10^{10}$以内有 277032 个非跳跃数。
求$10^{100}$以内有多少个非跳跃数。

很显然，不可能遍历。算法要和指数的大小相关。很直观的，要想办法从$i$位数字中非跳跃数的个数构造出$i+1$位数字中非跳跃数的个数。

我们首先考虑递增的情况。有一个$i$位的递增数，如果起始数字是$d$，那么可以往它的前面插入一个小于等于$d$的数字，构成$i+1$位的递增数，反过来想，第一个字母是$d$的$i+1$位递增数的个数是$d$到$9$开头的$i$位递增数的个数之和。那么，构造一个二维数组，一层一层往后计算即可。

private static long GetIncreasingCount()
{
    //          9,8,7...,3,2,1
    // 1 digits 1,1,1...,1,1,1
    // 2 digits 1,2,3...
    // n digits
    long[,] matrix = new long[Power, 9];
    for (int i = 0; i < 9; i++)
    {
        matrix[0, i] = 1;
    }
    for (int i = 1; i < Power; i++)
    {
        long count = 0;
        for (int j = 0; j < 9; j++)
        {
            count += matrix[i - 1, j];
            matrix[i, j] = count;
        }
    }
    return matrix.Cast<long>().Sum();
}

递减数的个数类似，需要特殊考虑下零即可。

最后，递增数和递减数有重合，比如33，111，8888这种，重复个数是9乘以幂次数，这里是100。