形式化题目

一个正整数是不降数，当且仅当把它写成十进制串 $d_1 d_2 \dots d_k$（$d_1 \neq 0$）后，从左到右每一位都不小于前一位，即

给定 $a, b$（$1 \leqslant a \leqslant b \leqslant 2^{31} - 1$），求 $[a, b]$ 中不降数的个数。输入有多组，每组一行两个整数，读到文件结束；每组输出一行答案。

样例：1 9 输出 9，1 19 输出 18。

• 1 9：一位数 $1 \sim 9$ 全部符合，共 $9$ 个。
• 1 19：在 $1 \sim 9$ 的 $9$ 个之外，两位的 $11, 12, \dots, 19$ 也都满足 $1 \leqslant$ 个位，共 $9$ 个，合计 $18$。

注意 $10$ 不是不降数（$1 > 0$），$20$、$110$ 也都不是。

正解

思路

朴素做法与它的瓶颈。 最直接的想法是从 $a$ 枚举到 $b$，对每个数把数位串排序后与原串比较。复杂度 $O\big((b-a)\log b\big)$，而 $b - a$ 最大接近 $2 \times 10^9$，必然超时。瓶颈在于逐个枚举数字：相邻两个数是否不降几乎无关（$123$ 是，$130$ 就不是），枚举过程中攒不出可跳过的增量信息。

换个角度看，“不降"只约束相邻两位，是一个纯数位性质。而 $[0, n]$ 中的数完全由"前 $i$ 位是什么、第 $i+1$ 位起是否还贴着上界"决定。于是把枚举单位从"数字"改成"数位前缀”。

第一步：区间拆成两个前缀计数。 记

则答案为

第二步：把 $[0, n]$ 按"首次小于上界的位置"分类。 设 $n$ 的数位为 $d_1 d_2 \dots d_k$。任何与 $n$ 位数相同且小于 $n$ 的 $x$，都存在唯一的位置 $i$，使得前 $i-1$ 位与 $n$ 完全相同，而第 $i$ 位 $x_i < d_i$。

对固定位置 $i$，设 $r = k - i$ 是它后面还剩的位数，$\ell$ 是上一位的数字（若前面全是前导零则令 $\ell = 0$）：

• 分支要求 $x_i = v$ 且 $v \geqslant \ell$（否则前缀就已违反不降，这些 $v$ 直接不合法），所以 $v \in [\ell,\ d_i - 1]$；
• 由于 $v < d_i$ 已经把 $x$ 压到 $n$ 以下，后 $r$ 位不再受上界约束，只需非降且每位 $\geqslant v$。

这一段的数量记作 $W(r, v)$，于是第 $i$ 位贡献 $\sum_{v=\ell}^{d_i-1} W(r, v)$。

第三步：前导零让长短不一的数自动纳入。 $F(n)$ 还要统计位数比 $n$ 少的数（$n = 150$ 时的 $1 \sim 99$）。技巧是把前导零也当成数位：从最高位开始扫描时，只要前面全是 $0$ 就认为"这个数还没开始"，此时令 $\ell = 0$ 而不是沿用上一位的 $0$。这样在位置 $i$ 取 $v = 0$ 就恰好代表"更短的数 / 数还没开始"，短位数被自动计入，无需额外枚举。代码里用哨兵 LEAD = 10 表示"上一位不存在"，避免和合法数位 $0 \sim 9$ 混淆。

第四步：自由段的闭式解。 $W(r, \ell)$ 是"从 $\ell, \ell+1, \dots, 9$ 这 $10 - \ell$ 种数字里，可重复地取 $r$ 个组成非降序列"的方案数。这不就是隔板法吗——把 $r$ 个取值和 $9 - \ell$ 块隔板排成一列，选出 $r$ 个位置当取值即可：

代码不必真去算组合数，按 $r$ 递推更省事：

因为 $W(r-1,\ell) \cdot (r + 9 - \ell)$ 恰好是 $\binom{r+9-\ell}{r}$ 的 $r$ 倍，整除总成立，用整数运算无精度问题。递推用 @cache 记忆化，状态只有 $r \leqslant 10$、$\ell \leqslant 10$ 共百余个。

