目前的解决方案...

...做了很多不必要的工作。所有数字均已整理并检查。没必要。例如，如果一个数字看起来像132xxxxxxx，那么它和它的所有邻居都可以被跳过。他们肯定不会通过考验。

路短...

...哈利在对该问题的评论中建议。你看到数字顺序了吗？在OEIS百科全书中找到它：https://oeis.org/search?q =1+10+100+475+1675+4954+12952 。不会有完全匹配，但会引用没有前导的序列：A364342。我们阅读文章，确保这是我们的序列，找到公式，对其进行编程，准备就绪。

如果你运气不好的话...

...并且没有找到序列，你将不得不用你的头脑来解决问题。我们将分别统计递增数和递减数。

数量不断增加

您需要经验来猜测n _,d - 恰好n位且第一位数字不小于d的递增数字的数量。事实：

• a _n,9 = 1 – n位数中只有一个以 9 开​​头的数字；
• a _1,d = 10 - d – 从一位数字开始递增的数字的数量很容易计算；
• a _n,d = a _n,d+1 + a _n-1,d是一个重要的公式。如果数字以严格大于d 的数字开头，则第一项“计数”此类数字。如果数字以等于d的数字开头，则第二项“计数”此类数字。在此公式中，n > 1且d < 9。

我们对不断增加的最多n位数字感兴趣。让我们用n_来表示它们。关注一个指标。

a _n = 1 + Σ _1≤j≤n a _j,1 – 您需要将所有合适长度的递增数相加，并加一为零。

代码直接重复了公式：

unsigned long long a(unsigned n, unsigned d) {
    if (d == 9) {
        return 1;
    }
    if (n == 1) {
        return 10 - d;
    }
    return a(n, d + 1) + a(n - 1, d);
}

unsigned long long a(unsigned n) {
    unsigned long long s = 1;
    for (unsigned j = 1; j <= n; ++j) {
        s += a(j, 1);
    }
    return s;
}

降序数字

方案是相同的：b _n,d - 正好n位数字的降序数字链（不是数字 - 这在这里很重要），并且第一个数字不超过d。

• b _n,0 = 1 – 只有一个n位数字的降序链从零开始；
• b _1,d = d + 1 – 一位数的下降链的数量很容易计算；
• b _n,d = b _n,d-1 + b _n-1,d – 如果数字以严格小于d 的数字开头，则第一项“计数”此类数字。如果数字以等于d的数字开头，则第二项“计数”此类数字。在此公式中，n > 1且d > 0。

我们对所有不超过n位的递减数字（这次不是链，数字）感兴趣。让我们用b _n来表示它们。再次，注意一个指标。

b _n = (Σ _1≤j≤n b _j,9 ) - (n - 1) – 您需要添加所有合适长度的递增链并减去非数字链。有n-1 个这样的链：00 , 000 , 0000 , ...

unsigned long long b(unsigned n, unsigned d) {
    if (d == 0) {
        return 1;
    }
    if (n == 1) {
        return d + 1;
    }
    return b(n, d - 1) + b(n - 1, d);
}

unsigned long long b(unsigned n) {
    unsigned long long s = 0;
    for (unsigned j = 1; j <= n; ++j) {
        s += b(j, 9);
    }
    return s - (n - 1);
}

“单调”数字

“单调”数字的数量c _n：

• c ₀ = 1 – 对于n = 0 ，序列a和b未定义，需要单独定义；

• 其中_n = a _n + b _n - 9·n - 1 – “单调”数字的数量是递增数字的数量加上递减数字的数量减去我们计算了两次的数字。零和所有数字都相同的数字会被计算两次：333、9999。这样的数有9·n 个。

unsigned long long c(unsigned n) {
    if (n == 0) {
        return 1;
    }
    return a(n) + b(n) - 9 * n - 1;
}

动态规划

我的硬件上的这个解决方案在一秒钟内计算出c ₂₅ = 236030401 。它比以前更好，但还可以更好。对于相同的参数，会重复调用a(n, d)和函数。b(n, d)让我们用表格替换它们：

unsigned long long a(unsigned n) {
    std::vector<std::array<unsigned long long, 10>> a(n + 1);
    for (unsigned i = 1; i < 10; ++i) {
        a[1][i] = 10 - i;
    }
    for (unsigned j = 2; j <= n; ++j) {
        a[j][9] = 1;
        for (unsigned i = 8; i > 0; --i) {
            a[j][i] = a[j][i + 1] + a[j - 1][i];
        }
    }

    unsigned long long s = 1;
    for (unsigned j = 1; j <= n; ++j) {
        s += a[j][1];
    }
    return s;
}

unsigned long long b(unsigned n) {
    std::vector<std::array<unsigned long long, 10>> b(n + 1);
    for (unsigned i = 1; i < 10; ++i) {
        b[1][i] = i + 1;
    }
    for (unsigned j = 2; j <= n; ++j) {
        b[j][0] = 1;
        for (unsigned i = 1; i < 10; ++i) {
            b[j][i] = b[j][i - 1] + b[j - 1][i];
        }
    }

    unsigned long long s = 0;
    for (unsigned j = 1; j <= n; ++j) {
        s += b[j][9];
    }
    return s - (n - 1);
}

对于n ≤ 375 ，此代码快速且正确地进行计数。c ₃₇₅ = 17980269677772943001。然后就溢出了unsigned long long。计算需要微秒，你可以冷静一下。但有一种更快的方法并且代码更少。

球和挡板方法

待办事项：继续

这是优化版本的样子：

#include <iostream>

unsigned long long cnk(unsigned long long n, unsigned long long k) {
    unsigned long long p = 1;
    for (unsigned long long i = 1; i <= k; ++i) {
        p = p * (n - k + i) / i;
    }
    return p;
}

unsigned long long mono(unsigned n) {
    return cnk(n + 9, 9) + cnk(n + 10, 10) - 10 * n - 1;
}

int main() {
    unsigned n;
    if (std::cin >> n) {
        std::cout << mono(n) << '\n';
    }
}