一个不需要用DFS的轻松做法....

实现一个 calc 函数

求出 x ~ 与x位数相同的最大值之间的合法数个数。

比如 x = 1234，那么就是 1234 ~ 9999 之间的合法数的个数。

如果 A,B 位数相同，利用前缀和的思想减一下就行。

如果位数不同，中间的位数是可以直接算出答案的，因为第一个数有7种，剩下的数8种选择。搞一个快速幂就行。

#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize(2)
#define int long long
#define endl '\n'
#define PII pair<int,int>
#define INF 1e18

//快速幂
int power(int a, int b) {
    int s = 1;
    while (b) {
        if (b & 1) s = s * a;
        a *= a;
        b >>= 1;
    }
    return s;
}

// a, b 数组存 a,b 的数位
vector<int> a, b;

// 获得 x 的数位数组
vector<int> getdigit(int x) {
    int t = x;
    int cnt = 0;
    vector<int> xx;
    while (t) {
        xx.push_back(t%10);
        t/=10;
    }
    return xx;
}

// 检查x中的数位是否含有4 or 9
bool check(int x) {
    while (x) {
        if (x%10 == 4 or x%10 == 9) return false;
        x/=10;
    }
    return true;
}

/*
    calc 函数计算：
    xxxx ~ 9999（同数位长度）下有多少不含4和9的数
    原理如下：
    以 xxxx = 12345 为例。
    首先算以 2,3,5,6,7,8 开头的数
    2,_,_,_,_ 后面的数随便填，即 8*8*8*8
    3,_,_,_,_ 后面的数随便填，即 8*8*8*8
    5,_,_,_,_ 后面的数随便填，即 8*8*8*8
    7,_,_,_,_ 后面的数随便填，即 8*8*8*8
    ....
    然后第二位，第一位此时必须是 1（因为第一位其他的可能已经被计算完了）
    1,_,_,_,_
    第二位的选择有 3,5,6,7,8
    1,3,_,_,_,_ 后面的数随便填，即 8*8*8
    1,5,_,_,_,_ 后面的数随便填，即 8*8*8
    1,6,_,_,_,_ 后面的数随便填，即 8*8*8
    1,7,_,_,_,_ 后面的数随便填，即 8*8*8
    ....

    然后再看第三位，此时前两位必须是 1,2
    .....

    直到处理完所有位。

    时间复杂度是 O(len * 8 * log(len))，这个 8 可以优化掉，只不过我懒得拆循环。
*/
int calc(int xx) {
    int sum = 0;
    vector<int> tt = getdigit(xx);

    for (int i = tt.size() - 1; i >= 0; i--) {
        for (int j = tt[i]; j <= 9; j++) {
            if (j > tt[i] and j != 4 and j != 9)
                sum += power(8, i);
        }
        // 此时已经算完了从最高位到i位的情况，那么第i位就必须是和tt[i]一样了。如果tt[i]是4or9，直接break即可。
        if (tt[i] == 4 or tt[i] == 9) break;
    }
    //最终看一下 xx 是不是不含 4,9
    if (check(xx)) sum ++;
    return sum;
}


void slove () {
    int A, B;
    cin >> A >> B;

    a = getdigit(A);
    b = getdigit(B);

    // 如果 A, B 位数相同，那么计算一下 A ~ 同位最大值的答案 - B ~ 同位最大值的答案 + B 本身
    if (a.size() == b.size()) {
        int sum = calc(A) - calc(B);
        if (check(B)) sum ++;
        cout << B - A + 1 - sum << endl;
    } else {
        // 如果位数不同，中间的位数没有限制可以直接算，比如有len位，那么开头可以选 7个数，剩下每个数位8种选择，答案就是 7*power(8, len - 1)
        int sum = 0;
        sum += calc(A);
        sum += calc(power(10, b.size() - 1)) - calc(B);

        if (check(B)) sum ++;
        for (int i = a.size() + 1; i < b.size(); i++) {
            sum += 7 * power(8, i - 1);
        }
        cout << B - A + 1 - sum << endl;
    }
}

signed main () {
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    slove();
}