第五步：若 $n$ 自身在某一断裂掉。 沿主链走时若发现 $d_i < \ell$，说明 $n$ 的前 $i$ 位已经不是不降前缀，后面不存在任何合法分支，可以立即返回；此时 $n$ 自己也不是不降数，不加最后那 $1$。若走完全程都合法，说明 $n$ 本身是不降数，答案再 $+1$。

以 $n = 19$ 为例逐位累加（count_upto(19)，数位 [1, 9]；列的含义：i 是位置、cur 是 $n$ 在该位的数字、rest 是剩下位数、候选 v 与它们的 $W$ 值）：

两行都走完后 $n$ 自身合法，再 $+1$：$F(19) = 10 + 8 + 1 = 19$。而 $F(0) = 1$，故 $[1, 19]$ 得 $19 - 1 = 18$，与样例一致。第一行的 $W(1,0) = 10$ 正是"$0 \sim 9$ 开头、后面随便填一位"的那批数，也就是一位数 $0 \sim 9$ 本身——前导零分支一次性覆盖了它们。

下图展示"贴着上界"的主链与每个位置挂出去的分支（以 $n = 19$ 为例）：

graph TD
    root["前缀为空<br/>high = LEAD（数未开始）"] -->|"x₁ = 1（贴住上界）"| n1["前缀 1<br/>high = 1"]
    root -.->|"x₁ = 0 < 1，首次变小"| b0["前缀 0<br/>低位自由，≤ 9 都可<br/>贡献 W(1,0) = 10"]
    n1 -->|"x₂ = 9（贴住上界）"| n2["前缀 19 = n<br/>n 自身合法，+1"]
    n1 -.->|"x₂ ∈ [1,8] < 9，首次变小"| b1["前缀 1v<br/>低位自由<br/>贡献 W(0,v) = 1，共 8 项"]

粗看这张图可以得到两点：实线只有一条（贴着上界走的主链），这正是逐位扫描的循环；虚线是从主链节点挂出去的子树，每棵子树内低位完全自由，因而能用闭式 $W$ 一次算完，不必递归展开。所谓"数位 DP 的记忆化"在这里被压缩成了 $O(1)$ 的组合数——这也是本解与记忆化搜索写法复杂度同阶、常数却更小的原因。

代码

Python 版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 10:20
# update_at: 2026-10-02 10:20

import sys
from functools import cache

DIGITS = 10   # 十进制数位取值 0..9
LEAD = 10     # 状态哨兵：当前这位还没定下来（更高位全是前导零），下一位可以任取


@cache
def ways(length: int, low: int) -> int:
    """长度为 length、每一位都取自 [low, 9] 且相邻不降的串有多少个。

    这就是"从 low..9 里允许重复地取 length 个数的非降序列"的数量，
    即组合数 C(length + 9 - low, length)：把 length 个位置上的取值
    和 9 - low 个"分隔板"排成一列，选 length 个位置当作取值即可。
    """
    return 1 if length == 0 else ways(length - 1, low) * (DIGITS + length - 1 - low) // length


def count_upto(n: int) -> int:
    """统计 [0, n] 内有多少个"从左到右各位数字不降"的数（含 0，它只有一位）。"""
    if n < 0:
        return 0
    digits = [int(c) for c in str(n)]

    # 逐位确定前缀。high 是上一位的数字，LEAD 表示更高位还全是前导零；
    # 前导零不参与"不降"的判定，所以数位长度天然可以比 len(digits) 短。
    total, high = 0, LEAD
    for i, cur in enumerate(digits):
        rest = len(digits) - i - 1  # 这一位固定后，低位还剩多少位
        low = 0 if high == LEAD else high
        # 这一位取 [low, cur-1]，低位就能自由填任意不降串（上限已被压小，不再受限）
        total += sum(ways(rest, d) for d in range(low, cur))
        if cur < low:  # n 自身在这一位就违反了不降，前缀只能到此为止
            return total
        high = cur
    return total + 1  # 每一位都贴着 n，n 本身也是不降数


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    out = []
    # 多组数据，EOF 结束；a-1 可能为 0，count_upto 已处理
    for a, b in zip(data, data):
        out.append(count_upto(b) - count_upto(a - 1))
    print('\n'.join(map(str, out)))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 10:39
 * update_at: 2026-10-05 10:39
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int LEAD = 10; // 哨兵：上一位"还不存在"（更高位全是前导零），避免和合法数位 0~9 混淆

