数位DP

TODO

• 补充数位 \(DP\) 概念等
• 补充题目分析及过程
• 增加题目

题目

CF1073E. Segment Sum

CF1073E. Segment Sum

求 \(L\sim R\) 之间最多不包含 \(K\) 个数码的数的和

\(K\le10，L,R\le10^{18}\)

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
constexpr int MOD = 998244353;
i64 POW10[19] = {1};
int k;
// 从0位开始算，如 12 中 1位于1位置，2位于0位置
// dp1[i][j] : 第i位选择了状态为j，当前位置及其后的总方案数
// dp2[i][j] : 第i位选择了状态为j，当前位置及其后的总方案和
vector<vector<i64>> dp1(18, vector<i64>(1 << 10, -1));
vector<vector<i64>> dp2(18, vector<i64>(1 << 10, -1));
// 1. now   : 当前选择第几位
// 2. s     : 上界
// 3. mask  : 到当前位置，已经用了哪些数码和个数，first记录出现了哪些数码，second记录出现了多少个数码
// 4. limit : 前面数字是否紧贴上界，即是否有限制
// 5. have  : 前面是否填了数字，即是否为最高位
// 6. 返回值 : first方案数，second总方案和
pair<i64, i64> dfs(int now, const string& s, pair<int, int> mask, bool limit, bool have) {
    // debug(now, s, mask);
    // 已经不符合要求了
    if (mask.second > k) return {0, 0};
    // 从当前位置到最低位置，任意选都不会超过k个，则直接返回（499122177是2在模998244353意义下的乘法逆元）
    if (!limit && now + 1 + mask.second <= k) return {(POW10[now + 1] - !have) % MOD, (POW10[now + 1] - 1) % MOD * POW10[now + 1] % MOD * 499122177 % MOD};
    if (!limit && have && dp1[now][mask.first] != -1) return {dp1[now][mask.first], dp2[now][mask.first]};
    // 选到了最后一位了
    if (now == 0) {
        // 方案不能选多的数码了
        if (mask.second == k) {
            i64 sum = 0;
            i64 cnt = 0;
            int high = limit ? s[now] - '0' : 9;
            for (int i = 0; i <= high; ++i)
                if (mask.first >> i & 1)
                    sum += i, ++cnt;
            if (!limit && have) dp1[now][mask.first] = cnt, dp2[now][mask.first] = sum;
            return {cnt, sum};
        }
        // 在界限范围内任意选
        int high = limit ? s[now] - '0' : 9;
        int low = have ? 0 : 1;
        i64 cnt = high - low + 1;
        i64 sum = (low + high) * cnt / 2;
        if (!limit && have) dp1[now][mask.first] = cnt, dp2[now][mask.first] = sum;
        return {cnt, sum};
    }
    i64 cnt = 0;
    i64 sum = 0;
    // 是最高位，则可以跳过
    if (!have) {
        auto t = dfs(now - 1, s, mask, false, false);
        cnt = (cnt + t.first) % MOD, sum = t.second % MOD;
    }
    int low = have ? 0 : 1;
    int high = limit ? s[now] - '0' : 9;
    for (int i = high; i >= low; --i) {
        int a = mask.first | (1 << i);
        int b = mask.first >> i & 1 ? mask.second : mask.second + 1;
        auto t = dfs(now - 1, s, {a, b}, limit && i == high, true);
        cnt = (cnt + t.first) % MOD;
        sum = (sum + i * POW10[now] % MOD * t.first % MOD + t.second) % MOD;
    }
    if (!limit && have) {
        dp1[now][mask.first] = cnt;
        dp2[now][mask.first] = sum;
    }
    return {cnt, sum};
}
int main() {
    for (int i = 1; i < 19; ++i) POW10[i] = POW10[i - 1] * 10L;
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);
    string r;
    i64 _l;
    cin >> _l >> r >> k;
    string l = to_string(_l - 1);
    reverse(l.begin(), l.end());
    reverse(r.begin(), r.end());
    i64 ans1 = dfs(l.length() - 1, l, {0, 0}, true, false).second;
    i64 ans2 = dfs(r.length() - 1, r, {0, 0}, true, false).second;
    cout << (ans2 - ans1 + MOD) % MOD << endl;
}