Moe's CF Life

喵~ 主人，下午好呀！今天我们来看一道非常有趣的计数问题，叫做 Classy Numbers。别担心，这道题虽然看起来有点吓人，但只要跟着我的思路一步一步来，就会发现它其实是一只很温顺的小猫咪呢，喵~

题目大意

首先，我们来理解一下什么是 "Classy Number" 吧！

一个正整数如果它的十进制表示中，非零数字 的个数不超过 3 个，那它就是一个 "Classy Number"。

举几个例子就好懂啦：

4 (1个非零), 200000 (1个非零), 10203 (3个非零) —— 这些都是 Classy Numbers。
4231 (4个非零), 102306 (4个非零) —— 这些就不是啦，因为它们的非零数字超过 3 个了。

题目会给我们很多个查询，每个查询包含一个区间 [L, R]。我们的任务就是，对于每个区间，找出里面有多少个 Classy Number。

注意哦，L 和 R 最大可以到 10^18，这么大的范围，想一个一个数过去是不可能的，会累死猫的喵... 所以我们需要一个更聪明的办法！

题解方法

看到这种 “在很大区间内统计满足特定数位条件的数的个数” 的问题，我们的第一反应就应该是 数位DP 啦！

数位DP是一种动态规划技巧，专门用来解决这类问题。它的核心思想是：

差分思想: 要求 [L, R] 区间内的数量，我们可以把它转换成 count(1, R) - count(1, L-1)。这样，问题就简化为实现一个函数 solve(n)，用来计算 [1, n] 中有多少个 Classy Number。
逐位构造: 我们不直接去数，而是去 “构造” 所有小于等于 n 的 Classy Number。我们从高位到低位，一位一位地填数字，并记录下当前状态，比如已经填了多少位，用了多少个非零数字等等。

为了保证我们构造的数不超过 n，我们需要一个特殊的标记，通常叫做 tight 或者 limit。这个标记告诉我们，当前位能填的数字是否受到了 n 对应位的限制。

比如说，我们要计算 [1, 520] 范围内的数。

当我们构造百位数时，如果填了 1, 2, 3, 4，那么后面的十位和个位就可以随便填 0-9 了，因为无论怎么填，结果都小于 520。这时 tight 限制就解除了。
但如果我们百位数填了 5，和 520 的百位一样，那么十位数就最多只能填 2。这时 tight 限制依然存在。

这样，我们就可以通过一个递归函数，带着这些状态信息，把所有情况都统计出来啦！

题解详解

好啦，现在我们来仔细看看这份代码是怎么实现这个思路的，喵~

cpp

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstring>

// R 可以到 10^18，所以要用 long long 喵
using ll = long long;

// 全局变量
std::string S; // 把数字 n 转换成字符串，方便按位处理
ll memo[20][4][2][2]; // 记忆化数组，避免重复计算

// 核心的 DP 函数
// pos: 当前处理到第几位 (从左往右，0-indexed)
// cnt: 到目前为止，已经使用的非零数字的个数
// tight: 是否受到 n 的限制 (true 表示是，false 表示否)
// is_leading: 当前是否正在处理前导零 (true 表示是，false 表示否)
ll dp(int pos, int cnt, bool tight, bool is_leading) {
    // === 递归边界 ===
    // 1. 非零数字超过3个了，此路不通，返回0
    if (cnt > 3) {
        return 0;
    }
    // 2. 所有位都填完了，说明成功构造了一个合法的数，返回1
    if (pos == S.size()) {
        return 1;
    }
    
    // === 记忆化 ===
    // 就像猫猫会记住藏鱼干的地方一样，我们也记住算过的结果
    if (memo[pos][cnt][tight][is_leading] != -1) {
        return memo[pos][cnt][tight][is_leading];
    }

    ll ans = 0;
    // 确定当前位能填的数字的上限
    int upper_bound = tight ? (S[pos] - '0') : 9;

    // 尝试在当前位填入 0 到 upper_bound 之间的每个数字
    for (int digit = 0; digit <= upper_bound; ++digit) {
        // 如果当前是前导零阶段，并且我们填的也是0
        if (is_leading && digit == 0) {
            // 那么下一位依然是前导零阶段，非零数个数不变
            // tight 限制的传递：只有当这一位也达到了上限，下一位才会继续受限
            ans += dp(pos + 1, cnt, tight && (digit == upper_bound), true);
        } else {
            // 只要填了一个非0数字，或者在非0数字后填0，前导零阶段就结束了
            // cnt 的更新：只有当填的 digit 不是0时，非零数字个数才+1
            // is_leading 变为 false
            ans += dp(pos + 1, cnt + (digit != 0), tight && (digit == upper_bound), false);
        }
    }

    // 把结果存起来再返回
    return memo[pos][cnt][tight][is_leading] = ans;
}