ll w[15][15];  // w[r][low] = 长度为 r、每位取自 [low, 9] 且非降的串数 = C(r + 9 - low, r)
ll digits[15]; // n 的十进制数位，digits[1] 是最高位
ll len;        // n 的位数

// 预处理自由段的组合数：把 r 个取值和 9 - low 块隔板排成一列，选 r 个位置当取值。
// 递推 w[r][low] = w[r-1][low] * (r + 9 - low) / r，整数整除恒成立，无精度问题。
void init_ways() {
    for (int low = 0; low <= LEAD; low++) {
        w[0][low] = 1;
        for (int r = 1; r <= 11; r++) {
            w[r][low] = w[r - 1][low] * (r + 9 - low) / r;
        }
    }
}

// 统计 [0, n] 内有多少个不降数（0 也算一位数，count_upto(0) = 1）。
// 把 [0, n] 按"第 i 位首次小于上界"分类：该位取 v ∈ [low, cur-1] 压到 n 以下后，
// 剩余 rest 位彻底自由，只需非降且每位 >= v，用 w[rest][v] 一次算完。
ll count_upto(ll n) {
    if (n < 0) return 0;

    // 拆数位，digits[1] 为最高位
    len = 0;
    ll t = n;
    while (t > 0) {
        len++;
        digits[len] = t % 10;
        t /= 10;
    }
    for (ll i = 1; i <= len / 2; i++) {
        swap(digits[i], digits[len + 1 - i]);
    }

    ll total = 0;
    ll high = LEAD; // 上一位的数字；LEAD 表示数还没开始（前面全是前导零）
    for (ll i = 1; i <= len; i++) {
        ll cur = digits[i];
        ll low = 0; // 本位的下界：数还没开始时前导零不参与不降判定，可取 0
        if (high != LEAD) low = high;
        ll rest = len - i; // 这一位固定后，低位还剩多少位

        // 枚举本位首次小于上界的取值 v，低位自由填不降串
        for (ll v = low; v < cur; v++) {
            total += w[rest][v];
        }
        if (cur < low) return total; // n 自身在这一位断裂，更深的链全部不合法，立即返回
        high = cur;
    }
    return total + 1; // 每一位都贴着 n，n 本身也是不降数
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    init_ways();

    ll a, b;
    // 多组数据，EOF 结束；答案 = F(b) - F(a-1)
    while (cin >> a >> b) {
        cout << count_upto(b) - count_upto(a - 1) << "\n";
    }

    return 0;
}

复杂度

设 $n$ 的位数为 $k \leqslant 10$，数据组数为 $T$。

• 时间复杂度：$O(Tk)$。count_upto 的主循环 $k$ 次，每次至多求和 $10$ 项，而每项 ways(r, v) 在 @cache 下摊还 $O(1)$（r 和 low 都至多取 $11$ 种值，状态总数有常数上界 $121$；实测 $n = 2^{31}-1$ 时只生成 $20$ 项）。参考实现 12.cpp 的记忆化数位 DP 状态 $O(10k)$、转移 $O(10)$，量级相同；本解把自由段用组合闭式一次结清，常数更小。$k \leqslant 10$ 意味着每组数据只有几十次基本运算，$1000\,\text{ms}$ 绰绰有余（12 组真实数据实测 0.017 s）。
• 空间复杂度：$O(1)$。@cache 的条目数有常数上界，加上 $O(k)$ 的数位表与输出缓冲，实测峰值 14.7 MB，远低于 $128\,\text{MB}$。

总结

• 数位性质就按位处理：区间计数先差分成 $F(b) - F(a-1)$，再把 $[0, n]$ 按"第 $i$ 位首次小于上界"唯一分类，做到不重不漏。
• 一旦某位变小，低位就彻底自由：自由段的约束只剩"非降且不小于该位"，由隔板法得闭式 $W(r,\ell) = \binom{r+9-\ell}{r}$，$O(1)$ 结清——这是把记忆化搜索压成组合计数的关键。
• 前导零是"数还没开始"的标记：用哨兵 LEAD 把它和真正的数位 $0$ 区分开，短位数就自动被覆盖，不必为每种长度单独统计。
• 断裂即停：一旦 $d_i < \ell$，$n$ 自身与更深的链全部不合法，立即返回，同时决定是否补上 $+1$。
• 整体复杂度 $O(Tk)$，$k \leqslant 10$，Python 实测 0.017 s / 14.6 MB，稳定通过。