正经题解｜寻找特别之数

题目解析

考虑 $\bf{数位DP}$。

将数字 $n$ 转化为字符串 $s$ 并 $\bf{反转}$，定义 $f(i, r, one, isLim)$ 表示构造低位第 $i$ 位及其之前数位的合法方案数，其余参数含义为：

• $r$ 表示前面选择的数字除以 $3$ 的余数。
• $one$ 表示前面选择的数字是否存在 $1$。若 $one = 1$ 表示存在 $1$，否则表示不存在 $1$。
• $isLim$ 表示当前是否受到了 $n$ 的约束（注意要构造的数字不能超过 $n$）。若为真，则第 $i$ 位填入的数字至多为 $s[i]$，否则可以是 $9$。如果在受到约束的情况下填了 $s[i]$，那么后续填入的数字仍会受到 $n$ 的约束。例如 $n=1234$ 那么 $i=3(s[3] = 4)$ 填的是 $4$ 的话，$i=2(s[2] = 3)$ 的这一位至多填 $3$。

AC代码

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

constexpr int N = 18;
constexpr int M = 3;

namespace DigitDp {
    string s;
    int n;

    i64 dp[N + 1][M][2];

    void init() {
        memset(dp, -1, sizeof dp);
    }

    i64 dfs(int i, int r, int one, int isLim) {
        if (i < 0) return r == 0 and one;
        if (!isLim and dp[i][r][one] != -1)
            return dp[i][r][one];
        i64 res = 0;
        int hi = (isLim ? s[i] - '0' : 9);
        for (int d = 0; d <= hi; ++d)
            res += dfs(i-1, (r*10+d)%3, one|(d==1), isLim and d == hi);
        if (isLim) return res;
        return dp[i][r][one] = res;
    }

    i64 calc(i64 x) {
        init();
        s = to_string(x);
        reverse(begin(s), end(s));
        n = s.size();
        return dfs(n - 1, 0, 0, true);
    }
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    DigitDp::init();
    int _; cin >> _;
    while (_--) {
        i64 l, r;
        cin >> l >> r;
        i64 lo = DigitDp::calc(l - 1);
        i64 hi = DigitDp::calc(r);
        cout << hi - lo << '\n';
    }
    return 0;
}

复杂度分析

采用记忆化搜索实现数位DP。

$\bf{数位DP的时间复杂度} = \bf{状态的个数} \times \bf{单个状态的计算时间}$。

本题状态的个数为 $O(N \times 3 \times 2)$，令 $D = 10$，计算单个状态的时间为 $O(D)$，所以本题数位DP的时间复杂度为 $O(6 \times N \times D)$。

本题 $\bf{DP数组}$ 可以 $\bf{复用}$ 与查询次数无关，总的时间复杂度为 $O(6ND + T)$。

若 $\bf{DP数组}$ 无法复用，则时间复杂度为 $O(6NDT)$。