// 计算 [1, n] 中 Classy Number 个数的辅助函数
ll solve_for(ll n) {
    if (n == 0) {
        return 0;
    }
    S = std::to_string(n);
    // 每次计算前，要把记忆化数组重置为-1，表示都没算过
    memset(memo, -1, sizeof(memo));
    
    // dp(0, 0, true, true) 计算的是 [0, n] 范围内的个数
    // 初始状态：从第0位开始，用了0个非零数，受n限制，是前导零阶段
    // 题目要求正整数，所以我们要把 0 这个数（它有0个非零数字，被我们算进去了）排除掉
    return dp(0, 0, true, true) - 1;
}

void solve() {
    ll l, r;
    std::cin >> l >> r;
    // 使用差分思想求解
    ll ans = solve_for(r) - solve_for(l - 1);
    std::cout << ans << "\n";
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

代码讲解小贴士：

solve_for(n) 函数:
- 这是我们通往答案的入口。它把数字 n 转成字符串 S，这样就能用 S[pos] 来获取第 pos 位的数字了。
- memset(memo, -1, sizeof(memo)) 是在告诉我们的猫咪大脑：“忘掉上次计算的结果，我们要开始一次新的冒险啦！”
- dp(0, 0, true, true) 的调用是关键。初始时：
  - pos = 0: 从最高位开始。
  - cnt = 0: 还没用任何非零数字。
  - tight = true: 我们要构造的数必须小于等于 n，所以一开始肯定受 n 的最高位限制。
  - is_leading = true: 一开始我们可能填前导零。
- 最后为什么要 -1 呢？因为我们的 dp 函数会把 0 也算作一个合法的 Classy Number（它有0个非零数字）。但题目要求的是 正整数，所以要把 0 去掉。
dp 函数的状态转移:
- upper_bound 的计算完美体现了 tight 标记的作用。如果 tight 为 true，当前位最多只能填到 S[pos]；否则，就可以随便填到 9。
- cnt + (digit != 0) 是一个很巧妙的写法。当 digit 不为 0 时，digit != 0 的值为 true，在C++里转成 int 就是 1，cnt 就增加了。如果 digit 是 0，cnt 就不变。这涵盖了 is_leading 为 false 之后的情况。
- tight && (digit == upper_bound): 只有当之前就受限，并且当前位也取到了上限值时，下一位才会继续受限。只要有一次没取到上限，后面的位就自由啦！
- is_leading && (digit == 0): 只有当之前是前导零，并且当前位继续填 0 时，下一位才继续是前导零。

把这些逻辑组合起来，dp 函数就能不重不漏地，把所有小于等于 n 的 Classy Number 都数一遍啦！最后用 solve_for(r) - solve_for(l - 1)，就能得到最终答案。是不是很优雅呢？喵~

知识点介绍：数位DP入门

最后，给对数位DP还不太熟悉的主人科普一下吧！

数位DP (Digit DP) 是一种用于解决特定类型计数问题的动态规划方法。

它适合什么样的问题？ 通常是问你在一个非常大的数字区间 [L, R] 内，有多少个数满足某种与“数位”相关的性质。比如：

数字中不含 4 和 62。
数字中每个数位上的数字之和是 k 的倍数。
就像本题，数字中非零数的个数不超过 k。

它的核心套路是什么？ 一般都是一个 dfs 或者 dp 的递归函数，其参数通常包含：

pos: 当前正在处理第几位。
state: 一个或多个变量，用于记录题目要求的状态。在本题中就是 cnt。
tight (或 limit): 一个布尔值，标记当前位的选择是否受上限数字的限制。这是数位DP的灵魂！
is_leading (或 lead): 一个布尔值，用于处理前导零的特殊情况（比如前导零不算入计数，或者有特殊限制）。

通过 记忆化搜索 (将 (pos, state, tight, is_leading) 的结果存起来)，我们可以将指数级的暴力搜索优化到接近多项式的复杂度，从而解决 10^18 这种大数据范围的问题。

希望这次的讲解能帮助主人理解这道题和数位DP这个可爱的知识点！如果还有不懂的地方，随时可以再来问我哦，喵~ (ฅ'ω'ฅ)

题目大意 ​

题解方法 ​

题解详解 ​

代码讲解小贴士： ​

知识点介绍：数位DP入门 ​

题目大意

题解方法

题解详解

代码讲解小贴士：

知识点介绍：数位DP入门