NC200204 数位 DP-Toy模板网

这篇具有很好参考价值的文章主要介绍了NC200204 数位 DP。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题意

传送门 NC200204 dh的帽子

题解

可以独立考虑每一位是否合法。维护数字上下界的状态，枚举三个数字，仅对合法的状态进行转移。数位 DP 求解即可，时间复杂度 $O (l o g R)$ 。文章来源地址https://www.toymoban.com/news/detail-565799.html

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int N = 20;
ll dp[20][8][8];
vector<int> big, small;

ll rec(int k, int llim, int ulim) {
    if (k < 0) {
        return 1;
    }
    if (dp[k][llim][ulim] != -1) {
        return dp[k][llim][ulim];
    }
    ll res = 0;
    for (int x = 0; x < 8; ++x) {
        int ok = 1, l = 0, u = 0;
        for (int i = 0; i < 3; ++i) {
            int lb = (llim >> i & 1) ? small[k] : 0;
            int ub = (ulim >> i & 1) ? big[k] : 1;
            int t = x >> i & 1;
            if (t < lb || t > ub) {
                ok = 0;
                break;
            }
            l |= (t == lb) << i;
            u |= (t == ub) << i;
        }
        if (!ok) {
            continue;
        }
        int xors = 0, ors = 0;
        for (int i = 0; i < 3; ++i) {
            int t = x >> i & 1;
            xors ^= t;
            ors |= t;
        }
        if (xors != ors) {
            continue;
        }
        res += rec(k - 1, llim & l, ulim & u);
    }
    return dp[k][llim][ulim] = res;
}

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

    int l, r;
    cin >> l >> r;
    auto get = [](int x) {
        vector<int> a;
        while (x > 0) {
            a.push_back(x & 1);
            x >>= 1;
        }
        return a;
    };
    big = get(r), small = get(l);
    int n = max(big.size(), small.size());
    small.resize(n);

    memset(dp, -1, sizeof(dp));
    cout << rec(n - 1, 7, 7) << '\n';

    return 0;
}